直接插入法是最简单的排序法，其排序思想如下：
打牌时，每抓一张牌就将其放到对应的顺序位置。
下面是待排记录的类型定义：

1
2
3
4
5
6
7
8
9
10
#define MAXSIZE 200
typedef int KeyType//关键字类型
typedef struct{
KeyType key;//关键字
InfoType otherinfo;//其他数据项
}RedType;//记录类型
typededf struct{
RedType r[MAXSIZE+1];//r[0]闲置或作为哨兵
int length;//顺序表长度
}SqList;

上述的RedType结构体类型实际上是没必要定义的，实际做题时可以写成如下代码，更方便一点：

1
2
3
4
5
6
#define MAXSIZE 200
typedef int KeyType//关键字类型
typededf struct{
KeyType r[MAXSIZE+1];//r[0]闲置或作为哨兵
int length;//顺序表长度
}SqList;

直接插入排序算法的描述：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void InsertSort(SqList &L)
{
//对顺序表L做直接插入排序
	for(i=2;i<=L.length;i++)
	{
		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]后移
			//记录逐个后移，直到找到插入位置
			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];
		
		}
	}	
}

常见错误^by小胡^：
1）低位输出随机数。（记录逐个后移，找到插入位置）三行代码的位置放在了if语句外，导致即便低位符合降序，但仍执行代码，致溢出。

直接插入排序算法分析：

  • 最好的情况是记录序列按关键字有序
  • 比较次数n-1；移动次数0
  • 最坏的情况是记录序列按关键字逆序
  • 比较次数(n+2)(n-1)/2；移动次数(n+4)(n-1)/2
  • 平均情况下比较次数和移动次数约为n^2^/4,时间复杂度为O(N^2^)
  • 直接插入排序容易实现，是稳定排序
  • 直接插入排序也适用于链式结构，不需要移动
  • 适用于初始基本有序的情况

希尔排序法是直接插入法的优化，它的思想是先将整个排序序列分成若干子序列，并分别进行直接插入排序，当整个记录中的序列基本有序时，再对全体记录进行一次直接插入排序。

希尔排序法的描述：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void ShellInsert(SqList& L, int dk)
{//对顺序表 L 做一趟增量是 dk 的希尔插入排序
	int i, j;
	for (i = dk + 1; i <= L.length; ++i)
	{
		if (L.r[i] < L.r[i - dk]) {
			//需将 L.r[i] 插入有序增量子表
			L.r[0] = L.r[i]; //暂存在L.r[0]
			for (j = i - dk; j > 0 && L.r[0] < L.r[j]; j -= dk)
				L.r[j + dk] = L.r[j];//记录后移
			L.r[j + dk] = L.r[0];//将 r[0] 插入
		}//if
	}//for
}//ShellInsert
void ShellSort(SqList& L, int dt[], int t)
{//按增量序列 dt[0..t-1] 对顺序表 L 作 t 趟希尔排序
	int k;
	for (k = 0; k < t; ++k)
		ShellInsert(L, dt[k]);
}

希尔排序法算法分析：

  • 时间复杂度取决于增量序列，可到 O(N ^4/3^ )，优于直接插入排序
  • 如何选择最佳 d序列，目前尚未解决，但增量系列应该无公因子，最后一个增量值必须为 1
  • 空间复杂度为 O(1)
  • 记录跳跃移动导致排序方法不稳定
  • 只能用于顺序结构，不能用于链式结构

利用希尔排序解决如下问题：
输入
输入的第一行包含1个正整数n，表示共有n个整数需要参与排序。其中n不超过1000。
第二行包含n个用空格隔开的正整数，表示n个需要排序的整数.
输出
只有1行，包含n个整数，表示从小到大排序完毕的所有整数。
请在每个整数后输出一个空格，并请注意行尾输出换行。
样例输入
10
2 8 4 6 1 10 7 3 5 9
样例输出
1 2 3 4 5 6 7 8 9 10

下面是源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
using namespace std;
#define KeyType int
#define MAXSIZE 1000
typedef struct {
	KeyType r[MAXSIZE+1];
	int length;
}SqList;
void ShellInsert(SqList& L, int dk)
{//对顺序表 L 做一趟增量是 dk 的希尔插入排序
	int i, j;
	for (i = dk + 1; i <= L.length; ++i)
	{
		if (L.r[i] < L.r[i - dk]) {
			//需将 L.r[i] 插入有序增量子表
			L.r[0] = L.r[i]; //暂存在L.r[0]
			for (j = i - dk; j > 0 && L.r[0] < L.r[j]; j -= dk)
				L.r[j + dk] = L.r[j];//记录后移
			L.r[j + dk] = L.r[0];//将 r[0] 插入
		}//if
	}//for
}//ShellInsert
void ShellSort(SqList& L, int dt[], int t)
{//按增量序列 dt[0..t-1] 对顺序表 L 作 t 趟希尔排序
	int k;
	for (k = 0; k < t; ++k)
		ShellInsert(L, dt[k]);
}
int main()
{
	int n;
	cin >> n;
	SqList L;
	int dlta[1000];
	L.length = n;
	for (int i = 1; i <= n; i++)
	{
		cin >> L.r[i];
		dlta[i - 1] = n-i;
	}
	ShellSort(L,dlta,n);
	for (int i = 1; i <= n; i++)
		cout << L.r[i] << " ";
	cout << endl;
	return 0;
}

