本文共 2562 字，大约阅读时间需要 8 分钟。

插入排序

插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序可以分为直接插入排序和希尔排序。

直接插入排序

相信大家都玩过扑克牌（即使没玩过，也听说过）。

• 当我们手里有第一张牌的时候，随便放
• 当有第二张牌的时候，与第一张牌进行比较，比第一张大，放在它的后面，比一张小，放在它的前面
• 当有第三张牌的时候，与前两张比较，选择位置插入
• 以此类推

这就是插入，类比到我们排序中，就能得到如下步骤

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤2~5
   代码如下：

void InsertSort(int arr[], int size)	{
   		for (int i = 1; i < size; i++) //i表示当前要排序的数		{
   			int key = arr[i];			int j;			for (j = i - 1; j >= 0; j--) //从i的前一个元素开始往前找			{
   				if (arr[j] > key)				{
   					arr[j + 1] = arr[j];				}				else				{
   					break;				}			}			arr[j + 1] = key;		}	}

时间复杂度：O(n ^ 2)

二分插入排序

由于上述在查找比较关键码的时候，会比较慢。因为关键码前面已经有序，就可以运用二分查找的思想来判断关键码的位置。

void InsertSort(int arr[], int size)	{
   		for (int i = 1; i < size; i++)		{
   			int tmp = arr[i];			//加入了一个二分查找的过程			int left = 0;			int right = i - 1;			while (left <= right)			{
   				int mid = (left & right) + ((left ^ right) >> 1);				if (arr[mid] > tmp)				{
   					right = mid - 1;				}				else				{
   					left = mid + 1;				}			}			//这里一定要大于等于left，因为在上面left已经加1			for (int j = i - 1; j >= left; j--)			{
   				arr[j + 1] = arr[j];			}			arr[left] = tmp;		}	}

希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。

• 先将待排序序列分成若干个子序列（由相隔某个“增量”的元素组成的）
• 将每个子序列进行直接插入排序
• 将增量减1，再重复上述过程
• 最终直到增量为1停止
  
  代码如下：

void __InsertSort(int arr[], int size, int gap)	{
   		for (int g = 0; g < gap; g++)		{
   			for (int i = g + gap; i < size; i += gap)			{
   				int key = arr[i];				int j;				for (j = i - gap; j >= 0; j -= gap)				{
   					if (arr[j] > key)					{
   						arr[j + gap] = arr[j];					}					else					{
   						break;					}				}				arr[j + gap] = key;			}		}	}	void ShellSort(int arr[], int size)	{
   		int gap = size;		while (1)		{
   			gap = gap / 3 + 1;			__InsertSort(arr, size, gap);			if (gap == 1)			{
   				break;			}		}	}

上述中gap = size / 3 + 1这是经过大量实验推算出来的，第一步的增量取这个值会更合理

void __InsertSort(int arr[], int size, int gap)	{
   		int j, key;		for (int i = gap; i < size; i++)		{
   			key = arr[i];			for (j = i - gap; j >= 0; j -= gap)			{
   				if (arr[j] > key)				{
   					arr[j + gap] = arr[j];				}				else				{
   					break;				}			}			arr[j + gap] = key;		}	}	void ShellSort(int arr[], int size)	{
   		int gap = size;		while (1)		{
   			gap = gap / 3 + 1;			__InsertSort(arr, size, gap);			if (gap == 1)			{
   				break;			}		}	}

直接插入排序可以看做是增量为1的希尔排序

转载地址：http://adwdb.baihongyu.com/