八大排序之插入排序（直接插入排序 & 希尔排序）

插入排序

插入排序（英语：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)
空间复杂度：O(1)
直接插入排序是稳定的
数组越有序，直接插入排序越快

二分插入排序

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

	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的希尔排序

---