数据结构 第八章 排序

8.1 基本概念

有n个记录的序列{R1，R2，…，Rn}，其相应关键字的序列是{K1，K2， …，Kn }，相应的下标序列为1，2，…，n。

通过排序，要求找出当前下标序列1，2，…， n的一种排列p1，p2， …，pn，使得相应关键字满足如下的**非递减（或非递增）**关系，即：Kp1≤ Kp2≤…≤ Kpn ，这样就得到一个按关键字有序的记录序列：{Rp1，Rp2， …， Rpn}。

（1）内部排序与外部排序

• 内部排序：整个排序过程不需要访问外存便能完成

• 外部排序：参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，需要借助外存

（2）主关键字与次关键字

上面所说的关键字 Ki可以是记录i的主关键字，也可以是次关键字，甚至可以是记录中若干数据项的组合。

若Ki是主关键字，则任何一个无序的记录序列经排序后得到的有序序列是唯一的。若Ki是次关键字或是记录中若干数据项的组合，得到的排序结果将是不唯一的，因为待排序记录的序列中存在两个或两个以上关键字相等的记录。

（3）排序的稳定性

若两个记录A和B的关键字值相等，若排序后A、B的先后次序保持不变，则称这种排序算法是稳定的，反之称为不稳定的。

（4）算法的优劣性

• 时间效率：排序速度(排序所花费的全部比较次数)

• 空间效率：占内存辅助空间的大小

• 稳定性：排序是否稳定

注：本章均以升序排序为例。

8.1 插入排序

基本思想： 在一个已排好序的记录子集的基础上，每一步将下一个待排序的记录有序插入到已排好序的记录子集中，直到将所有待排记录全部插入为止。

排序算法	改进思路	时间复杂度	最好情况	最坏情况	空间复杂度	稳定性
直接插入	基本排序方法	$O(n^2)$	$O(n)$，n较小或元素基本有序	$O(n^2)$	$O(1)$	稳定
折半排序	改进了确定插入位置的方法：利用折半思想	$O(n^2)$	$O(nlogn)$	$O(n^2)$	$O(1)$	稳定
希尔排序	利用直接插入的最好情况：（1）n比较小（2）基本有序	$O(n^{1.5})$			$O(1)$	不稳定

8.1.1 直接插入

**算法思想：**将第i个记录插入到前面i-1个已排好序的记录中。

具体过程：将第i个记录的关键字Ki，顺次与其前面记录的关键字Ki-1，Ki-2，…, K1进行比较，将所有关键字大于Ki的记录依次向后移动一个位置，直到遇见一个关键字小于或者等于Ki的记录Kj，此时Kj后面必为空位置，将第i个记录插入空位置即可。

时间复杂度$O(n^2)$,空间复杂度为$O(1)$，直接插入排序是一种稳定的排序方法。

若排序序列为{ 48，62， 35，77，55，14 ，35，98}，下图给出用直接插入排序算法执行的过程（大括号内为当前已排好序的记录子集合）：

public void insertSort(int[] a, int len) {
    for (int i = 0; i < len; i++) {
        int j = i - 1, temp = a[i];

        while (j >= 0 && temp < a[j]) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = temp;
    }
}

public static void main(String[] args) {
    int[] data = {41,1,7,65,72,84,4,61,34,96,91,59,52,1,26,68,60,18,45,26};
    insertSort(data,data.length);
    System.out.println(Arrays.toString(data));
}

8.1.2 折半插入

算法思想： 在已形成的有序表中折半查找，并在适当位置插入，把原来位置上的元素向后顺移。

折半查找相比与插入排序比较的次数大大减少，全部元素比较次数仅为 $O(nlogn)$ 。但其并未改变移动元素的时间耗费，所以时间效率仍然为为 $O(n^2)$ ，空间效率为 $O(1)$ ,折半插入也是一种稳定的排序方法。

8.1.3 希尔排序

算法思想： 先将整个待排记录序列分割成若干子序列, 分别进行直接插入排序, 待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

