排序的基本概念

排序操作十分常见，比如生活中的考试成绩榜、电影演出表等，都离不开排序。那么排序的目的是什么呢？排序可以使信息更加直观明了，更便于查找。

1. 排序：排序是将杂乱无章的数据元素通过一定的方法按关键字顺序排列的过程叫做排序。
2. 排序的稳定性：若在待排序的序列中，有两个或两个关键字以上相等的记录，对这个序列进行排序后，这个记录的先后次序发生变化，则所用的排序方法是不稳定的；若它们的先后次序仍不变，则称所用的排序方法是稳定的。需要注意的是，在所有的待排序记录中，只要有一组关键字的实例不满足稳定性，则该排序方法就是不稳定的。
3. 内部与外部排序：根据记录所占用的存储设备的不同，可将排序将排序分为两大类：一类是内部排序，待排序记录全部存放在计算机内存中进行排序；另一类是外部排序，内存一次不能容纳全部记录，在排序过程中需对外存进行访问的排序。
4. 排序算法效率的评价指标：
   排序的时间主要消耗在关键字之间的比较和记录的移动上，于是排序算法的时间复杂度由着两个指标决定。排序的空间复杂度由排序算法所需的辅助空间决定，辅助空间是除了存放待排序记录占用的空间之外，指向算法所需要的其它存储空间。
5. 待排序记录的数据类型定义：

#define MAXSIZE 20

typedef struct					//顺序表
{
	int r[MAXSIZE+1];
	int length;
}SqList;
1
2
3
4
5
6
7

插入排序

插入排序的基本思想是：每一趟将一个待排序的记录，按其关键字的大小插入到已经排好的一组记录上，直到所有待排序记录全部插入为止。

直接插入排序

直接插入排序是一种最简单的排序方法其基本操作是将一条记录插入到排好序的有序表中，从而得到一个新的、记录数量增1的有序表。

算法分析：
该算法其实十分简单，我们从一个序列中选择一个记录，然后将它与其余记录比较，若小于这个记录，就把其余记录插入到它前面；若大于，就插入到它的后面。需要注意的是，我们一般都选取序列中的第一个元素作为排序的第一个元素。依次将后面的元素与它比较，若后一个记录的关键字大于前一个，则排在前一个记录后面即可，若小于前一个，则需将后一个记录与前一个记录前面的所有记录比较，找到合适的位置插入，在插入前，还需将要插入位置的记录及该记录到“前一个”记录（不包括“前一个”记录）之间的所有元素向后移一位。
这里的“前一个”和“后一个”指的是紧挨着的两个记录。下面的部分比较好理解一些。

具体代码：

