【数据结构与算法】：直接插入排序和希尔排序

1. 排序的概念及其意义

1.1 排序的概念

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

1.2 排序的稳定性

• 假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
• 在排序算法中，稳定性是一个十分重要的评判标准。它在我们生活中的某些方面有着作用，比如一个有时间限制的竞赛项目，当两人分数相同时，先提交的选手的排名要比后提交的选手的排名高。这就必须使用具有稳定的排序了。

1.3 常见的排序算法

常见的排序有冒泡排序，插入排序，希尔排序，选择排序，堆排序，快速排序，归并排序，计数排序等，其中我们最常用的是快速排序。

插入排序

基本思想：

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

实际中我们玩扑克牌时，就用了插入排序的思想

2. 直接插入排序

基本思路：

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

如下图所示：
假设我们要排升序5 2 4 6 1 3

1. 把首元素5看成是有序的，我们用tmp保存下一个元素，即tmp = 2，再让tmp与前面已经有序的数据进行比较，此时tmp < 5，所以把5后挪，把tmp插入到5的前面，保持有序；
2. 接着再让tmp保存第三个元素，即tmp = 4，再让tmp与前面已经有序的数据进行比较，此时tmp < 5但是tmp > 2，所以把5后挪，把tmp插入到5的前面，2的位置不动，保持有序；
3. ……重复上述上述步骤，以此类推……

• 先考虑单趟排序的实现，代码如下：

int end ;
int tmp = arr[end + 1];//保存下一个值

while (end >= 0)
{
	if (tmp < arr[end])
	{
		arr[end + 1] = arr[end];//把前面的数按顺序往后挪
		end--;
	}
	else
	{
		break; //比前一个数要大时，说明找到了位置
	}
}

arr[end+1] = tmp;//包含了两种情况：1是在比较的过程中比前一个数要大，就把tmp放进去
                     //2是把前面的数都比完了，此时end==-1了，就把tmp放到最前面

这里的跳出循环包括两种情况：

1. 在tmp与前面的有序数据比较的过程中，tmp的值比最后一个有序数据大，进入了else语句，break直接跳出循环。例如上图中的第3次排序过程。
2. tmp比前面的有序数据都要小，一直end–，直到end < 0时，不满足循环条件，跳出循环。例如上图中的第4次排序过程。

而把arr[end+1] = tmp放在循环外面也是由于这两种情况，无论是第1种情况还是第2种情况，在循环结束后都要把待排序的元素放到指定是位置上。所以抽离这条语句放在循环外。

• 再考虑排序的整体过程，代码实现如下：

i是控制已经有序的数据的最后一个数据，是一个边界。

void InsertSort(int* arr, int sz)
{
	for (int i = 0; i < sz - 1; i++)
	{
		int end = i;
		int tmp = arr[end + 1];//保存下一个值

		while (end >= 0)
		{
			if (tmp < arr[end])
			{
				arr[end + 1] = arr[end];//把前面的数按顺序往后挪
				end--;
			}
			else
			{
				break; //比前一个数要大时，说明找到了位置
			}
		}
		arr[end+1] = tmp;
	}
}