技巧： 子序列的构成不是简单地“逐段分割”，而是将相隔某个增量dk的记录组成一个子序列。关于增量 d 的取法，最初提出取d=n/2，d=d/2，直到d=1为止。该思路的缺点是，在奇数位置的元素在最后一步才会与偶数位置的元素进行比较，使得希尔排序效率降低。因此后来提出d=d/3+1。

时间效率因为选取的增量的不同而不同，经验公式为 $O(n^{1.25})$ ~ $O(1.6n^{1.25})$ ，空间效率为 $O(1)$ ，希尔插入是一种不稳定的排序方法。

若待排序序列为{ 46，55， 13，42，94，17 ，05，70}，给出用希尔排序算法执行的过程：

public void shellSort(int[] a, int len) {
    for (int h = len / 2; h > 0; h /= 2) {
        for (int i = h; i < len; i++) {
            int temp = a[i];
            int j = i - h;
            for (; j >= 0; j -= h) {
                if (temp < a[j]) {
                    a[j + h] = a[j];
                } else {
                    break;
                }
            }
            a[j + h] = temp;
        }
    }
}

public static void main(String[] args) {
    int[] data = {41,1,7,65,72,84,4,61,34,96,91,59,52,1,26,68,60,18,45,26};
    shellSort(data, data.length);
    System.out.println(Arrays.toString(data));
}

8.2 交换排序

基于交换的排序法是一类通过交换逆序元素进行排序的方法。

排序算法	改进思路	时间复杂度	最好情况	最坏情况	空间复杂度	稳定性
冒泡排序	基本排序方法	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	稳定
快速排序	交换不相邻两个元素，消除多个逆序	$O(nlogn)$	$O(nlogn)$	$O(n^2)$	$O(logn)$	不稳定

8.2.1 冒泡排序

冒泡排序是一种简单的交换类排序方法，它是通过相邻的数据元素的交换，逐步将待排序序列变成有序序列的过程。

算法思想：每趟对所有记录从左到右相邻两个记录进行比较，若不符合排序要求，则进行交换。使用前提必需是顺序存储结构。

时间效率为 $O(n^2)$ ，空间效率为 $O(1)$, 冒泡排序是一种稳定的排序方法。

若序列为{8, 3, 2, 5, 9, 3, 6}，下图给出排序过程：