void InsertSort(SqList *L)
{
	int i,j;
	for(i=2;i<=L->length;i++)
		//假定r[i]为后一个元素，r[i-1]为前一个元素
		if(L->r[i]<L->r[i-1])		
		{
			L->r[0]=L->r[i];			//保存r[i]元素的“副本”
			L->r[i]=L->r[i-1];			//因为r[i-1]大于r[i]，先用r[i-1]去占用r[i]的位置，这就是为什么要保存r[i]的副本
			//r[i]虽然小于r[i-1]，但r[i-1]的前面说不定还有记录，所以需要确定插入的位置
			for(j=i-2;L->r[0]<L->r[j];j--)
				L->r[j+1]=L->r[j];
			L->r[j+1]=L->r[0];	
		}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

我在学习的过程中，对第二个for循环那里思考了很久。为什么$j=i-2?$ 因为我们要在$r[i-1]$前面的记录中去找一个合适的位置，而$r[i-2]$就表示$r[i-1]$的前一个记录，然后$j--$去找。若$r[0]$（也就是$r[i]$）比$r[j]$（也就是$r[i-2]）$小，这时，就需要将$r[j]$在内到$r[i-1]$（不包括$r[i-1]$）的所有记录向后移一位。注意，并不是$r[j]$后面的全部记录都要后移，后移只是针对已排好的序列。 直接插入排序过程如下图：
其中红色表示已排好的序列，绿色表示保存的副本。

直接插入排序法的时间复杂度为$O(n^2)$。空间复杂度为$O(1)$，因为只需要一个辅助空间$r[0]$。

折半插入排序

直接插入排序采用顺序查找法查找当前已排好的序列中的插入位置，由此，我们也可以用折半查找法查找当前已排好的序列中的插入位置。

算法分析：
该算法也很简单，也是先在已排好的序列中找出插入位置，然后在这个序列中将插入位置后面的记录后移即可。

具体代码：

void BInsertSort(SqList *L)
{
	int i,j,m;
	for(i=2;i<=L->length;i++)
	{
		L->r[0]=L->r[i];			//先保存待插入记录的副本
		low=1;
		high=i-1;					//high=i-1是因为要在已排好的序列中寻找插入位置，而r[i]是待插入记录
		while(low<=high)
		{
			m=(low+high)/2;
			if(L->r[0]<L->r[m])
				high=m-1;
			else
				low=m+1;			//思考：为什么两者相等时，是low=m+1
		}
		//位置查找结束，为high+1，可根据上面的循环推出
		//开始后移
		for(j=i-1;j>=high+1;j--)
			L->r[j+1]=L->r[j];
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

照样，红色数字为已排好的序列，绿色数字为保存的副本。

在平均情况下，这般插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。其时间复杂度仍为$O(n^2)$，空间复杂度仍为$O(1)$。

希尔排序

希尔排序（Shell’s Sort）又称缩小增量排序（Diminishing Increment Sort）。

直接插入排序，当待排序的记录个数较少且待排序序列的关键字基本有序时，效率较高。希尔排序基于以上两点，从“减少记录个数”和“序列基本有序”两个方面对直接插入排序进行了改进。

算法分析：

希尔算法的实质就是类似于分组插入。不过这个分组不同于一般的分组，它是将相隔某个增量的记录分成一组，而这个增量呢可以有很多个，但最后一个增量必定是1，因为这时就满足了基本有序，这个1就是再对全体记录进行一次直接插入排序，例如有下面一个序列：

我们取增量（5，3，1），首先是第一趟，r[1]、r[6]，r[2]、r[7]，r[3]、r[8]，r[4]、r[9]，r[5]、r[10] 一共5个组，它们位置之间的差都为5，在每组里进行直接插入排序，排成一个有序的序列。例如，若r[1]>r[6]，这时就交换它们两个的位置，不影响其它记录。

第二趟增量为3，r[1]、r[4]、r[7]、r[10]，r[2]、r[5]、r[8]，r[3]、r[6]、r[9] 一共3个组，它们位置之间的差都为3，在每组里进行直接插入排序，将每组排成一个有序的序列。

最后在进行第三趟排序…

具体代码：

void ShellInsert(SqList *L,int dk)				//dk为一个增量
{
	for(i=dk+1;i<=L->length;i++)				//直接插入
	{
		if(L->r[i] < L->r[i-dk])
		{
			L->r[0]=L->r[i];
			for(j=i-dk;j>0 && L->r[0] < L->r[j];j-=dk)
				L->r[j+dk]=L->r[j];
		}
	}
}

void ShellSort(SqList *L,int dt[],int t)		//t为趟数，数组dt[]存储每趟的增量
{
	for(int k=0;k<t;k++)
		ShellInsert(L,dt[k]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

在学习的过程中只有一个地方让我思考了一下，就是第一个$for$循环，$i$的初始条件为$i=dk+1$，然后每次循环结束都执行$i++$，最开始我在想这样的话它不是最多就只能针对一组 的两个记录吗。其实每次$i$自加1，加着加着就到了该组中的下一个记录$dk+1+dk$。

希尔排序的时间复杂度涉及一些数学上尚未解决的问题，这里不做讨论。它的空间复杂度还是$O(1)$。

总结

插入排序有三种：直接插入排序、折半插入排序和希尔排序。其实这三种排序，记录插入的方法都是一样的。直接插入和折半插入排序就是在查找插入位置的算法不同，直接插入排序比较稳定、算法更简单、也适用于链式存储结构，但它只适用于$n$较小的序列。折半插入排序也是比较稳定的，能适用于$n$较大的情况，但是它只能用于顺序存储结构。而希尔排序，相当于是对直接插入排序的改进，$n$越大效果越明显，但它的跳跃式移动记录导致其排序方法不稳定，且也只能用于顺序结构，不能用于链式结构。