void PrintArray(int* arr, int sz)
{
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

int main()
{
	int arr[] = { 6,7,9,2,4,3,5,1,0,8,-1};
	int sz = sizeof(arr) / sizeof(int);

     InsertSort(arr, sz);
     PrintArray(arr, sz);
     
     return 0;
}

排序结果为：

2.2 时间复杂度的分析

1. 最好：当待排序的元素为顺序时，时间复杂度0(N)。
2. 最坏：当待排序的元素为逆序时，时间复杂度0(N*N)。

所以，直接插入排序的时间复杂度是0(N*N)。

2.3 排序的稳定性分析

• 在上述代码排序过程中，当遇到两个相同数据时，会进入else语句，直接跳出循环，不会发生位置的挪动，即两个相同数据的相对位置依旧保持不变，所以直接插入排序是稳定的。

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

希尔排序是一种基于插入排序的改进算法。通过引入间隔的概念来改进插入排序的性能。

3.1 基本思想：

通过设置间隔，而对于每个间隔上的元素再进行插入排序，一趟排序后，间隔变小，再继续对此次间隔上的元素进行插入排序，直到间隔为1，此时就是一次完整的直接插入排序。

• 下面的排序代码与图解都是降序。

希尔排序分为两个步骤：

1. 预排序
   预排序是让数组接近有序，需要通过分组来排，间隔为gap的是一组。 间隔为3时的一组预排序图解：
   
   所以要进行多组间隔为gap的预排序，gap由大变小。

2. 直接插入排序
   当gap = 1时，就是一次直接插入排序。

3.2 对预排序的代码实现：

• 首先考虑间隔gap = 3时的单趟排序：

int gap = 3;
int end ;
int tmp = arr[end + gap];

while (end >= 0)
{
	if (tmp < arr[end + gap])
	{
		arr[end + gap] = arr[end];
		end -= gap;
	}
	else
	{
		break;
	}
}
arr[end + gap] = tmp;

这里跳出循环的情况与上文的直接插入排序的两种情况一模一样。

图解如下：

• 然后把间隔为gap = 3的多组数据同时排：

int gap = 3;
for (int i = 0; i < sz - gap; i++)
{
	int end = i;
	int tmp = arr[end + gap];

	while (end >= 0)
	{
		if (tmp > arr[end])
		{
			arr[end + gap] = arr[end];
			end -= gap;
		}
		else
		{
			break;
		}
	}
	arr[end + gap] = tmp;
}

部分图解如下：
每趟都是间隔为3的元素之间的一次直接插入排序。其中 i 控制end的走法，end和gap控制每次排序的走法。

• 接下来考虑如何取gap的值，就是如何让gap的值由大变小：
  gap越大，小的数可以越快到后面，大的数可以越快到前面，同时，gap越大，相对于gap越小而言预排完后越不接近有序。

void ShellSort(int* arr, int sz)
{
	int gap = sz;
	while (gap > 1)
	{
		gap = gap / 2;         // O（log2N)
		//gap = gap / 3 + 1;   // O（log3N)

		//对多组间隔为gap的数据同时排序
		for (int i = 0; i < sz - gap; i++)
		{
			int end = i;
			int tmp = arr[end + gap];

			while (end >= 0)
			{
				if (tmp > arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;
		}
	}
	
}

gap的取值有两种形式，首先它与数组元素个数挂钩，让gap = sz，

1. gap = gap / 2 ；当满足gap > 1时，任何数除2最后结果都是1，对应了gap = 1时就是直接插入排序。
2. gap = gap / 3 + 1；当满足gap > 1时，为了使最后 gap= 1，所以要+1。

排序结果为：

3.3 时间复杂度分析：
希尔排序的时间复杂度与数组元素的个数和和gap的取值有关。假设元素个数为N个。
当gap很大时，下面两层循环预排序接近O（N）
当gap很小时，数组已经很接近有序了，差不多也是O（N）

当gap = gap / 2时，第一个循环大致执行log2N次(以2为底N的对数）
当gap = gap / 3 + 1时，第一个循环大致执行log3N次(以3为底N的对数）

所以希尔排序的时间复杂度是O(N * log2N)或是O(N * log3N)。

3.4 稳定性分析：

不稳定，考虑序列（2，2，1），排序后序列为（1，2，2），我们发现2的相对位置发生了变化(粗体2与非粗体2)，所以是不稳定的排序算法。

4. 两种排序的性能对比

clock() 函数是 <time.h> 头文件中的一个函数，用来返回程序启动到函数调用时之间的CPU时钟周期数。这个值通常用来帮助衡量程序或程序的某个部分的性能

我们可以用这个函数进一步对比两种排序占用的CPU时间

代码实现为：

void TestOP()
{
	    srand(time(0));
		const int N = 100000;
		int* a1 = (int*)malloc(sizeof(int) * N);
		int* a2 = (int*)malloc(sizeof(int) * N);
		
	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
		a2[i] = a1[i];
	}
	
	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();
	
	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();
	
	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
	
	free(a1);
	free(a2);
}

这里让随机生成十万个随机数，分别用希尔排序和直接插入排序来进行排序，测试两种算法的执行时间：

通过上面的执行时间的对比，可以发现希尔排序的效率远远快于插入排序。