冒泡排序排序法，相邻元素之间进行比较，如果逆序则交换位置。

冒泡排序法的描述：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 void BubbleSort(SqList &L)
 {//对顺序表L做冒泡排序
 	m = L.length − 1;
 	flag = 1;//用来标记某一趟排序是否发生交换
 	while((m > 0) && (flag == 1)) {
 		flag = 0; //没有发生交换
 		for(j = 1; j <= m; j++)
 			if(L.r[j].key > L.r[j + 1].key) {
 				flag = 1;//表示本趟排序发生了交换
 				t = L.r[j];
 				L.r[j] = L.r[j + 1];
 				L.r[j + 1] = t;//交换前后两个记录
 			}//if
 		−−m;
 	}//while
}//BubbleSort

实际上此冒泡排序是对原冒泡排序的一种优化，flag标识符实现了优化。
例如：1 2 5 3 7 8 9 10
原冒泡排序要比较7趟，而此冒泡排序只需比较3趟。

下面贴上原冒泡排序算法描述：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void BubbleSort(SqList &L)
{
    int i, j，temp;
    int m=L.length-1;
    while(m>0)
        for (j = 1; j <= m; j++)
        	if (L.r[j] > L.r[j + 1])
        	{
            	temp = L.r[j];
            	L.r[j] = L.r[j + 1];
            	L.r[j + 1] = temp;
        	}
        --m;
}

冒泡排序算法分析:

  • 最好情况下初始有序，只需一趟排序，比较次数为n-1，不需要移动记录
  • 最坏情况是初始逆序，需 n-1 趟排序
  • 比较的次数：n(n-1)/2;移动的次数：3n(n-1)/2
  • 平均时间复杂度为 O(n 2 )
  • 辅助空间复杂度为 O(1)
  • 是一种稳定的排序方法，可用于链式存储结构

快速排序法是最常用的一种排序方法，同时也是很典型的分治思想，分而治之。它的排序思路如下：

1.任取一个记录作为枢轴
2.划分：所有比枢轴小的记录一律前放，比枢轴大的记录一律后放，形成左右两个子表
3.对子表重新进行前两步操作，直到每个子表元素只剩一个

快速排序法算法描述：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int Partition(SqList &L,int low,int high)
{//对表 r[low..high] 进行一趟排序，返回枢轴位置
	L.r[0]=L.r[low]; //子表的第一个记录做枢轴
	pivotkey=L.r[low];
	while(low<high){//从表两端交替向中间扫描
		while(low<high&&L.r[high]>=pivotkey)
			−−high;
	L.r[low]=L.r[high];//比枢轴小的移到低端
 	while(low<high&&L.r[low]<=pivotkey)
 		++low;
 	L.r[high]=L.r[low];//比枢轴大的移到高端
 }//while
 	L.r[low]=L.r[0]; //枢轴记录到位
 	return low; //返回枢轴位置
}//Partition
 void QSort(SqList &L, int low, int high)
 { //对顺序表 L 中的子序列 L.r[low..high] 做快速排序
 	if(low < high) { //长度大于1
 		pivotloc = Partition(L, low, high);
 		QSort(L, low, pivotloc − 1);//左子表排序
 		QSort(L, pivotloc + 1, high);//右子表排序
 	}//if
 }//QSort
 void QuickSort(SqList &L)
 { //对顺序表L做快速排序
 	QSort(L, 1, L.length);
 }//QuickSort

快速排序算法分析：

  • 性能最好情况是均匀划分，时间复杂度是 O(nlog 2 n)。
  • 性能最差情况如初始序列有序，导致最不均匀划分，性能退至O(n ^2^)。
  • 为避免最坏情况发生，可以三者取中，即头、尾和中间记录三者中关键字居中的记录作为枢轴
  • 可以证明，平均计算时间是 O(nlog n)。
  • 实验结果表明：就平均计算时间而言，快速排序是所有内部排序方法中最好的一个。
  • 辅助空间复杂度取决于栈的层次，最坏 O(n), 最好O(log 2 n)。
  • 快速排序不稳定，不适用于链表结构。