⑤ 程序：
1.void InsSort（RecordType r[], int length）
2.{
3. for（i = 2; I <= length; i++）
4. {
5. r[0] = r[i];
6. j = i – 1;
7. while（r[0].key < r[j].key）
8. {
9. r[j + 1] = r[j]; j = j – 1;
10. }
11. r[j+1] = r[0];
12. }
13.}
2、 折半插入排序：
① 思想：
因为是已经确定了前部分是有序序列，所以在查找插入位置的时候可以用折半查找的方法进行查找，提高效率。
② 时间复杂度：
比较时的时间减为O（n㏒n），但是移动元素的时间耗费未变，所以总是得时间复杂度还是O（n²）。
③ 空间复杂度：
S（n）=O
（1）。
④ 稳定性：
稳定排序。
⑤ 程序：
1.void BinSort（RecordType r[], int length）
2.{
3. for（i = 2; i <= length; i++）
4. {
5. x = r[i];
6. low = 1; high = i – 1;
7. while（low <= high）
8. {
9. mid = （low + high） / 2;
10. if（x.key < r[mid].key）
11. high = mid – 1;
12. else
13. low = mid – 1;
14. }
15. for（j = i – 1; j >= low; --j）
16. r[j + 1] = r[j];
17. r[low] = x;
18. }
19.}
3、 希尔排序：
① 思想：
又称缩小增量排序法。
把待排序序列分成若干较小的子序列，然后逐个使用直接插入排序法排序，最后再对一个较为有序的序列进行一次排序，主要是为了减少移动的次数，提高效率。
原理应该就是从无序到渐渐有序，要比直接从无序到有序移动的次数会少一些。
② 时间复杂度：
O（n的1.5次方）
③ 空间复杂度：
O
（1）
④ 稳定性：
不稳定排序。
{2,4,1,2}，2和1一组4和2一组，进行希尔排序，第一个2和最后一个2会发生位置上的变化。
⑤ 程序：
1.void ShellInsert（RecordType r[], int length, int delta）
2.{
3. for（i = 1 + delta; i <= length; i++）/*1+delta为第一个子序列的第二个元素的下表*/
4. if（r[i].key < r[1 - delta].key）
5. {
6. r[0] = r[i];
7. for（j = i – delta; j > 0 && r[0].key < r[j].key; j -=delta）
8. r[j + delta] = r[j];
9. r[j + delta] = r[0];
10. }
11.}
12.void ShellSort（RecordType r[], int length, int delta[], int n）
13.{
14. for（i = 0; i <= n – 1; ++i）
15. ShellInsert（r, length, delta[i]）;
16.}
三、交换类排序：
（一） 思想：
通过交换逆序元素进行排序的方法。
（二） 分类：
1、 冒泡排序：
① 思想：
反复扫描待排序序列，在扫描的过程中顺次比较相邻的两个元素的大小，若逆序就交换位置。
第一趟，从第一个数据开始，比较相邻的两个数据，（以升序为例）如果大就交换，得到一个最大数据在末尾；然后进行第二趟，只扫描前n-1个元素，得到次大的放在倒数第二位。
以此类推，最后得到升序序列。
如果在扫描过程中，发现没有交换，说明已经排好序列，直接终止扫描。
所以最多进行n-1趟扫描。
② 时间复杂度：
T（n）=O（n²）。
③ 空间复杂度：
S（n）=O
（1）。
④ 稳定性：
稳定排序。
⑤ 程序：
1.void BubbleSort（RecordType r[], int length）
2.{
3. n = length;
4. change = TRUE;
5. for（i = 1; i <= n – 1 && change; i++）
6. {
7. change = FALSE;
8. for（j = 1; j <= n – I; ++j）
9. if（r[j].key > r[j + 1].key）
10. {
11. x = r[j];
12. r[j] = r[j + 1];
13. r[j + 1] = x;
14. change = TRUE;
15. }
16. }
17.}
2、 快速排序：
① 思想：
冒泡排序一次只能消除一个逆序，为了能一次消除多个逆序，采用快速排序。
以一个关键字为轴，从左从右依次与其进行对比，然后交换，第一趟结束后，可以把序列分为两个子序列，然后再分段进行快速排序，达到高效。
② 时间复杂度：
平均T（n）=O（n㏒n），最坏O（n²）。
③ 空间复杂度：
S（n）=O（㏒n）。
④ 稳定性：
不稳定排序。
{3，2，2}
⑤ 程序：
1.void QKSort（RecordType r[], int low, int high）
2.{
3. int pos;
4. if（low < high）
5. {
6. pos = QKPass（r, low, high）;
7. QKSort（r, low, pos - 1）;
8. QKSort（r, pos + 1, high）;
9. }
10.}
11.int QKPass（RecordType r[], int left, int right）
12.{
13. RecordType x;
14. int low, high;
15. x = r[left];
16. low = left;
17. high = right;
18. while（low < high）
19. {
20. while（low < high && r[high].key >= x.key）
21. high--;
22. if（low < high）
23. {
24. r[low] = r[high];
25. low++;
26. }
27. while（low < high && r[low].key < x.key）
28. low++;
29. if（low < high）
30. {
31. r[high] = r[low];
32. high--;
33. }
34. }
35. r[low] = x;
36. return low;
37.}
四、选择类排序：
（一） 思想：
每一趟在n–i+1（i=1,2,…,n-1）个记录中选取关键字最小的记录作为有序序列中的第i个记录。
（二） 分类：
1、 简单选择排序：
① 思想：
第一趟时，从第一个记录开始，通过n–1次关键字的比较，从n个记录中选出关键字最小的记录，并和第一个记录进行交换。
第二趟从第二个记录开始，选择最小的和第二个记录交换。
以此类推，直至全部排序完毕。
② 时间复杂度：
T（n）=O（n²）。
③ 空间复杂度：
S（n）=O
（1）。
④ 稳定性：
不稳定排序，{3，3，2}。
⑤ 程序：
1.void SelectSort（RecordType r[], int length）
2.{
3. n = length;
4. for（i = 1; i <= n - 1; i++）
5. {
6. k = i;
7. for（j = i + 1; j <= n; i++）
8. if（r[j].key < r[k],key）
9. k = j;
10. if（k !
= i）
11. {
12. x = r[i];
13. r[i] = r[k];
14. r[k] = x;
15. }
16. }
17.}
2、 树形选择排序：
① 思想：
为了减少比较次数，两两进行比较，得出的较小的值再两两比较，直至得出最小的输出，然后在原来位置上置为∞，再进行比较。
直至所有都输出。
② 时间复杂度：
T（n）=O（n㏒n）。
③ 空间复杂度：
较简单选择排序，增加了n-1个额外的存储空间存放中间比较结果，就是树形结构的所有根节点。
S（n）=O（n）。
④ 稳定性：
稳定排序。
⑤ 程序：
3、 堆排序：
① 思想：
把待排序记录的关键字存放在数组r[1…n]中，将r看成是一刻完全二叉树的顺序表示，每个节点表示一个记录，第一个记录r[1]作为二叉树的根，一下个记录r[2…n]依次逐层从左到右顺序排列，任意节点r[i]的左孩子是r[2i]，右孩子是r[2i+1]，双亲是r[i/2向下取整]。
然后对这棵完全二叉树进行调整建堆。
② 时间复杂度：
T（n）=O（n㏒n）。
③ 空间复杂度：
S（n）=O
（1）。
④ 稳定性：
不稳定排序。
{5，5，3}
⑤ 程序：
（1） 调整堆：
1.void sift（RecordType r[], int k, int m）
2.{
3. /*假设r[k...m]是以r[k]为根的完全二叉树，而且分别以r[2k]和r[2k+1]为根的左右子树为大根堆，调整r[k]，使整个序列r[k...m]满足堆的性质*/
4. t = r[k];/*暂存“根”记录r[k]*/
5. x = r[k].key;
6. i = k;
7. j = 2 * i;
8. finished = FALSE;
9. while（j <= m && !
finished）
10. {
11. if（j < m && r[j].key < r[j + 1].key）
12. j = j + 1;/*若存在右子树，且右子树根的关键字大，则沿右分支“筛选”*/
13. if（x >= r[j].key）
14. finished = TRUE;/*筛选完毕*/
15. else
16. {
17. r[i] = r[j];
18. i = j;
19. j = 2 * i;
20. }/*继续筛选*/
21. }
22. r[i] = t;/*将r[k]填入到恰当的位置*/
23.}
（2） 建初堆：
1.void crt_heap（recordType r[], int length）
2.{
3. n = length;
4. for（i = n / 2; i >= 1; --i）/*自第n/2向下取整 个记录开始进行筛选建堆*/
5. sift（r, i, n）;
6.}
（3） 堆排序：
1.void HeapSort（RecordType r[], int length）
2.{
3. crt_heap（r, length）;
4. n = length;
5. for（i = n; i >= 2; --i）
6. {
7. b = r[1];/*将堆顶记录和堆中的最后一个记录互换*/
8. r[1] = r[i];
9. r[i] = b;
10. sift（r, 1, i - 1）;/*进行调整，使r[1…i-1]变成堆*/
11. }
12.}
五、归并排序：
（一） 思想：
（二） 分类：
1、 归并排序：
① 思想：
假设初始序列右n个记录，首先将这n个记录看成n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2向上取整个长度为2（n为奇数时，最后一个序列的长度为1）的有序子序列。
在此基础上，在对长度为2的有序子序列进行两两归并，得到若干个长度为4的有序子序列。
如此重复，直至得到一个长度为n的有序序列为止。
② 时间复杂度：
T（n）=O（n㏒n）。
③ 空间复杂度：
S（n）=O（n）。
④ 稳定性：
稳定排序。
⑤ 程序：
1.void Merge（RecordType r1[], int low, int mid, int high, RecordType r2[]）
2.{
3. /*已知r1[low...mid]和r1[mid + 1...high]分别按关键字有序排列，将它们合并成一个有序序列，存放在r2[low...high]*/
4. i = low;
5. j = mid + 1;
6. k = low;
7. while（（i <= mid） && （j <= high））
8. {
9. if（r1[i].key <= r1[j].key）
10. {
11. r2[k] = r1[i];
12. ++i;
13. }
14. else
15. {
16. r2[k] = r1[j];
17. ++j;
18. }
19. ++k;
20. }
21. while（i <= mid）
22. {
23. r2[k] = r1[i];
24. k++;
25. i++;
26. }
27. while（j <= high）
28. {
29. r2[k] = r1[j];
30. k++;
31. j++;
32. }
33.}
34.void MSort（RecordType r1[], int low, int high, RecordType r3[]）
35.{
36. /*r1[low...high]经过排序后放在r3[low...high]中，r2[low...high]为辅助空间*/
37. RecordType r2[N];
38. if（low == high）
39. r3[low] = r1[low];
40. else
41. {
42. mid = （low + high） / 2;
43. MSort（r1, low, mid, r2）;
44. MSort（r1, mid + 1, high, r2）;
45. Merge（r2, low, mid, high, r3）;
46. }
47.}
48.void MergeSort（RecordType r[], int n）
49.{
50. /*对记录数组r[1...n]做归并排序*/
51. MSort（r, 1, n, r）;
52.}
六、分配类排序：
（一） 思想：
分配类排序是利用分配和收集两种基本操作。
（二） 分类：
1、 多关键字排序：
2、 链式基数排序：
① 思想：
先分配，再收集，就是先按照一个次关键字收集一下，然后进行收集（第一个排序），然后再换一个关键字把新序列分配一下，然后再收集起来，又完成一次排序，这样所有关键字分配收集完后，就完成了排序。
② 时间复杂度：
T（n）=O（d（n+rd））。
③ 空间复杂度：
S（n）=O（rd）。
④ 稳定性：
稳定排序。
⑤ 程序：
七、总结：
（1）简单排序法一般只用于n较小的情况（例如n<30）。
当序列的记录“基本有序”时，直接插入排序是最佳的排序方法。
如果记录中的数据较多，则应采用移动次数较少的简单选择排序法。
（2）快速排序、堆排序和归并排序的平均时间复杂度均为O（n㏒n），但实验结果表明，就平均时间性能而言，快速排序是所有排序方法中最好的。
遗憾的是，快速排序在最坏情况下的时间性能为O（n²）。
堆排序和归并排序的最坏时间复杂度仍为O（n㏒n），当n较大时，归并排序的时间性能优于堆排序，但它所需的辅助空间最多。
（3）可以将简单排序法与性能较好的排序方法结合使用。
例如，在快速排序中，当划分子区间的长度小于某值时，可以转而调用直接插入排序法；或者先将待排序序列划分成若干子序列，分别进行直接插入排序，然后再利用归并排序法，将有序子序列合并成一个完整的有序序列。
（4）基数排序的时间复杂度可以写成O（d·n）。
因此，它最适合于n值很大而关键字的位数d较小的序列。
当d远小于n时，其时间复杂度接近O（n）。
（5）从排序的稳定性上来看，在所有简单排序法中，简单选择排序是不稳定的，其他各种简单排序法都是稳定的。
然而，在那些时间性能较好的排序方法中，希尔排序、快速排序、堆排序都是不稳定的，只有归并排序、基数排序是稳定的。
文章二
数据结构中各种排序算法比较
1快速排序（QuickSort）
快速排序是一个就地排序，分而治之，大规模递归的算法。
从本质上来说，它是归并排序的就地版本。
快速排序可以由下面四步组成。
（1） 如果不多于1个数据，直接返回。
（2） 一般选择序列最左边的值作为支点数据。
（3） 将序列分成2部分，一部分都大于支点数据，另外一部分都小于支点数据。
（4） 对两边利用递归排序数列。
快速排序比大部分排序算法都要快。
尽管我们可以在某些特殊的情况下写出比快速排序快的算法，但是就通常情况而言，没有比它更快的了。
快速排序是递归的，对于内存非常有限的机器来说，它不是一个好的选择。
2归并排序（MergeSort）
归并排序先分解要排序的序列，从1分成2，2分成4，依次分解，当分解到只有1个一组的时候，就可以排序这些分组，然后依次合并回原来的序列中，这样就可以排序所有数据。
合并排序比堆排序稍微快一点，但是需要比堆排序多一倍的
升级会员 