前言

如果说各种编程语言是程序员的招式，那么数据结构和算法就相当于程序员的内功。

想写出精炼、优秀的代码，不通过不断的锤炼，是很难做到的。

八大排序算法

排序算法作为数据结构的重要部分，系统地学习一下是很有必要的。

排序的概念

排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。

排序分为内部排序和外部排序。

若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。

反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。

排序分类

八大排序算法均属于内部排序。如果按照策略来分类，大致可分为：交换排序、插入排序、选择排序、归并排序和基数排序。如下图所示：

算法分析

下表给出各种排序的基本性能，具体分析请参看各排序的详解：

课后习题

【2017年真题】在内部排序时，若选择了归并排序而没有选择插入排序，则可能的理由是（）
1.归并排序的程序代码更短
2.归并排序的占用空间更少
3.归并排序的运行效率更高
A.仅2        B.仅3        C.仅1、2        D.仅1、3

参考答案：B

【2017年真题】下列排序方法中，若将顺序存储更换为链式存储，则算法的时间效率会降低的是（）
1.插入排序    2.选择排序    3.起泡排序    4.希尔排序    5.堆排序
A.仅1、2    B.仅2、3    C.仅3、4    D.仅4、5

参考答案：D

【2015年真题】下列排序算法中，元素的移动次数与关键字的初始排列次序无关的是（）。
A．直接插入排序    B．起泡排序    C．基数排序    D．快速排序

参考答案：C

【2012年真题】在内部排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束都至少能够确定一个元素最终位置的方法是（）
Ⅰ．简单选择排序 
Ⅱ．希尔排序 
Ⅲ．快速排序 
Ⅳ．堆排序 
Ⅴ．二路归并排序 
A．仅Ⅰ、Ⅲ、Ⅳ 
B．仅Ⅰ、Ⅲ、Ⅴ 
C．仅Ⅱ、Ⅲ、Ⅳ 
D．仅Ⅲ、Ⅳ、Ⅴ 

参考答案：A
答案解析：考查各种内部排序算法的性质。 
对于Ⅰ，简单选择排序每次选择未排序列中的最小元素放入其最终位置。对于Ⅱ，希尔排序每次是对划分的子表进行排序，得到局部有序的结果，所以不能保证每一趟排序结束都能确定一个元素的最终位置。对于Ⅲ，快速排序每一趟排序结束后都将枢轴元素放到最终位置。对于Ⅳ，堆排序属于选择排序，每次都将大根堆的根结点与表尾结点交换，确定其最终位置。对于Ⅴ，二路归并排序每趟对子表进行两两归并从而得到若干个局部有序的结果，但无法确定最终位置。 

【2010年真题】对一组数据(2，12，16，88，5，10)进行排序，若前三趟排序结果如下： 
第一趟排序结果：2，12，16，5，10，88 
第二趟排序结果：2，12，5，10，16，88 
第三趟排序结果：2，5，10，12，16，88 
则采用的排序方法可能是（）。 
A．起泡排序 
B．希尔排序 
C．归并排序 
D．基数排序 

参考答案：A
答案解析：考查各种排序算法的过程。 
看第一趟可知仅有 88 被移到最后. 
如果是希尔排序，则 12，88，10 应变为 10，12，88。因此排除希尔排序。 
如果是归并排序，则应长度为 2 的子序列是有序的，由此可排除归并。 
如果是基数排序，则 16，5，10 应变为 10，5，16，由此排除基数。 
可以看到，每一趟都有一个元素移到其最终位置，符合冒泡排序特点。

【2009年真题】若数据元素序列 11，12，13，7，8，9，23，4，5 是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（）。 
A．起泡排序 B．插入排序 C．选择排序 D．二路归并排序 
参考答案：B
答案解析：考查各排序算法的特点。 
解答本题之前要对不同排序算法的特点极为清楚。对于起泡排序和选择排序而言，每一趟过后都能确定一个元素的最终位置，而由题目中所说，前两个元素和后两个元素均不是最小或最大的两个元素并按序排列。答案 D 中的二路归并排序，第一趟排序结束都可以得到若干个有序子序列，而此时的序列中并没有两两元素有序排列。插入排序在每趟排序结束后能保证前面的若干元素是有序的，而此时第二趟排序后，序列的前三个元素是有序的，符合其特点。 

【2018年真题】给定一个含n（n>=1）个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{-5,3,2,3}中未出现的最小正整数是1；数组{1,2,3}中未出现的最小正整数是4。要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
（3）说明你所设计算法的时间复杂度和空间复杂度。

参考答案：
（1）题目要求算法时间上尽可能高效，因此采用空间换时间的办法（注：读者还可以是使用O(N)复杂度的排序法）。分配一个用于标记的数组B[n]，用来记录A中是否出现了1~n中的正整数，B[0]对应正整数1，B[n-1]对应正整数n，因此可能返回的值是1~n+1，当A中n个数恰好为1~n时返回n+1。当数组A中出现了小于等于0或者大于n的值时，会导致1~n中出现空余位置，返回结果必然在1~n中，因此对于A中出现了小于等于0或者大于n的值可以不采取任何操作。
（2）经过以上分析可以得出算法流程：从A[0]开始遍历A，若0<A[i]<=n，则令B[A[i]-1]=1；否则不做操作。对A遍历结束后，开始遍历数组B，若能查找到第一个满足B[i]==0的下标i，返回i+1即为结果，此时说明A中未出现的最小正整数在1~n之间。若B[i]全部不为0，返回i+1（跳出循环时i=n,i+1等于n+1），此时说明A中未出现的最小正整数是n+1。

int FindMissMin(int A[], int n) {  
    int i, *B;                    //标记数组  
    B = (int *)malloc(sizeof(int) * n);  //分配空间  
    memset(B, 0, sizeof(int) * n);   //赋初值为0  
    for (i = 0; i < n; i++)           
        if (A[i] > 0 && A[i] <= n)//若A[i]的值介于1~n，则标记数组B  
            B[A[i] - 1] = 1;  
    for (i = 0; i < n; i++) //扫描数组B，找到目标值  
        if (B[i] == 0) break;  
    return i + 1;           //返回结果  

（3）时间复杂度：遍历A一次，遍历B一次，两次循环内操作步骤为O(1)量级，因此时间复杂度为O(n)。空间复杂度：额外分配了B[n]，空间复杂度为O(n)。
提示：本题有更好的解法，请看本书配套视频讲解。