常见排序算法——插入排序（直接插入排序 & 希尔排序）

目录

直接插入排序

基本思想

代码实现

时间复杂度计算 

特性总结

 希尔排序（缩小增量排序） 

基本思想

代码实现

时间复杂度计算

特性总结

直接插入排序

基本思想

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。具体如下图所示：

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与 array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移。

代码实现

// 插入排序		
void InsertSort(int* arr, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		//end表示已经排好序的尾标
		int end = i;
		//保存要排序的数，一会就会被覆盖
		int tmp = arr[end + 1];
		//注意end可以等于0  （tmp比前面所有数字都要小）
		//while (end >= 0 && arr[end] < tmp)//降序
		while (end >= 0 && arr[end] > tmp)  //升序
		{
			//语句顺序不能乱	先交换再--
			arr[end + 1] = arr[end];
			end--;
		}
		arr[end + 1] = tmp;
	}
}

时间复杂度计算 

特性总结

1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定       （遍历数组不会改变相同元素的相对顺序） 

 希尔排序（缩小增量排序） 

基本思想

先选定一个整数，把待排序文件中所有记录分成多个组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后，减小gap，重复上述分组和排序的工作。当到达gap=1时，所有记录在统一组内排好序。

 可以理解为希尔排序是对插入排序的优化，这样做能让大的数更快到达后面，小的数更快到达前面，完成排序。

当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就 会很快。这样整体而言，可以达到优化的效果。

代码实现

// 希尔排序
void ShellSort(int* arr, int n)
{
	int gap = n;
	while (gap > 1)
	{
		//只有gap最后为1，才能保证最后有序，所以这里要加1
		gap = gap / 3 + 1;
		//下面类似直接插入排序  区别在于将1换成gap
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				//if(arr[end] < tmp)//降序
				if (arr[end] > tmp)//升序
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
					break;
			}
			arr[end + gap] = tmp;
		}
	}
}

时间复杂度计算

希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好多书中给出的希尔排序的时间复杂度都不固定：

《数据结构(C语言版)》--- 严蔚敏

 《数据结构-用面相对象方法与C++描述》--- 殷人昆

因为我们的gap是按照Knuth提出的方式取值的，而且Knuth进行了大量的试验统计，我们暂时就按照：O(N ^ 1.25)到O(1.6 * N ^ 1.25)来算。 

特性总结

1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序；当gap == 1时，数组已经接近有序的了。
3. 时间复杂度：O(N ^ 1.25)~O(1.6 * N ^ 1.25)
4. 空间复杂度：O(1)
5. 稳定性：不稳定       （不能保证原来所具有的相对次序）

不能保证具有相同排序码的记录原来所具有的相对次序，即原来排在前面的，经过排序后有可能排某个具有相同码的记录的后面，例如排序码43，89，21，43，28，15，经过5遍排序后次序为15，21，28，43，43，89。排序前第一个位置上的排序码43现在位于第5个位置。