public void bubbleSort(int[] a, int len) {
    for (int i = 0; i < len - 1; i++) {
        for (int j = 0; j < len - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
    }
}

public static void main(String[] args) {
    int[] data = {41,1,7,65,72,84,4,61,34,96,91,59,52,1,26,68,60,18,45,26};
    bubbleSort(data, data.length);
    System.out.println(Arrays.toString(data));
}

我们可以简单优化一下冒泡排序，通过设置一个交换标志，如果某次循环没有发生交换操作，则说明序列已经有序：

public static void bubbleSort2(int[] a, int len) {
    for (int i = 0; i < len - 1; i++) {
        boolean flag = true;
        for (int j = 0; j < len - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                flag = false;
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
        if(flag) {
            break;
        }
    }
}

冒泡排序的另一个优化实现叫做鸡尾酒排序。它先对数组从左到右进行升序的冒泡排序，再对数组从右到左的降序冒泡排序，以此类推，持续的、依次的改变冒泡的方向，并不断缩小没有排序的范围。

public static void cocktailSort(int[] a, int len) {
    int left = 0, right = len - 1;
    while (left < right) {
        for (int i = left; i < right; i++) {
            if (a[i] > a[i + 1]) {
                int t = a[i];
                a[i] = a[i + 1];
                a[i + 1] = t;
            }
        }
        right--;

        for (int i = right; i > left; i--) {
            if (a[i - 1] > a[i]) {
                int t = a[i - 1];
                a[i - 1] = a[i];
                a[i] = t;
            }
        }
        left++;
    }
}

8.2.2 快速排序

改进要点：在冒泡排序中，由于扫描过程中只对相邻的两个元素进行比较，因此在互换两个相邻元素时只能消除一个逆序。如果能通过两个（不相邻的）元素的交换，消除待排序记录中的多个逆序，则会大大加快排序的速度。快速排序方法中的一次交换可能消除多个逆序。

算法思想：从待排序列中任取一个元素 (例如取第一个) 作为中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右两个子表；然后再对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个。此时便为有序序列了。

快速排序的使用前提也是顺序存储结构，快速排序的最差时间复杂度和冒泡排序是一样的都是$O(n^2)$，它的平均时间复杂度为$O(nlogn)$，是一种不稳定的排序方法。

注：下面例子引用于【坐在马桶上看算法】算法3：最常用的排序——快速排序。

假设我们现在对 [6 1 2 7 9 3 4 5 10 8] 这个10个数进行排序。首先在这个序列中随便找一个数作为基准数。为了方便，以第一个数 6 作为基准数。

分别从序列两端开始“探测”。先从右往左找一个小于 6 的数，再从左往右找一个大于 6 的数，然后交换他们。这里可以用两个变量 $i$ 和 $j$ ，分别指向序列最左边和最右边。我们为这两个变量起个好听的名字 “哨兵$i$” 和 “哨兵$j$” 。刚开始的时候让哨兵i指向序列的最左边（即$i$=1），指向数字 6 。让哨兵j指向序列的最右边（即$j$=10），指向数字 8 。

首先哨兵 $j$ 开始出动，因为此处设置的基准数是最左边的数，所以需要让哨兵 $j$ 先出动，这一点非常重要。哨兵 $j$ 一步一步地向左挪动（即 $j$–），直到找到一个小于 6 的数停下来。接下来哨兵i再一步一步向右挪动（即 $i$++ ），直到找到一个数大于 6 的数停下来。最后哨兵 $j$ 停在了数字 5 面前，哨兵 $i$ 停在了数字 7 面前。

现在交换哨兵 $i$ 和哨兵 $j$ 所指向的元素的值。交换之后的序列如下：6 1 2 5 9 3 4 7 10 8。

到此，第一次交换结束。接下来开始哨兵 $j$ 继续向左挪动。他发现了4（比基准数6要小，满足要求）之后停了下来。哨兵 $i$ 也继续向右挪动的，他发现了9（比基准数6要大，满足要求）之后停了下来。

此时再次进行交换，交换之后的序列如下：6 1 2 5 4 3 9 7 10 8。

第二次交换结束，“探测”继续。哨兵 $j$ 继续向左挪动，他发现了3（比基准数6要小，满足要求）之后又停了下来。哨兵 $i$ 继续向右移动，糟啦！此时哨兵 $i$ 和哨兵 $j$ 相遇了，哨兵 $i$ 和哨兵 $j$ 都走到3面前。说明此时“探测”结束。

我们将基准数6和3进行交换。交换之后的序列如下：3 1 2 5 4 6 9 7 10 8。

到此第一轮“探测”真正结束。此时以基准数6为分界点，6左边的数都小于等于6，6右边的数都大于等于6。

现在基准数 6 已经归位，它正好处在序列的第6位。此时我们已经将原来的序列，以6为分界点拆分成了两个序列，左边的序列是“3 1 2 5 4”，右边的序列是“9 7 10 8”，接下来还需要分别处理这两个序列。这是个递归的过程，直到将每个序列都排序完为止，下图展示了整个处理过程：

public void quickSort(int[] a, int left, int right) {
    if (left > right) {
        return;
    }

    // 基数
    int temp = a[left];
    int i = left, j = right;

    while (i != j) {
        // 先从右边开始左移
        while (a[j] >= temp && i < j) {
            j--;
        }
        // 再从左边开始右移
        while (a[i] <= temp && i < j) {
            i++;
        }

        // 交换元素
        if (i < j) {
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }

    // 基数和相交点交换
    a[left] = a[i];
    a[i] = temp;

    // 拆分成两个子队列递归
    quickSort(a, left, i - 1);
    quickSort(a, i + 1, right);
}

public static void main(String[] args) {
    int[] data = {41,1,7,65,72,84,4,61,34,96,91,59,52,1,26,68,60,18,45,26};
    quickSort(data, 0, data.length-1);
    System.out.println(Arrays.toString(data));
}

8.3 选择排序

在待排记录中依次选择关键字最小的记录作为有序序列的最后一条记录，逐渐缩小范围直至全部记录选择完毕。

排序算法	改进思路	时间复杂度	最好情况	最坏情况	空间复杂度	稳定性
简单选择排序	基本排序方法	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定
树型选择排序	排序比较过程中记录元素大小关系	$O(nlogn)$	$O(nlogn)$	$O(nlogn)$	$O(n)$	稳定
堆排序	将存储在向量中的数据元素看成一颗完全二叉树，减少了辅助空间	$O(nlogn)$	$O(nlogn)$	$O(nlogn)$	$O(1)$	不稳定

8.3.1 简单选择排序

**算法思想：**首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

时间复杂度 $О(n^2)$，空间复杂度为$О(1)$，简单选择排序是一种不稳定的排序方法。

public void selectSort(int[] a, int len) {
    for (int i = 0; i < len - 1; i++) {
        int min = i;
        for (int j = i + 1; j < len; j++) {
            if (a[min] > a[j]) {
                min = j;
            }
        }
        if (min != i) {
            int temp = a[min];
            a[min] = a[i];
            a[i] = temp;
        }
    }
}

public static void main(String[] args) {
    int[] data = {41,1,7,65,72,84,4,61,34,96,91,59,52,1,26,68,60,18,45,26};
    selectSort(data, data.length);
    System.out.println(Arrays.toString(data));
}

8.3.2 树型选择排序

算法思想：把带排序的n个记录的关键字两两进行比较，取出较小者。在[n/2]个较小者中，采用同样的方法进行比较选出每两个中的较小者。如此反复，直至选出最小关键字记录为止。

树型选择排序又称为锦标赛法(Tournament Sort)，时间复杂度$O(nlogn)$，空间复杂度为$O(n)$，树型选择排序是一种稳定的排序方法。相较于简单选择排序，虽然提升了时间复杂度，但是增加了空间复杂度，其本质是空间换时间。

若排序序列为{49, 38, 65, 97, 76, 13, 27, 49}，根据算法思想，第一次选出最小关键字13：

将已经选出的13忽略掉（设置为$∞$），重新选出最小值，即27：

依此类推，就可以得到一个有序序列。

8.3.3 堆排序

**算法思想：**把待排序数组看成一颗完全二叉树，结点 $r[i]$ 的左孩子是 $r[2i]$ ，右孩子是 $r[2i+1]$ ，双亲是 $r[i/2]$ 。通过调整完全二叉树建堆及重建堆选择出关键字最小记录及次小记录等实现排序。

首先介绍下堆、小根堆和大根堆的概念：

• 堆(Heap)：每个结点的值都大于、小于或等于其左右孩子结点的值

• 小根堆：每个结点的值都小于或等于其左右孩子结点的值

$\begin{cases} k_i \leq k2_i \\ k_i \leq k2_i + 1 \end{cases}$

• 大根堆：每个结点的值都大于或等于其左右孩子结点的

$\begin{cases} k_i \ge k2_i \\ k_i \ge k2_i + 1 \end{cases}$

时间复杂度：$T(n)=O(nlogn)$，空间复杂度：$S(n)=O(1)$，堆排序是一种不稳定的排序方法。

以大根堆为例，首先我们根据堆定义建立初堆。去掉最大元之后重建堆，得到次大元。如此类推，完成堆排序。

建初堆步骤：

将一个任意序列看成是对应的完全二叉树，筛选需从最后一个子树位置[n/2]开始，反复利用重建堆法自底向上，把所有子树逐层调整为堆，直至根节点。

重建堆步骤：：

（1）将完全二叉树根结点中的关键字x移出，此时根结点相当于空结点。

（2）从空结点的左、右子中选出关键字最大的记录，如果该记录的关键字大于x，则将该记录上移至空结点。

（3）重复上述移动过程，直到空结点左、右子的关键字均不大于x。此时，将待调整记录放入空结点即可。

重建堆的调整方法相当于把待调整记录逐步向下“筛”的过程，所以一般称为筛选。

堆排序步骤：
（1）建立初堆：从最后一子树 $n/2$ 直到根建堆。

（2）将堆顶第一个元素与最后一个元素互换。

（3）去掉最后元素，将剩余元素调整建堆，再转出堆顶元素。

（4）重复执行（2）、（3）步骤 $n-1$ 次，直到序列有序。

若关键字初始序列为：｛48，62，35，77，55，14，35 ，98｝，给出堆排序的具体步骤：

public void heapSort(int[] a, int len) {
    // 建立出堆
    for (int i = len / 2 - 1; i >= 0; i--) {
        adjustHeap(a, i, len - 1);
    }
    
    // 交换首末元素,并重建堆
    for (int i = len - 1; i >= 0; i--) {
        int temp = a[0];
        a[0] = a[i];
        a[i] = temp;
        adjustHeap(a, 0, i - 1);
    }
}

private void adjustHeap(int[] a, int pos, int len) {
    int temp, child;
    for (temp = a[pos]; 2 * pos + 1 <= len; pos = child) {
        child = 2 * pos + 1;
        if (child < len && a[child] < a[child + 1]) {
            child++;
        }
        if (a[child] > temp) {
            a[pos] = a[child];
        } else {
            break;
        }
    }
    a[pos] = temp;
}

public static void main(String[] args) {
    int[] data = {41,1,7,65,72,84,4,61,34,96,91,59,52,1,26,68,60,18,45,26};
    heapSort(data, data.length);
    System.out.println(Arrays.toString(data));
}

8.4 归并排序

前面介绍的插入排序、交换排序和选择排序，都是将一组记录按关键字大小排成一个有序的序列。而归并排序它的基本思想是基于合并，将两个或两个以上有序表合并成一个新的有序表。下面以二路归并为例，介绍归并排序算法。

算法思想： 假设初始序列含有 n 个记录，首先将这 n 个记录看成 n 个有序的子序列， 每个子序列的长度为 1，然后两两归并，得到[2/n]个长度为 2（n 为奇数时，最后一个序列的长度为 1）的有序子序列。在此基础上，再对长度为2的有序子序列进行两两归并，得到若干个长度为4的有序子序列。如此重复，直至得到一个长度为 n 的有序序列为止。

归并排序总的时间复杂度为 $O(nlogn)$ 。在实现归并排序时，需要和待排记录等数量的辅助空间，空间复杂度为 $O(n)$ ，归并排序是一种稳定的排序方法。

排序算法	改进思路	时间复杂度	最好情况	最坏情况	空间复杂度	稳定性
归并排序	分解与合并	$O(nlogn)$	$O(nlogn)$	$O(nlogn)$	$O(n)$	稳定

可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程，递归深度为 $logn$ 。

再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤。

 public void mergeSort(int[] a, int left, int right, int[] temp) {
    if(left < right) {
        int mid = (left + right) / 2;

        //左边归并排序,使得左子序列有序
        mergeSort(a, left, mid, temp);
        //右边归并排序,使得右子序列有序
        mergeSort(a, mid + 1, right, temp);
        //将两个有序子数组合并操作
        merge(a, left, mid, right, temp);
    }
}

private void merge(int[] a, int left, int mid, int right, int[] temp) {
    // 左指针、右指针、temp数组指针
    int i = left, j = mid + 1, t = 0;

    // 依次比较填充temp数组
    while (i <= mid && j <= right) {
        if(a[i] < a[j]) {
            temp[t++] = a[i++];
        } else {
            temp[t++] = a[j++];
        }
    }

    // 将剩余未拷贝的元素拷贝到temp数组
    while (i <= mid) {
        temp[t++] = a[i++];
    }
    while (j <= right) {
        temp[t++] = a[j++];
    }

    // 将temp数组中元素拷贝回原始数组
    t = 0;
    while (left <= right) {
        a[left++] = temp[t++];
    }
}

public static void main(String[] args) {
    int[] data = {41,1,7,65,72,84,4,61,34,96,91,59,52,1,26,68,60,18,45,26};
    mergeSort(data, 0, data.length - 1, new int[data.length]);
    System.out.println(Arrays.toString(data));
}

一般情况下，由于要求附加和待排记录等数量的辅助空间，因此很少利用二路归并排序进行内部排序，归并的思想主要用于外部排序。

外部排序分为以下两步：

（1）待排序记录分批读入内存，用某种方法在内存排序，组成有序的子文件，再按某种策略存入外存。

（2）子文件多路归并，成为较长有序子文件，再进入外存，如此反复，直到整个待排序文件有序。

8.5 分配类排序

8.5.1 桶排序

已知一组范围在0 ~ 10的数据(如:9,5,2,7,7)，我们只需要借助一个一维数组就可以解决问题。

首先，我们申请一个长度为11的数组int a[11]，因为我们的数据范围是0 ~ 10。开始的时候，我们将所有元素都初始化为0，表示这些数都未出现过。例如a[0]等于0，就表示待排序数据还未出现过0；同理，若a[9]等于1，则表示待排数据中9出现过1次。
　　
我们只需要遍历待排数组，然后将每个数值对应下标的元素加1(比如第一个数是9，我们就将a[9]+1)。你会发现，待排数组遍历完之后，a[0] ~ a[10]中的数值，其实就是0 ~ 10出现的次数，我们只需要按次数将下标打印出来就实现排序了。代码如下:

#include <stdio.h>
int main() {
    int a[11],i,j,t;
    for(i=10; i>=0; i--) {
        a[i]=0;
    }

    for(i=1; i<=5; i++) { //循环读入5个待排数
        scanf("%d",&t); //把每一个数读到变量t中
        a[t]++; //进行计数
    }

    for(i=10; i>=0; i--) {
        for(j=1; j<=a[i]; j++) {
            printf("%d ",i);
        }
    }

    printf("\r\n");
    getchar();
    return 0;
}

首先我们用了一个M次（M为桶的个数）的循环把桶清空，然后再用一个N次（N为待排序数据的个数）的循环，设置的数据的显示次数，最后又进行了M + N次循环，把数据显示出来。所以，整个排序算法一共执行了M+N+M+N次。因此该算法的时间复杂度是O(m+n+m+n)即O(2 * (m + n ))。忽略常数后最终桶排序的时间复杂度为 $O(M+N)$ ，这是一个非常快的排序算法。

桶排序虽快，但其实它是用空间在换时间。如果需要排序的数范围非常宽，那我们就需要申请非常多的“桶”来存储每一个数出现的次数，即使依然只是需要对5个数进行排序。

8.5.2 基数排序

基数排序(Radix Sort)是桶排序的扩展，它的基本思想是：将整数按位数切割成不同的数字，然后按每个位数分别比较。

具体做法：

将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

以序列（278，109,063,930,589,184,505,269,008,083）进行基数排序为例。

分析：

序列中记录的关键字均为 1000 以下的十进制正整数。故每个关键字由三位子关键字 $k^1$ $k^ 2$ $k^3$ 构成，其中 $k^1$代表关键字的百位数，$k^2$代表关键字的十位数，$k^3$代表关键字的个位数，基数 $rd=10$。进行分配与收集操作需要用到队列，队列的数目与基数相等，所以共设 10 个链队列，head[i]和 tail[i]分别为队列 i 的头指针和尾指针。

首先将待排序记录存储在一个链表中，如下图（a）所示，然后进行如下三趟分配、收集操作。

第一趟分配用最低位子关键字 $k^3$ 进行，将所有最低位子关键字相等的记录分配到同一个队列，如下图（b）所示，然后进行收集操作。收集时，改变所有非空队列的队尾结点的 next 指针，令其指向下一个非空队列的队头记录，从而将分配到不同队列中的记录重新链成一个链表。第一趟收集完成后，结果如下图（c）所示。

第二趟分配用次低位子关键字 $k^2$ 进行，将所有次低位子关键字相等的记录分配到同一个队列，如下图 （d）所示。第二趟收集完成后，结果如下图（e）所示。

第三趟分配用最高位子关键字 $k^1$ 进行，将所有最高位子关键字相等的记录分配到同一个队列，如下图（f）所示。第三趟收集完成后，结果如下图 （g）所示。至此，整个排序过程结束。

8.6 总结

排序算法	改进思路	时间复杂度	最好情况	最坏情况	空间复杂度	稳定性
直接插入	基本排序方法	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	稳定
折半排序	改进了确定插入位置的方法：利用折半思想确定在有序表中的插入位置	$O(n^2)$	$O(nlogn)$	$O(n^2)$	$O(1)$	稳定
希尔排序	利用直接插入的最好情况：（1）n比较小（2）基本有序	$O(n^{1.5})$			$O(1)$	不稳定
冒泡排序	基本排序方法	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	稳定
快速排序	交换不相邻两个元素，消除多个逆序	$O(nlogn)$	$O(nlogn)$	$O(n^2)$	$O(logn)$	不稳定
简单选择排序	基本排序方法	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定
树型选择排序	排序比较过程中记录元素大小关系	$O(nlogn)$	$O(nlogn)$	$O(nlogn)$	$O(n)$	稳定
堆排序	将存储在向量中的数据元素看成一颗完全二叉树，减少了辅助空间	$O(nlogn)$	$O(nlogn)$	$O(nlogn)$	$O(1)$	不稳定
归并排序	分解与合并	$O(nlogn)$	$O(nlogn)$	$O(nlogn)$	$O(n)$	稳定

元素的移动次数与关键字的初始排列次序无关的是：基数排序。

元素的比较次数与初始序列无关是：选择排序。

算法的时间复杂度与初始序列无关的是：直接选择排序。

（1）简单排序法一般只用于 n 较小的情况（例如 n<30）。当序列中的记录“基本有序” 时，直接插入排序是最佳的排序方法。如果记录中的数据较多，则应采用移动次数较少 的简单选择排序法。

（2）快速排序、堆排序和归并排序的平均时间复杂度均为 $O(nlogn)$，但实验结果表明，就平均时间性能而言，快速排序是所有排序方法中最好的。遗憾的是，快速排序在最坏情况下的时间性能为 $O(n^2)$。堆排序和归并排序的最坏时间复杂度仍为 $O(nlogn)$，当 n 较大时，归并排序的时间性能优于堆排序，但它所需的辅助空间最多。

（3）可以将简单排序法与性能较好的排序方法结合使用。例如，在快速排序中，当划分 子区间的长度小于某值时，可以转而调用直接插入排序法；或者先将待排序序列划分成 若干子序列，分别进行直接插入排序，然后再利用归并排序法，将有序子序列合并成一 个完整的有序序列。

（4）基数排序的时间复杂度可以写成 $O(dn)$。因此，它最适用于 n 值很大而关键字的位 数 d 较小的序列。当 d 远小于 n 时，其时间复杂度接近 $O(n)$。

（5）从排序的稳定性上来看，在所有简单排序法中，简单选择排序是不稳定的，其他各 种简单排序法都是稳定的。然而，在那些时间性能较好的排序方法中，希尔排序、快速 排序、堆排序都是不稳定的，只有归并排序、基数排序是稳定的。

综上所述，每一种排序方法各有特点，没有哪一种方法是绝对最优的。应根据具体情况选择合适的排序方法，也可以将多种方法结合起来使用。

8.7 例题

8.7.1 例1

希尔排序法、快速排序法、堆排序法和二路归并排序法四种排序法中，要求辅助空间最多的是【 】排序。

二路归并排序法

8.7.2 例2

快速排序、归并排序、堆排序、基数排序中，适合记录个数很大，但待排序关键字位数很少的排序算法是【 】。

基数排序

8.7.3 例3

设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列【 】方法可以达到此目的。
A.归并排序 B.堆排序 C.基数排序 D.快速排序

B.堆排序

8.7.4 例4

在插入和选择排序中，若初始数据基本正序，则选用【 】；若初始数据基本反序，则选用【 】。在堆排序和快速排序中，若初始记录接近正序或反序，则选用【 】；若初始记录基本无序，则最好选用【 】。

插入排序 ; 选择排序 ; 堆排序 ; 快速排序

8.7.5 例5

设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则：

冒泡排序一趟扫描的结果是【 】；

H C Q P A M S R D F X Y

初始步长为4的希尔（shell）排序一趟的结果是【 】；

P A C S Q D F X R H M Y

二路归并排序一趟扫描的结果是【 】；

H Q C Y A P M S D R F X

快速排序一趟扫描的结果是【 】；

F H C D P A M Q R S Y X

堆排序初始建堆的结果是【 】。

A D C R F Q M S Y P H X