第七讲排序¶

【考频统计】：

年份	考点	分值
2009	堆的插入操作、内部排序算法的分析或选择	单选*2 = 4分
2010	快速排序、内部排序算法的分析或选择	单选*2 = 4分
2011	快速排序、堆的插入操作	单选*2 = 4分
2012	插入排序、内部排序算法的分析或选择	单选*2 = 4分
2013	基数排序	单选2分
2014	希尔排序、快速排序	单选*2 = 4分
2015	希尔排序、堆的删除操作	单选*2 = 4分
2016	外部排序、快速排序的分治思想（大题）	单选2分+算法题15分=$17$分
2017	归并排序、内部排序算法的分析或选择	单选*2 = 4分
2018	希尔排序、建堆操作	单选*2 = 4分
2019	快速排序、内部排序算法的分析或选择、外部排序之最佳归并树	单选*3 = 6分
2020	堆、内部排序算法的分析或选择	单选*2 = 4分
2021	基于入堆实现的建堆、基数排序、计数排序应用题	单选*2 + 应用题 = $12$分
2022	二路归并排序、内部排序算法的分析或选择、应用题(堆排序或者快排的分治思想)	单选*2 + 应用题 = $14$分
2023	内部排序算法的分析或选择、快速排序、外部排序的置换选择排序	单选*2 + 应用题 = $14$分

【考点分析】：快速排序单独考察6次、希尔排序考察3次、堆考察6次，这些都是极重要的考点，此外各类算法的分析比较以及选择哪一种排序算法也是常考点；

【考点预测】近3年，排序算法的思想经常用来考应用题，这里针对应用题，要重点关注

堆的入堆、出堆、建堆操作的手动模拟；

归并排序的分治思想

基数排序的手工模拟

外部排序中的败者树、最佳归并树添加“虚段”后问你读写外存的次数（注意与哈夫曼树的带权路径长度WPL联系起来，注意乘2）

7.1 排序算法的评价维度¶

运行效率：我们期望排序算法的时间复杂度尽量低，且总体操作数量较少（即时间复杂度中的常数项降低）。对于大数据量情况，运行效率显得尤为重要。
就地性：顾名思义，「原地排序」通过在原数组上直接操作实现排序，无需借助额外的辅助数组，从而节省内存。通常情况下，原地排序的数据搬运操作较少，运行速度也更快。
稳定性：「稳定排序」在完成排序后，相等元素在数组中的相对顺序不发生改变。例如 $nums={3,1,2_1,2_2}$ ，数字 $2$ 出现了两次，下标表示他们出现的次序，若排序方法将 $nums$ 排成了 ${1,2_2,2_1,3}$ ，虽然排序结果正确，但改变了两个 $2$ 的相对位置。只有排序为 ${1,2_1,2_2,3}$ 我们才说该排序是稳定的。稳定排序是优良特性，也是多级排序场景的必要条件。

稳定性的用途的例子：假设有一批二手房供挑选，可以先对这批二手房按总价由低到高排序，排完序后发现有一些总价相同的房子，但是面积不同。如果需要再按面积由小到大排序排序，此时若采用稳定性的排序算法，就可以使得面积相同的房子中，总价最低的房子排在前面。简而言之，若排序时需要保留序列的初始相对顺序，那么在排序时应选择稳定的排序算法。

自适应性：「自适应排序」的时间复杂度会受输入数据的影响，即最佳、最差、平均时间复杂度并不完全相等。

自适应性需要根据具体情况来评估。如果最差时间复杂度差于平均时间复杂度，说明排序算法在某些数据下性能可能劣化，因此被视为负面属性；而如果最佳时间复杂度优于平均时间复杂度，则被视为正面属性。

是否基于比较：「基于比较的排序」依赖于比较运算符（$<$ , $=$ , $>$）来判断元素的相对顺序，从而排序整个数组，理论最优时间复杂度为 $O(n \log n)$ 。而「非比较排序」不使用比较运算符，时间复杂度可达 $O(n)$ ，但其通用性相对较差。

7.2 各大内部排序算法比较¶

算法名称	动画	备注
直接插入排序		（有序区，无序区）把无序区的第一个元素插入到有序区的合适位置适合局部有序或文件长度较小
希尔排序		每一轮按照事先决定的间隔进行插入排序，间隔会依次缩小，但最后一次一定为1.代码量小，不使用调用堆栈，速度相当快，在内存非常宝贵的情况下很有用，例如嵌入式和旧式大型机应用程序
冒泡排序		(无序区，有序区) 从无序区中通过交换依次将最大元素冒到有序区末尾；当某一轮未发生交换元素则提前终止；所以输入数组已排序时最好。
快速排序	法一：法二：	(小数，基准元素，大数) 当输入数组有序，且总是选取第一个元素为主轴时，时间复杂度退化为$O(n^2)$。空间开销为递归深度。
选择排序		比较得多换的少；比较次数与序列状态无关
堆排序		（最大堆，有序区）弹出堆顶元素放进有序区，将堆底元素放入堆顶适用于关键字很多的情况，经常用于`top-k` 问题；输入数组所有数字相等时，时间复杂度为O(n)。
二路归并排序		408一般采用图示的自顶向下非原地方法；高度并行化，可同时处理大量数据
计数排序
基数排序		适用于关键字很多的情况，如果关键字的取值范围很大，采用最高位优先
桶排序		桶排序是否稳定取决于排序桶内元素的算法是否稳定。

排序算法	平均/最佳/最差时间复杂度	空间复杂度	就地性	适用数据对象	比较次数是否与序列初始状态有关	元素的移动(交换)次数是否与序列初始状态有关	排序趟数是否与序列初始状态有关
插入	$O(n^2)/O(n)/O(n^2)$	$O(1)$	原地	数组/链表	有关	有关	无关
折半插入	$O(n^2)$	$O(1)$	原地	数组	无关	有关	无关
希尔	$O(n^{1.3})/O(nlogn)/O(n^2)$不准确，复杂度取决于增量序列	$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(1)$	原地	数组	有关（不同情况堆化比较的次数不同）	有关	无关
归并	$O(nlogn)/O(nlogn)/O(nlogn)$	$O(n)$	非原地	数组/链表	有关（不同状态两两归并次数不同）	无关(因为非原地排序)	无关
计数	$ O(n + k) $$ k $为数据范围	$ O(n + k) $	非原地	数组/链表	非比较排序，无关	非比较(不基于移动元素)排序，无关	无关
基数	$ O(d(n + r)) $$ d $为最大位数(即排序趟数)，待排序数据为$ r $进制	$ O(n+r) $	非原地	数组/链表	非比较排序，无关	非比较排序，无关	无关
桶	$ O(n+k)/O(n+k)/O(n^2) $$ k $为桶的数量	$ O(n+k) $	非原地	数组	非比较排序，无关	非比较排序，无关	无关

一次交换移动3次，swap

稳定性: 存在稳定和非稳定版本时，视作「稳定」。

7.3 插入类排序¶

7.3.1 直接插入排序¶

「插入排序 Insertion Sort」是一种简单的排序算法，它的工作原理与手动整理一副牌的过程非常相似。

具体来说，我们在未排序区间选择一个基准元素，将该元素与其左侧已排序区间的元素逐一比较大小，并将该元素插入到正确的位置。

回忆数组的元素插入操作，设基准元素为 base ，我们需要将从目标索引到 base 之间的所有元素向右移动一位，然后再将 base 赋值给目标索引。

简言之：每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成。

单次插入过程

算法流程

插入排序的整体流程如下：

初始状态下，数组的第 1 个元素已完成排序。
选取数组的第 2 个元素作为 base ，将其插入到正确位置后，数组的前 2 个元素已排序。
选取第 3 个元素作为 base ，将其插入到正确位置后，数组的前 3 个元素已排序。
以此类推，在最后一轮中，选取最后一个元素作为 base ，将其插入到正确位置后，所有元素均已排序。\
算法实现

void InsertSort(int nums[],int size) {
    // 外循环：已排序元素数量为 1, 2, ..., n
    for(int i = 1; i < size; ++i) {
        int base = nums[i], j = i - 1;
        //内循环，将base插入到已排序序列的正确位置；
        while(j >= 0 && nums[j] > base) {
            //将nums[j]向后移动一位；
            nums[j+1] = nums[j];
            j--;
        }
        //将base插入到正确位置；
        nums[j+1] = base;
        // 若发生移动，此时的插入对象数字≥j位置的数字，故插入位置为j + 1，
        //若未移动也成立，无需判断
    }
}

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        for(int i = 1; i < nums.size(); ++i) {
            int base = nums[i];
            int j = i -1;
            for(; j >=0 ; j--) {
                if(nums[j] > base) {
                    nums[j+1] = nums[j];
                }else break;
            }
            nums[j+1] = base;
        }       
        return nums;
    }
};

算法特性：
时间复杂度$O(n^2)$、自适应排序 ：最差情况下，每次插入操作分别需要比较 $n - 1$ , $n-2$ , $\cdots$ , $2$ , $1$ 次，求和得到 $\frac{(n - 1) n}{2}$ ，因此时间复杂度为 $O(n^2)$ 。在遇到有序数据时，插入操作会提前终止(当前元素值大于它的前一个元素的值)。当输入数组完全有序时，插入排序达到最佳时间复杂度 $O(n)$ 。

因此，该算法的比较次数与移动次数都与序列初始状态有关。

空间复杂度$O(1)$、原地排序 ：指针 $i$ , $j$ 使用常数大小的额外空间。
稳定排序：在插入操作过程中，我们总是从后往前先比较再移动，因此会将元素插入到相等元素的右侧，不会改变它们的顺序，因此该算法稳定。
适用性：适用于顺序存储和链式存储的线性表。在链表中，可以从前往后查找指定元素的位置，且不用移动元素。

147. 对链表进行插入排序

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if (head == nullptr) {
            return head;
        }
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* lastSorted = head;
        ListNode* curr = head->next;
        while (curr != nullptr) {
            if (lastSorted->val <= curr->val) {
                lastSorted = lastSorted->next;
            } else {
                ListNode *prev = dummyHead;
                while (prev->next->val <= curr->val) {
                    prev = prev->next;
                }
                lastSorted->next = curr->next;
                curr->next = prev->next;
                prev->next = curr;
            }
            curr = lastSorted->next;
        }
        ListNode* result = dummyHead->next;  //保存结果后再释放哨兵节点；
        delete dummyHead;  //避免哨兵节点内存泄漏；
        return result; 
    }
};

插入排序优势

插入排序的时间复杂度为 $O(n^2)$ ，而我们即将学习的快速排序的时间复杂度为 $O(n \log n)$ 。尽管插入排序的时间复杂度相比快速排序更高，但在数据量较小的情况下，插入排序通常更快。

这个结论与线性查找和二分查找的适用情况的结论类似。快速排序这类 $O(n \log n)$ 的算法属于基于分治的排序算法，往往包含更多单元计算操作。而在数据量较小时，$n^2$ 和 $n \log n$ 的数值比较接近，复杂度不占主导作用；每轮中的单元计算操作数量起到决定性因素。

实际上，许多编程语言（例如 Java）的内置排序函数都采用了插入排序，大致思路为：对于长数组，采用基于分治的排序算法，例如快速排序；对于短数组，直接使用插入排序。

虽然冒泡排序、选择排序和插入排序的时间复杂度都为 $O(n^2)$ ，但在实际情况中，插入排序的使用频率显著高于冒泡排序和选择排序。这是因为：

冒泡排序基于元素交换实现，需要借助一个临时变量，共涉及 3 个单元操作；插入排序基于元素赋值实现，仅需 1 个单元操作。因此，冒泡排序的计算开销通常比插入排序更高。

选择排序在任何情况下的时间复杂度都为 $O(n^2)$ 。如果给定一组部分有序的数据，插入排序通常比选择排序效率更高。

选择排序不稳定，无法应用于多级排序。

7.3.2 优化—折半插入排序¶

注意到插入排序的每一轮向前插入都使得该元素在完成插入后，从第一个元素到该元素是有序状态（指这部分的相对排序状态，在它们中间后续可能还会插入其他数字），利用这一点，对一个新的插入对象向前执行折半插入，能够显著减少比较的次数。另一种优化是增量递减插入排序，也叫 希尔排序 ，将在希尔排序章节中介绍。

折半插入的关键在于找到插入位置，折半过程代码如下。这实际上是二分查找「模版一」中的「小于等于」情形。二分查找从入门到入睡

int binarySearch(vector<int>& nums, int l, int r, int target) {
    while(l <= r) {  //使用待查找区间的左边界；
        int mid = l + (r - l) / 2;
        if(nums[mid] <= target) l = mid + 1;  
        else r = mid - 1;  
    }
    return l;
}

折半插入总的查找(比较)次数虽为$O(nlogn)$，但平均移动 (每轮移动一半的数字) 次数仍是$O(n^2)$。

比较次数与待排序序列的初始状态无关，仅取决于表中元素个数n；而元素的移动次数与普通的插入排序一样，依赖于序列的初始状态；

因此时间复杂仍为$O(n^2)$

由于需要折半查找插入位置，因此仅适用于顺序表，链表不行嗷！

完整操作代码

class Solution {
private: 
    int binarySearch(vector<int>&nums,int l, int r, int target) {
        while(l <= r) {
            int mid = l + (r - l) / 2;
            if(nums[mid] <= target) l = mid + 1;
            else r= mid - 1;
        }
        return l;
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        for(int i = 1; i < nums.size(); ++i) {  //n-1次外循环；
            int base = nums[i];
            int pos = binarySearch(nums,0,i-1,base);  //通过二分查找找到插入位置；
            for(int j = i; j > pos; j--) {  //将待插入位置后的元素移动；
                nums[j] = nums[j-1];
            }
            nums[pos] = base; //将base插入到正确位置；
        }
        return nums;       
    }
};

7.3.3 希尔排序¶

算法描述

希尔排序是 简单插入排序的改进 ，它基于以下事实。

简单插入排序对 排序程度较高的序列 有较高的效率。假设初始序列已完全排序，则每一轮均只需比较一次，将得到 $O(n)$ 的线性复杂度，冒泡排序和选择排序做不到这一点，均仍需 $O(n^2)$ 次比较 (冒泡排序在应用提前结束优化后可以做到) 。
简单插入排序每次比较最多将数字移动一位，效率较低。

Donald Shell 在 1959 年发表的论文中，针对这两个事实，提出如下方法。对原待排序列中相隔 $gap$ 的数字执行简单插入排序，然后缩小 $gap$，对新的 $gap$ 间隔的数字再次执行简单插入排序。以一种规则减少 $gap$ 的大小，当 $gap$ 为 1 时即简单插入排序，因此希尔排序也称作 增量递减排序。希尔在论文中提出的增量序列生成式为 $n / 2^k$，k = 1, 2, 3, ... ，例如 n = 11，则增量序列为 ${1,2,5}$ 。在讨论希尔排序时，可将其称为 Shell增量，另有更优的 Hibbard增量、Knuth增量、Sedgewick增量 等。

程序开始时$gap$较大，待排元素较少，因此排序速度较快。当$gap$较小时，基于第一点，此时待排序列已大致有序，排序效率接近线性复杂度。因此能够期待希尔排序复杂度将优于$O(n^2)$。详细见「复杂度分析」。

稳定性：不稳定。

gap > 1 时，跨越 $gap$ 的插入可能会改变两个相同值元素的位置关系。例如 ${0, 1, 4, 3_1, 3_2, 5, 6}$ ，当 gap = 2 时，对 ${0, 4, 3, 6}$ 简单插入排序后得到 ${0, 1, 3_2, 3_1, 4, 5, 6}$ ，原数组中的两个 3 的相对位置发生了变化。（当相同关键字的记录被划分到不同的子表时，进行排序后可能会改变它们之间的相对次序）

复杂度分析

时间复杂度：希尔排序的时间复杂度与增量序列的选择有关。最优复杂度增量序列尚未明确。

Shell增量 (Shell, 1959): $n / 2^k$，最坏时间复杂度 $Θ(n^2)$，当$n$在某个特定范围内，时间复杂度为$O(n^{1.3})$

当输入数组已排序时，达到最好时间复杂度。

空间复杂度：算法中只有常数项变量，$O(1)$。

逆序数

希尔排序是较早出现的 突破二次复杂度 的排序算法，下面从 逆序数 的角度来直观地证明为何希尔排序能够突破二次复杂度。

以数值从小到大为「顺序」，则在一个排列中，如果任意一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序，一个排列中逆序的总数就称为这个排列的 逆序数。排序的过程就是不断减少逆序数 直到逆序数为 0 的过程。

回顾冒泡排序和简单插入排序，算法的每一次交换，都只交换相邻元素（简单插入排序中元素每次右移也看作交换），因此每次交换只能减少一个逆序。冒泡排序和简单插入排序的元素平均交换次数均为 $O(n^2)$，也即逆序数 (或逆序数减少次数) 为 $O(n^2)$。如果能跨越多个数字进行交换，则可能一次减少多个逆序。在选择排序中，每轮选到最小元素后的交换即是跨越多个元素的，交换次数 (减少逆序数的操作) 为 $O(n)$，要少于冒泡和简单插入排序，只是因为比较次数仍是 $O(n^2)$，所以整体复杂度为 $O(n^2)$。

现在来分析跨越多个元素的交换如何减少逆序数，假设 $arr[i]>arr[j],i\<j$。对于任意的 $arr[k] (i < k < j)$：

若 $arr[k] < arr[j]$ ，交换 $arr[i] 和$arr[j] 后，三者的逆序数从 2 变为 1。
若 $arr[k] > arr[i]$ ，交换 $arr[i] 和$arr[j] 后，三者的逆序数从 2 变为 1。
若 $arr[i] > arr[k] > arr[j]$，交换 $arr[i]$ 和 $arr[j]$ 后，三者的逆序数从 3 变为 0 。

$arr[k] = arr[i]$ 或 $arr[k] = arr[j]$ 的情况一样，都使得三者逆序数从 2 变为 1 ，下图省略。

对 $arr[i]$ 和 $arr[j]$ 的逆序消除，使得逆序至少减少一次，并 有机会减少大于一次的逆序 (情况3)，因此能够以比 $n^2$ 低阶的次数消除所有逆序。

实际上归并排序，快速排序，堆排序均实现了 长距离交换元素，使得复杂度优于 $O(n^2)$。

希尔排序的示例图：包括每一轮(趟)希尔排序后的状态（高频题型：给出增量序列，分析每一趟排序后的状态）
实现代码：

class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
    int n = nums.size();
    for(int gap = n/2; gap > 0; gap /= 2) {  
        //gap初始值为n/2,缩小gap直至为1；
        for(int start = 0; start < gap; start++) { 
            //步长增量为gap，当前增量下需要对gap组序列进行简单插入排序；
            for(int i = start + gap; i < n; i += gap) { 
                //从这里开始就是对当前增量序列进行简单插入排序；
                int base = nums[i], j = i - gap;
                while(j >= 0 && nums[j] > base) {
                    nums[j+gap] = nums[j];
                    j -= gap;
                }
                nums[j+gap] = base;
            }
        }
    }
    return nums;
}
};

实际上 $Shell$ 增量无论 $n$ 等于多少，都直接从 $n / 2$ 开始，不断除 2 直到 gap = 1。详情可参考 Donald Shell 原论文 A High-Speed Sorting Procedure。原论文 TABLE 1 给出了长度为 11 的序列 ${3, 11, 6, 4, 9, 5, 7,8,10, 2, 1}$，首个 $gap$ 为 gap = 11 / 2 = 5，接着是 gap = 2 ，gap = 1。

7.4交换类排序¶

7.4.1 冒泡排序¶

「冒泡排序 Bubble Sort」通过连续地比较与交换相邻元素实现排序。这个过程就像气泡从底部升到顶部一样，因此得名冒泡排序。

我们可以利用元素交换操作模拟上述过程：从数组最左端开始向右遍历，依次比较相邻元素大小，如果“左元素 > 右元素”就交换它俩。遍历完成后，最大的元素会被移动到数组的最右端。

动画演示：如下动图展示了 ${4,6,2,1,7,9,5,8,3}$ 的冒泡排序过程（未应用优化）\
算法流程

设数组的长度为 $n$ ，冒泡排序的步骤为：

首先，对 $n$ 个元素执行“冒泡”，将数组的最大元素交换至正确位置，

接下来，对剩余 $n - 1$ 个元素执行“冒泡”，将第二大元素交换至正确位置。

以此类推，经过 $n - 1$轮“冒泡”后，前$n - 1$大的元素都被交换至正确位置。

仅剩的一个元素必定是最小元素，无需排序，因此数组排序完成。

未优化版本代码

void bubbleSort(vector<int> &nums) {
    // 外循环：未排序区间为 [0, i]
    for (int i = nums.size() - 1; i > 0; i--) {
        // 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端 
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                // 交换 nums[j] 与 nums[j + 1]
                int temp = nums[j];   
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;               
            }
        }
    }
}

效率优化
提前结束式优化：我们发现，如果某轮“冒泡”中没有执行任何交换操作，说明数组已经完成排序，可直接返回结果。因此，可以增加一个标志位 flag 来监测这种情况，一旦出现就立即返回。

经过优化，冒泡排序的最差和平均时间复杂度仍为 $O(n^2)$ ；但当输入数组完全有序时，比较次数为$n-1$,数组元素交换次数为0，因此可达到最佳时间复杂度$O(n)$

void bubbleSortWithFlag(int nums[], int size) {
    // 外循环：未排序区间为 [0, i]
    for (int i = 0; i < size - 1; i++) {
        bool flag = false;
        // 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端 
        for (int j = 0; j < size - 1 - i; j++) {
            if (nums[j] > nums[j + 1]) {
                int temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
                flag = true;
            }
        }
        if (flag == false)  break;  //每执行完一趟冒泡排序，都检查一下标志位，如果本轮没有交换，说明表
    }
}

冒泡界优化\ 记录前一轮交换的最终位置，该位置之后的元素为已排序状态，下一轮的交换只需执行到该处。容易看出此优化包含了提前结束优化。

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        if(nums.size() < 2) return nums;
        // 上一轮最后交换时的下标，即发生 swap(num[i],nums[i+1]) 时的 i;
        int lastswappedIdx = nums.size()-1;
        // 若上一轮最后交换的下标 > 0 ，继续
        while(lastswappedIdx > 0) {
            // 当前轮次发生交换的下标
            int curswappedIdx = 0;
            for(int i = 0; i < lastswappedIdx; ++ i) {
                if(nums[i] > nums[i+1]){
                    swap(nums[i],nums[i+1]);
                    curswappedIdx = i;   
                    //每次发生交换时，更新curswappedIdx,保证退出循环时，
                    //它是该轮循环最后一次发生交换时的下标，说明它后面的元素都已有序；
                }
            }
// 若当前轮次未发生交换，则 lastSwappedIdx = 0 ，则在下一次 while 判断时退出，
// 完成排序(提前结束)；
            lastswappedIdx = curswappedIdx;
        }
        return nums;
    }
};

算法特性
时间复杂度为$O(n^2)$、自适应排序 ：各轮“冒泡”遍历的数组长度(比较次数)依次为 $n - 1$ , $n - 2$ , $\cdots$ , $2$ , $1$ ，总和为 $\frac{(n - 1) n}{2}$ 。在引入 flag 优化后，最佳时间复杂度可达到 $O(n)$

在应用flag优化后，冒泡排序的比较次数与初始序列状态有关，如果初始序列有序的话一趟就可以结束排序，比较次数仅为$n-1$次，因为不用交换元素，因此元素移动次数为0；当序列为逆序时，比较次数则为$\frac{n(n-1)}{2}$次，交换次数也一样；在没有应用falg优化时，比较次数就与初始序列无关了，总是$\frac{n(n-1)}{2}$次；

空间复杂度为$O(1)$、原地排序：指针 $i$ , $j$ 使用常数大小的额外空间。
稳定排序：由于在“冒泡”中遇到相等元素不交换，因此稳定。
注意事项

【注】：

冒泡排序所产生的有序子序列一定是全局有序的(不同于插入排序)，每一趟排序都会将一个元素放到其最终应该在的位置。

冒泡排序也可以用于链表这种数据结构\ 可以试一下这题148. 排序链表，不过这题用冒泡会超时

7.4.2 快速排序¶

【注】：下面介绍的快排方法和王道的不同，属于hoare版本，即左右指针法

「快速排序 Quick Sort」是一种基于分治思想的排序算法，运行高效，应用广泛。

快速排序的核心操作是「哨兵划分」，其目标是：选择数组中的某个元素作为“基准数”，将所有小于基准数的元素移到其左侧，而大于基准数的元素移到其右侧。具体来说，哨兵划分的流程为：

选取数组最左端元素作为基准数，初始化两个指针 i 和 j 分别指向数组的两端。
设置一个循环，在每轮中使用 i（j）分别寻找第一个比基准数大（小）的元素，然后交换这两个元素。
循环执行步骤 2. ，直到 i 和 j 相遇时停止，最后将基准数交换至两个子数组的分界线。

哨兵划分完成后，原数组被划分成三部分：左子数组、基准数、右子数组，且满足“左子数组任意元素 $\leq$ 基准数 $\leq$ 右子数组任意元素”。因此，我们接下来只需对这两个子数组进行排序。

单趟动图：

step1–step3
step4—step6
step7—-step8

"快速排序的分治思想"

哨兵划分的实质是将一个较长数组的排序问题简化为两个较短数组的排序问题。

哨兵划分实现代码

/*哨兵划分*/
int partition(vector<int> &nums, int left, int right) {
    int i = left, j = right;
    //以nums[left]作为基准数pivot;
    while(i < j) {
        while(i < j && nums[j] >= nums[left])
            j--;  //从右往左找第一个小于基准值的元素；
        while(i < j && nums[i] <= nums[left]) 
            i++;  //从左往右找第一个大于基准值的元素；
        swap(nums[i], nums[j]);  //交换这两个元素；
    }
    swap(nums[left],nums[i]);  //将基准数交换至两个子数组的分界线；
    return i;  //返回基准数pivot的索引；
}

哨兵划分中“从右往左查找”与“从左往右查找”的顺序可以交换吗？

不行，当我们以最左端元素为基准数时，必须先“从右往左查找”再“从左往右查找”。这个结论有些反直觉，我们来剖析一下原因。

哨兵划分 partition() 的最后一步是交换 nums[left] 和 nums[i] 。完成交换后，基准数左边的元素都 <= 基准数，这就要求最后一步交换前nums[left] >= nums[i]必须成立。假设我们先“从左往右查找”，那么如果找不到比基准数更小的元素，则会在i == j时跳出循环，此时可能nums[j] == nums[i] > nums[left]。也就是说，此时最后一步交换操作会把一个比基准数更大的元素交换至数组最左端，导致哨兵划分失败。

举个例子，给定数组 [0, 0, 0, 0, 1] ，如果先“从左向右查找”，哨兵划分后数组为 [1, 0, 0, 0, 0] ，这个结果是不正确的。

再深入思考一下，如果我们选择 nums[right] 为基准数，那么正好反过来，必须先“从左往右查找”。

算法流程
首先，对原数组执行一次「哨兵划分」，得到未排序的左子数组和右子数组。
然后，对左子数组和右子数组分别递归执行「哨兵划分」。
持续递归，直至子数组长度为 1 时终止，从而完成整个数组的排序。

void quickSort(vector<int>&nums,int left,int right) {
    //子数组长度为1时终止递归
    if(left >= right) return;
    //哨兵划分
    int pivot = partition(nums,left,right);
    //递归左子数组、右子数组
    quickSort(nums,left,pivot-1);
    quickSort(nums,pivot+1,right);
}

算法特性
时间复杂度$O(n \log n)$、自适应排序 ：在平均情况下，哨兵划分的递归层数为$\log n$ ，每层中的总循环数为$n$ ，总体使用 $O(n \log n)$ 时间。在最差情况下，即正序或倒序，每轮哨兵划分操作都将长度为 $n$ 的数组划分为长度为 $0$ 和 $n - 1$ 的两个子数组，此时递归层数达到 $n$ 层，每层中的循环数为 $n$ ，总体使用 $O(n^2)$ 时间.

快速排序的递归次数(层数)与初始序列的状态有关，与分区处理顺序无关。快排的每一趟需要对划分的各分区都递归执行一次快速排序，因此快排的趟数和递归层数挂钩，自然也与初始序列状态有关。

空间复杂度$O(n)$、原地排序 ：在输入数组完全倒序的情况下，达到最差递归深度$n$ ，使用 $O(n)$栈帧空间。排序操作是在原数组上进行的，未借助额外数组。
非稳定排序：在哨兵划分的最后一步，基准数可能会被交换至相等元素的右侧。

执行 $partition$ 方法确定了主轴位置后，将一开始设置的主轴元素与最后一个小于主轴的元素 $x$ 交换时，若中间有与 $x$ 同值的元素，则稳定性被破坏。

例：7 2 4 4 8 9

7 为主轴元素，$partition$ 过后交换 7 和第二个 4 ，则两个 4 的位置关系发生变化。

王道书的快排方法：挖坑法

思路：挖坑法思路与hoare版本(左右指针法)思路类似

选出一个数据（一般是最左边或是最右边的）存放在key变量中，在该数据位置形成一个坑

还是定义一个L和一个R，L从左向右走，R从右向左走。（若在最左边挖坑，则需要R先走；若在最右边挖坑，则需要L先走）

后面的思路与hoare版本(左右指针法)思路类似在此处就不说了

单趟动图如下：

代码：

void QuickSort1(int* arr, int begin, int end)
{
    if (begin >= end)
        return;
    int left = begin,right = end;
    int key = arr[begin];
    while (begin < end)
    {
        //找小
        while (arr[end] >= key && begin < end)
        {
            --end;
        }
        //小的放到左边的坑里
        arr[begin] = arr[end];
        //找大
        while (arr[begin] <= key && begin < end)
        {
            ++begin;
        }
        //大的放到右边的坑里
        arr[end] = arr[begin];
    }
    arr[begin] = key;
    int keyi = begin;
    //[left,keyi-1]keyi[keyi+1,right]
    QuickSort1(arr, left, keyi - 1);
    QuickSort1(arr, keyi + 1, right);
}

快排为什么快？

从名称上就能看出，快速排序在效率方面应该具有一定的优势。尽管快速排序的平均时间复杂度与「归并排序」和「堆排序」相同，但通常快速排序的效率更高，原因如下：

出现最差情况的概率很低：虽然快速排序的最差时间复杂度为 $O(n^2)$ ，没有归并排序稳定，但在绝大多数情况下，快速排序能在 $O(n \log n)$ 的时间复杂度下运行。
缓存使用效率高：在执行哨兵划分操作时，系统可将整个子数组加载到缓存（局部性原理），因此访问元素的效率较高。而像「堆排序」这类算法需要跳跃式访问元素，从而缺乏这一特性。
复杂度的常数系数低：在上述三种算法中，快速排序的比较、赋值、交换等操作的总数量最少。这与「插入排序」比「冒泡排序」更快的原因类似。
基准数优化

快速排序在某些输入下的时间效率可能降低。举一个极端例子，假设输入数组是完全倒序的，由于我们选择最左端元素作为基准数，那么在哨兵划分完成后，基准数被交换至数组最右端，导致左子数组长度为 $n - 1$ 、右子数组长度为 $0$ 。如此递归下去，每轮哨兵划分后的右子数组长度都为 $0$ ，分治策略失效，快速排序退化为「冒泡排序」。

为了尽量避免这种情况发生，我们可以优化哨兵划分中的基准数的选取策略。例如，我们可以随机选取一个元素作为基准数。然而，如果运气不佳，每次都选到不理想的基准数，效率仍然不尽如人意。

需要注意的是，编程语言通常生成的是“伪随机数”。如果我们针对伪随机数序列构建一个特定的测试样例，那么快速排序的效率仍然可能劣化。

为了进一步改进，我们可以在数组中选取三个候选元素（通常为数组的首、尾、中点元素），并将这三个候选元素的中位数作为基准数。这样一来，基准数“既不太小也不太大”的概率将大幅提升。当然，我们还可以选取更多候选元素，以进一步提高算法的稳健性。采用这种方法后，时间复杂度劣化至 $O(n^2)$ 的概率大大降低。

/* 选取三个元素的中位数并将其换到数组最左边 */
void medianThree(vector<int> &nums, int left, int right) {
    int mid = left + (right - left) / 2;
    if(nums[left] > nums[mid]) swap(nums[left],nums[mid]);  //左中比较，大者在中间
    if(nums[mid] > nums[right]) swap(nums[mid],nums[right]);  //中右比较，大者在右边
    if(nums[left] > nums[mid]) swap(nums[left],nums[mid]);  //左中比较，让中间值的元素在左边；
}

/* 哨兵划分（三数取中值） */
int partition(vector<int> &nums, int left, int right) {
    // 让三个元素的中位数换到最左边；
    medianThree(nums, left, right);
    // 以 nums[left] 作为基准数
    int i = left, j = right;
    while (i < j) {
        while (i < j && nums[j] >= nums[left])
            j--; // 从右向左找首个小于基准数的元素
        while (i < j && nums[i] <= nums[left])
            i++;          // 从左向右找首个大于基准数的元素
        swap(nums[i],nums[j]); // 交换这两个元素
    }
    swap(nums[i],nums[left]); // 将基准数交换至两子数组的分界线
    return i;            // 返回基准数的索引
}

尾递归优化

在某些输入下，快速排序可能占用空间较多。以完全倒序的输入数组为例，由于每轮哨兵划分后右子数组长度为 $0$ ，递归树的高度会达到 $n - 1$ ，此时需要占用 $O(n)$ 大小的栈帧空间。

为了防止栈帧空间的累积，我们可以在每轮哨兵排序完成后，比较两个子数组的长度，仅对较短的子数组进行递归。由于较短子数组的长度不会超过 $\frac{n}{2}$ ，因此这种方法能确保递归深度不超过 $\log n$ ，从而将最差空间复杂度优化至 $O(\log n)$ 。

void quickSort(vector<int> &nums, int left, int right) {
    // 子数组长度为 1 时终止
    while (left < right) {  //在递归完较短的子数组后，会重新计算一个新的 pivot ，再递归较短数组，以此类推…… 直至整个数组排序完成。
        // 哨兵划分操作
        int pivot = partition(nums, left, right);
        // 对两个子数组中较短的那个执行快排
        if (pivot - left < right - pivot) {
            quickSort(nums, left, pivot - 1); // 递归排序左子数组
            left = pivot + 1;                 // 剩余未排序区间为 [pivot + 1, right]
        } else {
            quickSort(nums, pivot + 1, right); // 递归排序右子数组
            right = pivot - 1;                 // 剩余未排序区间为 [left, pivot - 1]
        }
    }
}

关于尾递归优化，为什么选短的数组能保证递归深度不超过 $logn?$

递归深度就是当前未返回的递归方法的数量。每轮哨兵划分我们将原数组划分为两个子数组。在尾递归优化后，向下递归的子数组长度最大为原数组的一半长度。假设最差情况，一直为一半长度，那么最终的递归深度就是 $logn$。

回顾原始的快速排序，我们有可能会连续地递归长度较大的数组，最差情况下为$n,n-1,n-2,\cdots,2,1$从而递归深度为 $n$ 。尾递归优化可以避免这种情况的出现。

408【相关考题】

【例 1】下列选项中，不可能是快速排序第 2 趟排序结果的是（）

A. 2，3，5，4，6，7，9

B. 2，7，5，6，4，3，9

C. 3，2，5，4，7，6，9

D. 4，2，3，5，7，6，9

【解法一】第 i 趟排序完成后，会有 i 个或以上的数出现在它最终将要出现的位置，即它左边的数比它小，右边的数比它大。

由于题目问的是第 2 趟排序结果，因此分析每个选项能否找到两个或以上这样的数（符合的数被加粗），即它左边的数比它小，右边的数比它大。

A 项：2，3，5，4，6，7，9

B 项：2，7，5，6，4，3，9

C 项：3，2，5，4，7，6，9 （只找到一个）

D 项：4，2，3，5，7，6，9\ 所以选 C。

【解法二】由于第 i 趟排序完成后，会有 i 个或以上的数出现在它最终将要出现的位置，所以只需将最终的排序结果写出来，再跟每个选项进行对比，符合条件的结果应该有两个以上的元素相同（加粗）。

最终：2，3，4，5，6，7，9

A 项：2，3，5，4，6，7，9 （有 5 个相同）

B 项：2，7，5，6，4，3，9 （有 2 个相同）

C 项：3，2，5，4，7，6，9 （只有 1 个相同）

D 项：4，2，3，5，7，6，9 （有 2 个相同）\ 所以选 C。

【例 2】排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。下列序列中，不可能是快速排序第二趟结果的是（）

A. 5, 2, 16, 12, 28, 60, 32, 72

B. 2, 16, 5, 28, 12, 60, 32, 72

C. 2, 12, 16, 5, 28, 32, 72, 60

D. 5, 2, 12, 28, 16, 32, 72, 60

【解】由于第 i 趟排序完成后，会有 i 个或以上的数出现在它最终将要出现的位置，所以只需将最终的排序结果写出来，再跟每个选项进行对比，符合条件的结果应该有两个以上的元素相同（加粗）。

最终：2, 5, 12, 16, 28, 32, 60, 72

A 项：5, 2, 16, 12, 28, 60, 32, 72

B 项：2, 16, 5, 28, 12, 60, 32, 72

C 项：2, 12, 16, 5, 28, 32, 72, 60

D 项：5, 2, 12, 28, 16, 32, 72, 60

第一趟排序，确定一个元素位置，第二趟排序，又可以确定一个或两个元素位置。

当第一趟元素确认的位置为最左或最右时，第二趟排序只能确认一个位置（A，B 项）

当第一趟元素确认位置不是最左或最右时，第二趟能确认 2 个位置（C 项）\ 所以选 D。\ 【注】按以上思路分析例 1 的选项，发现均符合上述规律。

7.5 选择类排序¶

7.5.1 简单选择排序¶

每一趟在待排序元素中选取关键字最小(或最大)的元素加入有序子序列。

具体来说，「选择排序 Selection Sort」的工作原理非常直接：开启一个循环，每轮从未排序区间选择最小的元素，将其放到已排序区间的末尾。

设数组的长度为 $n$ ，选择排序的算法流程如下：

初始状态下，所有元素未排序，即未排序（索引）区间为 $[0, n-1]$ 。
选取区间 $[0, n-1]$ 中的最小元素，将其与索引 $0$ 处元素交换。完成后，数组前 1 个元素已排序。
选取区间 $[1, n-1]$ 中的最小元素，将其与索引 $1$ 处元素交换。完成后，数组前 2 个元素已排序。
以此类推。经过 $n - 1$ 轮选择与交换后，数组前 $n - 1$ 个元素已排序。
仅剩的一个元素必定是最大元素，无需排序，因此数组排序完成。\ 如下动图展示了 ${4,6,2,1,7,9,5,8,3}$ 的选择排序过程。

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();
        //外循环，执行n-1轮即可，当前未排序区间为[i,n-1];
        for(int i = 0; i < n - 1; ++i) {
            int minIdx = i;   //每一轮循环开始设置当前最小元素下标为i；
            //执行内循环，在区间[i,n-1]中找到最小元素的下标；
            for(int j = i + 1; j < n; ++j) {
                if(nums[j] < nums[minIdx]){
                    minIdx = j;  //如果当前遍历到的元素值更小，则更新最小元素下标；
                }
            }
            //内循环执行完后，如果最小元素下标发生改变，则交换二者将最小元素加入有序子序列；
            if(minIdx != i)  swap(nums[i],nums[minIdx]);
        }
        return nums;
    }
};

算法特性：

时间复杂度$O(n^2)$、非自适应排序：两层 $for$ 循环，第1轮比较 $n - 1$ 次，最后一轮比较 1 次，由于选择排序的比较次数与序列的初始状态无关，始终为$\frac{n(n-1)}{2}$次，因此时间复杂度为$O(n^2)$。但是，简单选择排序的元素交换次数很少，不会超过$n-1$次，因为每次都是找到了最终应该在的位置后才交换元素，因此是$O(n )$级别的.

由于交换涉及到swap，需要移动3次元素才能交换位置。

空间复杂度$O(1)$、原地排序：仅有指针$i,j$使用常数大小的额外空间
稳定性：不稳定，存在跨越交换。找到本轮次最小值后，将与本轮起始元素交换位置，此时若二者中间有与起始元素值相同的元素，交换后则打破了稳定性；

例:　7 7 2。第一轮交换第一个 7 和 2，则两个 7 位置关系改变。

【扩展】：双元选择优化

在遍历寻找最小值下标 $minIdx$ 时，可以同时寻找最大值下标 $maxIdx$ ，这样就可以一轮遍历确定两个元素的位置，遍历次数减少一半，但每轮次的操作变多，因此该优化 只能少量提升选择排序的速度 (复杂度介于单元选择排序复杂度及其一半之间，只有系数上的区别)。

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();
        for(int i = 0; i < n - 1 -i; ++i) {   //// 每轮确定两个数字，因此上界也会动态变化
            int minIdx = i, maxIdx = i;
            for(int j = i + 1; j < n - i; ++ j) {
                if(nums[j] < nums[minIdx]) minIdx = j;
                if(nums[j] > nums[maxIdx]) maxIdx = j;
            }
            if(minIdx == maxIdx) break;  
            // 若本轮最大值等于最小值，说明未排序部分所有元素相等，无需再排序
            swap(nums[i] ,nums[minIdx]);
            if(maxIdx == i) maxIdx = minIdx;
            // 在交换 i 和 minIdx 时，有可能出现 i 即 maxIdx 的情况，此时需要修改 maxIdx 为 minIdx
            swap(nums[n-1-i],nums[maxIdx]);
        }
        return nums;
    }
};

7.5.2 堆排序¶

7.5.2.1堆¶

摘自https://www.hello-algo.com/chapter_heap/heap/

「堆 Heap」是一种满足特定条件的完全二叉树，可分为两种类型：

「大顶堆 Max Heap」，任意节点的值 $\geq$ 其子节点的值。
「小顶堆 Min Heap」，任意节点的值 $\leq$ 其子节点的值。

堆作为完全二叉树的一个特例，具有以下特性：

最底层节点靠左填充，其他层的节点都被填满。
我们将二叉树的根节点称为「堆顶」，将底层最靠右的节点称为「堆底」。
对于大顶堆（小顶堆），堆顶元素（即根节点）的值分别是最大（最小）的。

堆的实现¶

下文实现的是大顶堆。若要将其转换为小顶堆，只需将所有大小逻辑判断取逆（例如，将 $\geq$ 替换为 $\leq$ ）。

堆的存储与表示

我们在二叉树章节中的顺序存储中学习到，完全二叉树非常适合用数组来表示。由于堆正是一种完全二叉树，我们将采用数组来存储堆。

当使用数组表示二叉树时，元素代表节点值，索引代表节点在二叉树中的位置。节点指针通过索引映射公式来实现。

具体而言，给定索引 $i$ ，其左子节点索引为 $2i + 1$ ，右子节点索引为 $2i + 2$ ，父节点索引为 $(i - 1) / 2$（向下取整）。当索引越界时，表示空节点或节点不存在。

(从下标为0处开始存储，王道课上是从下标为1处开始存储)

我们可以将索引映射公式封装成函数，方便后续使用。

/* 获取左子节点索引 */
int left(int i) {
    return 2 * i + 1;
}
/* 获取右子节点索引 */
int right (int i) {
    return 2 * i + 2;
}
/* 获取父节点索引 */
int parent(int i) {
    return (i - 1) / 2; // 向下取整
}

访问堆顶元素：堆顶元素就是二叉树的根结点，也就是列表中的首个元素；

int peek() {
    return maxHeap[0];
}

元素入堆

给定元素val,入堆时首先将其添加到堆底，即数组的末尾处。添加之后，由于val可能大于它的父节点等其他元素，堆的成立条件可能已被破坏。因此，需要修复从插入节点到根节点路径上的各个结点，这个操作被称为堆化(Heapify)

堆化实现步骤：从入堆结点开始，从底到顶执行堆化。具体来说，我们比较插入节点和它的父节点的值，如果插入结点值更大，则将它们交换。然后继续执行此操作，依次修复堆中的各个结点，直到越过根节点或遇到无需交换的结点时结束。

示意图：

//元素入堆；
void push(int val) {
    maxHeap.push_back(val); //添加结点到堆底（即数组末尾）；
    siftup(maxHeap.size() - 1); //从堆底开始向上堆化；
}
//从下标为i的结点开始，从底至顶堆化；
void siftup(int i) {  
    while(true) {
        int p = parent(i);  //p为i结点的父节点下标；
        if(p < 0 || maxHeap[i] < maxHeap[p]) //当“越过根节点”或者当前元素小于其父节点，结束堆化；
            break;
        swap(maxHeap[i],maxHeap[p]); //否则，交换该结点与其父节点；
        i = p; //循环往上堆化，直到结束；
    }
}

设结点总数为$n$,则树的高度为$logn$.由此可知，堆化操作的循环次数最多为$logn$轮，因此元素入堆的时间复杂度为$O(logn)$.

堆顶元素出堆

堆顶元素是二叉树的根节点，即列表首元素。如果直接从列表中删除该元素，那么二叉数中所有结点的索引都将发生变化，这将使得后序使用堆化修复变得困难。为了尽量减少元素索引的变动，我们一般采用下列步骤：

交换堆顶与堆底元素；（即交换根节点与完全二叉树的最右下叶结点）；
交换完成后，将堆底元素删除，此时删除的其实就是原来的堆顶元素；
从根节点开始，自顶至底执行堆化；

这里的堆化与从底至顶的堆化操作方向相反，我们将根节点的值与两个子节点的值进行对比，得出最大的那个元素的下标，然后交换两节点的值；再更新待堆化结点，循环执行该操作，直到越过叶节点或者当前结点比其两个子节点的值都大时，堆化结束。

如下动图展示了删除大顶堆 ${9, 8, 5, 6, 7, 2, 4, 1, 3}$ 堆顶元素 9 的过程（动图中出现的100表示堆顶，值为9）。

至此，堆化完成，最大堆的性质得以修复。

//元素出堆
void pop() {
    if(maxHeap.empty()){  //判空处理
        throw out_of_range("堆为空");  
    }
    swap(maxHeap[0],maxHeap[maxHeap.size()-1]);  //交换堆顶与堆底元素；（即根节点与最右下叶节点）
    maxHeap.pop_back();  //将堆底元素出堆，这里出堆的实际上就是之前的堆顶元素；
    siftDown(0);   //从顶向底开始堆化；
}
//从结点i开始，自顶向底堆化,即”下滤“；
void siftDown(int i) {  
    while(true) {
        //判断当前结点与其左右孩子结点谁最大，maxIdx为三个结点中最大的那个元素的下标；
        int l = left(i), r = right(i), maxIdx = i;   
        //如果当前结点比其孩子结点值都要大或者已经索引l,r都已经越界，说明堆化完成，堆的性质已经恢复；
        if(l < maxHeap.size() && maxHeap[l] > maxHeap[maxIdx])
            maxIdx = l;
        if(r < maxHeap.size() && maxHeap[r] > maxHeap[maxIdx])
            maxIdx = r;
        if(maxIdx == i) 
            break;
        swap(maxHeap[i],maxHeap[maxIdx]);  //将更大的那个子节点的值与当前结点交换；
        i = maxIdx;   //继续向下执行堆化；     
    }
}

与元素入堆操作类似，因此时间复杂度也为$Ologn$

建堆操作¶

如果我们想要根据输入列表生成一个堆，这个过程称为建堆。

建堆有两种方式

借助入堆方法实现

最直接的方法是借助“元素入堆操作”实现，首先，创建一个空堆，然后将列表元素依次添加到堆中，设元素数量为$n$,则最后一个元素入堆的时间复杂度为$O(logn)$,在依次添加元素时，堆的平均长度为$\frac{n}{2}$,因此这种建堆方式的总体时间复杂度为$O(nlogn)$

2021年真题考察的就是这种建堆操作，题目：将关键字$6,9,1,5,8,4,7$,依次插入到初始为空的大根堆H中，得到的H是？

基于堆化操作实现

这种建堆方法更高效，其时间复杂度仅为$O(n)$。我们先将列表中的元素原封不动的添加到堆中，然后迭代地对各个结点执行“从顶到底堆化“。当然，我们不需要对叶子节点执行堆化操作，因为它们没有子节点,故其本身已满足堆序性质，也就无下滤的必要 (也不会下滤)。

如下动图是将输入数组 ${4, 6, 2, 1, 7, 9, 5, 8, 3}$ (1为最后一个非叶子结点) 堆化成大顶堆 ${9, 8, 5, 6, 7, 2, 4, 1, 3}$ 的过程。

void createmaxHeap(vector<int> nums) {  
    maxHeap = nums;  //// 将列表元素原封不动添加进堆
    int n = maxHeap.size();
    // 堆化除叶节点以外的其他所有节点
    for(int i = parent(n-1); i >= 0; --i) {
        siftDown(i);
    }
}

第五句：这里的 $i$ 就是这棵完全二叉树的最后一个叶子结点的父节点，也是这棵树的最后一个非叶子结点，先将以该结点为根的子树执行自顶向底的堆化，然后向前依次对各子树执行堆化操作，直到根节点为止，从而使得这颗完全二叉树成为堆。

一句话总结堆化操作：对最后一个非叶子节点到根节点，依次执行下滤操作 ($siftDown$) 。

复杂度分析：

这部分内容不用掌握，知道结论即可；

为什么第二种建堆方法的时间复杂度是 $O(n)$ ？我们来展开推算一下。

完全二叉树中，设节点总数为 $n$ ，则叶节点数量为 $(n + 1) / 2$ ，其中 $/$ 为向下整除。因此，在排除叶节点后，需要堆化的节点数量为 $(n - 1)/2$ ，复杂度为 $O(n)$ 。

在从顶至底堆化的过程中，每个节点最多堆化到叶节点，因此最大迭代次数为二叉树高度 $O(\log n)$ 。

将上述两者相乘，可得到建堆过程的时间复杂度为 $O(n \log n)$ 。然而，这个估算结果并不准确，因为我们没有考虑到二叉树底层节点数量远多于顶层节点的特性。

接下来我们来进行更为详细的计算。为了减小计算难度，我们假设树是一个“完美二叉树”，该假设不会影响计算结果的正确性。设二叉树（即堆）节点数量为 $n$ ，树高度为 $h$ 。上文提到，节点堆化最大迭代次数等于该节点到叶节点的距离，而该距离正是“节点高度”

因此，我们可以将各层的“节点数量 $\times$ 节点高度”求和，从而得到所有节点的堆化迭代次数的总和。

$ T(h) = 2^0h + 2^1(h-1) + 2^2(h-2) + \cdots + 2^{(h-1)}\times1 $

化简上式需要借助中学的数列知识，先对 $T(h)$ 乘以 $2$ ，得到

$ \begin{aligned} T(h) & = 2^0h + 2^1(h-1) + 2^2(h-2) + \cdots + 2^{h-1}\times1 \newline 2 T(h) & = 2^1h + 2^2(h-1) + 2^3(h-2) + \cdots + 2^{h}\times1 \newline \end{aligned} $

使用错位相减法，令下式 $2 T(h)$ 减去上式 $T(h)$ ，可得

$ 2T(h) - T(h) = T(h) = -2^0h + 2^1 + 2^2 + \cdots + 2^{h-1} + 2^h $

观察上式，发现 $T(h)$ 是一个等比数列，可直接使用求和公式，得到时间复杂度为

$ \begin{aligned} T(h) & = 2 \frac{1 - 2^h}{1 - 2} - h \newline & = 2^{h+1} - h - 2 \newline & = O(2^h) \end{aligned} $

进一步地，高度为 $h$ 的完美二叉树的节点数量为 $n = 2^{h+1} - 1$ ，易得复杂度为 $O(2^h) = O(n)$ 。以上推算表明，输入列表并建堆的时间复杂度为$O(n)$，非常高效。

`TOP-K`问题¶

leetcode上有类似面试题：面试题 17.14. 最小K个数

【2022年408真题】：现有 $n(n>100000)$ 个数保存在一维数组 $M$中，需要查找$M$中最小的$10$个数，请回答下列问题。

⑴ 设计一个完成上述查找任务的算法，要求平均情况下的比较次数尽可能少，简单描述其算法思想，不需要程序实现。

⑵ 说明你所设计的算法平均情况下的时间复杂度和空间复杂度。

解答：下面介绍的方法先从简单直接的开始，再介绍效率更高的算法。

方法一：利用选择排序的思想，我们可以进行$k$轮遍历，分别在每轮中提取第$1,2,\cdots,k$小的元素，然后交换到数组左边的有序子序列中，时间复杂度为$O(kn)$,因为本题中$k=10$,因此时间复杂度为$O(n)$,因为是原地排序，因此空间复杂度为$O(1)$

该方法只适用于$k<\<n$的情况，当$k$与$n$较为接近时，其时间复杂度趋近于$O(n^2)$.当$k=n$,时，这就是选择排序。

法二：对该数组进行排序，那么最左边$k$位的元素就是我们要找的元素，时间复杂度为$O(nlogn)$,这种方法”超额“完成任务了，因此效率不佳。
法三：堆，我们可以基于堆这种数据结构解决该问题，流程为

先在$M[1:10]$原地建造大顶堆，然后原地堆化调整；

遍历$M[11:n]$,将遍历到的每个元素$M[i]$与该大顶堆堆顶元素相比较，如果$M[i]$大于堆顶元素,什么都不要做，如果$M[i]$小于堆顶元素，则删除堆顶元素，将该元素入堆，并重新调整堆化为大顶堆；

遍历完成之后，该大顶堆中保存的就是最小的10个数。

为什么用大顶堆而不用小顶堆呢，因为该大顶堆每次删除的堆顶元素都是当前堆里面的元素中最大的，这样的话每次遍历就可以让更小的元素进入到堆里面，同时删除的也是原来堆内最大的元素；如果用小顶堆的话，堆顶是最小的元素，则达不到该效果，除非将该数组全部原地堆化，然后依次弹出堆顶元素，那样的话，时间复杂度就很高了，不如直接排序呢。

所以我们可以得出一个结论：找最大元素topk，用小顶堆；找最小的k个数，用大顶堆。

前10个元素原地建造大顶堆的时间复杂度为$O(10)$,即$O(1)$,然后执行了$n-10$次比较，假设执行了$n-10$次出堆入堆操作，那么该操作的时间复杂度为$O(n-10)log10=O(n)$

因为原地建堆，因此空间复杂度为$O(1)$.

另外，该方法适用于动态数据流的使用场景。在不断加入数据时，我们可以持续维护堆内的元素，从而实现最小k个元素的动态更新。

//基于堆查找数组中最小的k个元素
class Solution {
public:
vector<int> smallestK(vector<int>& arr, int k) {
        if (k <= 0) return {};  
        if (k >= static_cast<int>(arr.size())) return arr;  //避免k大于数组长度时越界；
        vector<int> vec(k, 0);
        priority_queue<int> Q;
        for (int i = 0; i < k; ++i) {
            Q.push(arr[i]);
        }
        for (int i = k; i < (int)arr.size(); ++i) {
            if (Q.top() > arr[i]) {
                Q.pop();
                Q.push(arr[i]);
            }
        }
        for (int i = 0; i < k; ++i) {
            vec[i] = Q.top();
            Q.pop();
        }
        return vec;
    }
};

若要找最小的$k$个元素的话，时间复杂度：$O(nlog⁡k)$，其中 $n$是数组 arr 的长度。由于大根堆实时维护前k小值，所以插入删除都是 O(logk)的时间复杂度，最坏情况下数组里 $n$ 个数都会插入，所以一共需要$O(nlogk)$的时间复杂度。

空间复杂度：$O(k)$，因为大根堆里最多$k$个数。

法四：利用快排思想

这个重要思想同样可以运用于2016年算法题！

由于题目仅要求返回最小$k$个元素，并没有要将它们排好顺序，因此，只需要将数组划分为最小的$k$个数和其他数字即可，而快速排序的哨兵划分即可完成此目标。

随便找个数，进行一轮快排
快排结束，进行数据划分，假设这个数属于第$t$个,
t==k,那么返回前$t$个就是我们要找的结果；
t>k,那么我们便将问题规模缩小到在前$t-1$个元素中找k个最小元素；
t<k,那么说明已经确定前面t个数属于我们要找的那k个数，但是第$t+1$到第$k$这些数还没确定，此时，问题规模缩小到从$t+1$到右边界找这剩下的$k-t$个数。

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        if (k <= 0) return {};
        if (k >= arr.size()) return arr;
        return quickSort(arr, k, 0, arr.size() - 1);
    }
private:
    vector<int> quickSort(vector<int>& arr, int k, int l, int r) {
        int i = l, j = r;
        while (i < j) {
            while (i < j && arr[j] >= arr[l]) j--;
            while (i < j && arr[i] <= arr[l]) i++;
            swap(arr[i], arr[j]);
        }
        swap(arr[i], arr[l]);
        if (i > k) return quickSort(arr, k, l, i - 1);
        if (i < k) return quickSort(arr, k, i + 1, r);
        vector<int> res;
        res.assign(arr.begin(), arr.begin() + k);
        return res;
    }
};

复杂度分析：本方法优化时间复杂度的本质是通过判断舍去了不必要的递归（哨兵划分）。

时间复杂度：$O(n)$,$n$为数组长度，对于长度为n的数组执行哨兵划分的时间复杂度为$O(n)$；每轮哨兵划分后根据$k和i$的大小关系选择递归，由于$i$分布的随机性，则向下递归的平均长度为$\frac{n}{2}$,因此平均情况下，哨兵划分操作一共有$n+\frac{n}{2}+\frac{n}{4}+\frac{n}{n}=\frac{n-\frac{1}{2}}{1-\frac{1}{2}}=2n-1$,即总体时间复杂度为$O(n)$

空间复杂度：划分函数的平均递归深度为$O(logn)$

堆在c++中的使用方法¶

堆通常用作实现优先队列，大顶堆相当于元素按从大到小顺序出队的优先队列。从使用角度来看，我们可以将「优先队列」和「堆」看作等价的数据结构。

/* 初始化堆 */
// 初始化小顶堆
priority_queue<int, vector<int>, greater<int>> minHeap;
// 初始化大顶堆
priority_queue<int, vector<int>, less<int>> maxHeap;

/* 元素入堆 */
maxHeap.push(1);
maxHeap.push(3);
maxHeap.push(2);
maxHeap.push(5);
maxHeap.push(4);

/* 获取堆顶元素 */
int peek = maxHeap.top(); // 5

/* 堆顶元素出堆 */
// 出堆元素会形成一个从大到小的序列
maxHeap.pop(); // 5
maxHeap.pop(); // 4
maxHeap.pop(); // 3
maxHeap.pop(); // 2
maxHeap.pop(); // 1

/* 获取堆大小 */
int size = maxHeap.size();

/* 判断堆是否为空 */
bool isEmpty = maxHeap.empty();

/* 输入列表并建堆 */
vector<int> input{1, 3, 2, 5, 4};
priority_queue<int, vector<int>, greater<int>> minHeap(input.begin(), input.end());

堆的小结¶

堆是一棵完全二叉树，根据成立条件可分为大顶堆和小顶堆。大（小）顶堆的堆顶元素是最大（小）的。

优先队列的定义是具有出队优先级的队列，通常使用堆来实现。

堆的常用操作及其对应的时间复杂度包括：元素入堆$O(\log n)$、堆顶元素出堆$O(\log n)$和访问堆顶元素$O(1)$等。

完全二叉树非常适合用数组表示，因此我们通常使用数组来存储堆。

堆化操作用于维护堆的性质，在入堆和出堆操作中都会用到。

输入$n$个元素并建堆的时间复杂度可以优化至$O(n)$，非常高效。

Top-K 是一个经典算法问题，可以使用堆数据结构高效解决，时间复杂度为 $O(n \log k)$ 。

7.5.2.2 堆排序¶

「堆排序Heap Sort」是一种基于堆数据结构实现的高效排序算法。我们可以利用已经学过的“建堆操作”和“元素出堆操作”实现堆排序：

输入数组并建立小顶堆，此时最小元素位于堆顶。
不断执行出堆操作，依次记录出堆元素，即可得到从小到大排序的序列。

以上方法虽然可行，但需要借助一个额外数组来保存弹出的元素，比较浪费空间。在实际中，我们通常使用一种更加优雅的实现方式。

算法流程：

设数组的长度为 $n$ ，堆排序的流程如下：

输入数组并建立大顶堆。完成后，最大元素位于堆顶。
将堆顶元素（第一个元素）与堆底元素（最后一个元素）交换。完成交换后，堆的长度减 $1$ ，已排序元素数量加 $1$ 。
从堆顶元素开始，从顶到底执行堆化操作（Sift Down）。完成堆化后，堆的性质得到修复。
循环执行第 2. 和 3. 步。循环 $n - 1$ 轮后，即可完成数组排序。

实际上，元素出堆操作中也包含第 2. 和 3. 步，只是多了一个弹出元素的步骤。

在代码实现中，我们使用了与堆章节相同的从顶至底堆化（SiftDown）的函数。值得注意的是，由于堆的长度会随着提取最大元素而减小，因此我们需要给 SiftDown 函数添加一个长度参数 $n$ ，用于指定堆的当前有效长度。

/* 堆的长度为 n ，从节点 i 开始，从顶至底堆化 */
void siftDown(vector<int> &nums, int n, int i) {
    while (true) {
        // 判断节点 i, l, r 中值最大的节点，记为 ma
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        int ma = i;
        if (l < n && nums[l] > nums[ma])
            ma = l;
        if (r < n && nums[r] > nums[ma])
            ma = r;
        // 若节点 i 最大或索引 l, r 越界，则无需继续堆化，跳出
        if (ma == i) {
            break;
        }
        // 交换两节点
        swap(nums[i], nums[ma]);
        // 循环向下堆化
        i = ma;
    }
}

/* 堆排序 */
void heapSort(vector<int> &nums) {
    // 建堆操作：堆化除叶节点以外的其他所有节点
    for (int i = nums.size() / 2 - 1; i >= 0; --i) {
        siftDown(nums, nums.size(), i);
    }
    // 从堆中提取最大元素，循环 n-1 轮
    for (int i = nums.size() - 1; i > 0; --i) {
        // 交换根节点与最右叶节点（即交换首元素与尾元素）
        swap(nums[0], nums[i]);
        // 以根节点为起点，从顶至底进行堆化
        siftDown(nums, i, 0);
    }
}

算法特性

时间复杂度$O(n \log n)$、非自适应排序 ：建堆操作使用 $O(n)$ 时间。从堆中提取最大元素的时间复杂度为 $O(\log n)$ ，共循环 $n - 1$ 轮。
空间复杂度$O(1)$、原地排序 ：几个指针变量使用 $O(1)$ 空间。元素交换和堆化操作都是在原数组上进行的。
非稳定排序：在交换堆顶元素和堆底元素时，相等元素的相对位置可能发生变化。

例：输入数组 ${1, 2_{red}, 2_{green}}$ ，灰色表示已排序。排序后最终为 ${1, 2_{green}, 2_{red}}$ ,可以看到 $2_{red}$ 和 $2_{green}$ 的相对顺序相比输入已改变。

7.6 二路归并排序¶

「归并排序 Merge Sort」基于分治思想实现排序，包含“划分”和“合并”两个阶段：

划分阶段：通过递归不断地将数组从中点处分开，将长数组的排序问题转换为短数组的排序问题。
合并阶段：当子数组长度为 1 时终止划分，开始合并，持续地将左右两个较短的有序数组合并为一个较长的有序数组，直至结束。 \ 算法流程\ “划分阶段”从顶至底递归地将数组从中点切为两个子数组：
计算数组中点 mid ，递归划分左子数组（区间 [left, mid] ）和右子数组（区间 [mid + 1, right] ）。
递归执行步骤 1. ，直至子数组区间长度为 1 时，终止递归划分。

“合并阶段”从底至顶地将左子数组和右子数组合并为一个有序数组。需要注意的是，从长度为 1 的子数组开始合并，合并阶段中的每个子数组都是有序的。\ aHR0cDovL3d3dy5jeHl4aWFvd3UuY29tL3dwLWNvbnRlbnQvdXBsb2Fkcy8yMDE5LzEwLzE1NzEwNTgyODEtNDFiNGMzYjk5N2FmMmNhLmdpZg.gif 如下树状图中的橙色线表示递归的轨迹（自顶向下递归归并排序）。

观察发现，归并排序的递归顺序与二叉树的后序遍历相同，具体来看：

后序遍历：先递归左子树，再递归右子树，最后处理根节点。
归并排序：先递归左子数组，再递归右子数组，最后处理合并。

class Solution {
public:
    /* 合并左子数组和右子数组 */
    // 左子数组区间 [left, mid]
    // 右子数组区间 [mid + 1, right]
    void merge(vector<int> &nums, int left,int mid, int right) {
        vector<int>tmp(nums.begin()+left,nums.begin()+right+1);   // 初始化辅助数组
        int leftstart = left - left, leftend = mid - left;        // 左子数组的起始索引和结束索引
        int rightstart = mid + 1 - left, rightend = right - left; // 右子数组的起始索引和结束索引
        int i = leftstart, j = rightstart;                        // i, j 分别指向左子数组、右子数组的首元素
        for(int k = left; k <= right; k++) {                      // 通过覆盖原数组 nums 来合并左子数组和右子数
            if(i > leftend) nums[k] = tmp[j++];                   // 若“左子数组已全部合并完”，则选取右子数组元素，并且 j++
            else if(j > rightend || tmp[i] < tmp[j]) nums[k] = tmp[i++]; 
            // 否则，若“右子数组已全部合并完”或“左子数组元素 <= 右子数组元素”，则选取左子数组元素，并且 i++
            else nums[k] = tmp[j++];
            // 否则，若“左右子数组都未全部合并完”且“左子数组元素 > 右子数组元素”，则选取右子数组元素，并且 j++
        }
    }
    /* 归并排序 */
    void mergesort(vector<int>&nums,int left,int right) {
        if(left >= right) { // 终止条件
            return;         // 当子数组长度为 1 时终止递归
        }
        int mid = left + (right - left) / 2;   // 计算中点
        mergesort(nums,left,mid);              // 递归左子数组
        mergesort(nums,mid+1,right);           // 递归右子数组
        merge(nums,left,mid,right);            // 合并阶段
    }
    vector<int> sortArray(vector<int>& nums) {
        mergesort(nums,0,nums.size() -1);
        return nums;
    }
};

合并方法 merge() 代码中的难点包括：

在阅读代码时，需要特别注意各个变量的含义。nums 的待合并区间为 [left, right] ，但由于 tmp 仅复制了 nums 该区间的元素，因此 tmp 对应区间为 [0, right - left] 。

在比较 tmp[i] 和 tmp[j] 的大小时，还需考虑子数组遍历完成后的索引越界问题，即 i > leftEnd 和 j > rightEnd 的情况。索引越界的优先级是最高的，如果左子数组已经被合并完了，那么不需要继续比较，直接合并右子数组元素即可。

算法特性

时间复杂度$O(n \log n)$、非自适应排序 ：划分产生高度为 $\log n$ 的递归树，每层合并的总操作数量为 $n$ ，因此总体时间复杂度为 $O(n \log n)$ 。
空间复杂度$O(n)$、非原地排序 ：递归深度为 $\log n$ ，使用 $O(\log n)$ 大小的栈帧空间。合并操作需要借助辅助数组实现，使用 $O(n)$ 大小的额外空间。
稳定排序：在合并过程中，相等元素的次序保持不变。

链表排序

归并排序在排序链表时具有显著优势，空间复杂度可以优化至 $O(1)$ ，原因如下：

由于链表仅需改变指针就可实现节点的增删操作，因此合并阶段（将两个短有序链表合并为一个长有序链表）无需创建辅助链表。
通过使用“迭代划分”替代“递归划分”，可省去递归使用的栈帧空间。

y总归并模板 acwing归并排序

void merge_sort(vector<int>&q, int l, int r)
{
    vector<int>tmp(r-l+1); 
    //递归的终止情况
    if(l >= r) return;

    //第一步：分成子问题
    int mid = l + r >> 1;

    //第二步：递归处理子问题
    merge_sort(q, l, mid ), merge_sort(q, mid + 1, r);

    //第三步：合并子问题
    int k = 0, i = l, j = mid + 1, tmp[r - l + 1];
    while(i <= mid && j <= r)
        if(q[i] <= q[j]) tmp[k++] = q[i++]; //将当前最小的放入备用数组.
        else tmp[k++] = q[j++];
    while(i <= mid) tmp[k++] = q[i++];
    while(j <= r) tmp[k++] = q[j++];

    for(k = 0, i = l; i <= r; k++, i++) q[i] = tmp[k];
}

前述的几种排序算法都属于“基于比较的排序算法”，它们通过比较元素间的大小来实现排序。此类排序算法的时间复杂度无法超越$O(n \log n)$。接下来，我们将探讨几种“非比较排序算法”，它们的时间复杂度可以达到线性阶。

基于比较的排序算法的下界:

决策树模型在排序算法分析中是一个重要的概念，它帮助我们理解基于比较的排序算法所需的最小比较次数。在排序算法的上下文中，决策树是一个完全二叉树，其中每个节点代表一个比较操作，每个叶子节点代表输入数组的一个可能的排列。

节点和路径：
树中的每个非叶子节点表示一次比较操作，即决定了接下来应该走哪条路径（即二叉决策树的左或右分支）, 节点的两个分支对应比较结果的两种可能性（例如，对于排序算法，可能是“元素 A 大于元素 B”和“元素 A 小于等于元素 B”）。
决策树中每个叶结点表示一个最终排序序列，由$n$个元素组成的数组有$n!$种排列，对应$n!$个叶结点，每个叶结点都是可从根结点开始的某条路径到达的（称该叶结点可达(reachable) ），该路径对应一连串排序比较的过程
树的高度：决策树的高度代表在最坏情况下所需的最大比较次数。因为决策树是完全二叉树，对于有$n!$个叶子节点的树（代表$n$个元素的所有可能排列），它的高度至少是 ($\lceil \log_2(n!) \rceil$)。

设决策树高度为$h$，叶结点个数为$l$, 则$n!≤l≤2^h$，故$h≥log⁡_2(n!)$。

斯特林近似：使用斯特林公式$n! \approx \sqrt{2\pi n} (\frac{n}{e})^n$近似，可以得到$\log_2(n!)$的简化估计，进一步证实$\Omega(n \log n)$的下界。

7.7 非比较排序¶

7.7.1 计数排序【2021】¶

简单（朴素）实现¶

先来看一个简单的例子。给定一个长度为 $n$ 的数组 nums ，其中的元素都是“非负整数”。计数排序的整体流程如下：

遍历数组，找出数组中的最大数字，记为 $m$ ，然后创建一个长度为 $m + 1$ 的辅助数组 counter 。
借助counter统计nums中各数字的出现次数，其中 counter[num] 对应数字 num 的出现次数。统计方法很简单，只需遍历 nums（设当前数字为 num），每轮将 counter[num] 增加 $1$ 即可。
由于counter的各个索引天然有序，因此相当于所有数字已经被排序好了。接下来，我们遍历 counter ，根据各数字的出现次数，将它们按从小到大的顺序填入 nums 即可。

实现代码：

/* 计数排序 */
// 简单实现，无法用于排序对象
void countingSortNaive(vector<int> &nums) {
    // 1. 统计数组最大元素 m
    int m = 0;
    for (int num : nums) {
        m = max(m, num);
    }
    // 2. 统计各数字的出现次数
    // counter[num] 代表 num 的出现次数
    vector<int> counter(m + 1, 0);
    for (int num : nums) {
        counter[num]++;
    }
    // 3. 遍历 counter ，将各元素填入原数组 nums
    int i = 0;
    for (int num = 0; num < m + 1; num++) {
        for (int j = 0; j < counter[num]; j++, i++) {
            nums[i] = num;
        }
    }
}

"计数排序与桶排序的联系"

从桶排序的角度看，我们可以将计数排序中的计数数组 counter 的每个索引视为一个桶，将统计数量的过程看作是将各个元素分配到对应的桶中。本质上，计数排序是桶排序在整型数据下的一个特例。

稳定性优化¶

朴素做法有两个明显的缺陷：

无法处理负数。
空间冗余。当元素个数较多，但很多相等元素使得元素分布 集中在较小范围 时，$m+1$ 大小的 $counter$ 中大部分空间是多余的。改进方法很简单，即创建大小为 $max - min + 1$ 的 $counter$ ，$max$ 和 $min$ 分别是 $arr$ 中最大和最小元素。后续代码将采用该改进。

另外，未经优化的计数排序 不稳定 。通过计数来排序，当遍历 $counter[i]$ 输出排序结果时，只是连续地输出 $counter[i]$ 次 $i + min$ ，稳定性得不到保证 (比如后放入的 1 会先输出) 。要保证稳定，必须使 先记录的先输出。可以通过对 $counter$ 变形来满足稳定性，使得遍历到同一个数字，例如 $k$ 时，能够将不同位置的 $k$ 按他们在 $nums$ 中出现的顺序放入到输出数组中。具体做法如下。

得到 $counter$ 后，遍历一次 $counter$ ，使得每一个 $counter[i]$ 的值都是从 $counter[0]$ 到 $counter[i]$ 中值不为 0 的项的值之和（前缀和）。例如对于待排序数组 ${5, 5, 4, 4, 1, 1}$ ，得到大小为 5 - 1 + 1 = 5 的 $counter$ ，具体为 ${2, 0, 0, 2, 2}$ ，表示有两个1，0个2，0个3，2个4，2个5。按照前述方法将其变形为 ${2, 0, 0, 4, 6}$ ，表示 1 的最大位置为第 2 位 (下标为1)， 4 的最大位置为 4 (下标为 3 )， 5 的最大位置为 6 (下标为 5 )。
在输出排序结果时，新建一个大小等于 $nums$的 $sortednums$ 数组，于是 $counter[nums[i] - min] - 1$ 即为 $nums[i]$ 这个数应当放入 $sortednums$ 的位置(下标)，即 $sortednums[counter[nums[i] - min] - 1] = nums[i]$ ，以倒序从 $nums.size()$ 遍历到 0 ，每次向 $sortednums$ 填入一个数字后，令 $counter[nums[i] - min]--$ 。遍历结束后得到的 $sortednums$ 即为 $nums$ 的稳定排序结果 (建议实际动手验证这个过程) 。

int countingSort(vector<int> &nums) {
    if(nums.size() < 2) return nums;
    int n = nums.size(), Min = nums[0], Max = nums[0];
    for(int i = 1; i < n; ++i) {  // 确定 Min 和 Max
        Min = min(Min,nums[i]);
        Max = max(Max,nums[i]);        
    }
    vector<int> counter(Max - Min + 1,0);  //nums最多有Max-Min+1种数字,全部初始化为0；
    for(int i = 0; i < n; ++i) {    //计数
        counter[nums[i] - Min] ++;   // nums[i] 的值出现一次，则 countArr[nums[i]-min] 加 1
    }
    for(int i = 1; i < counter.size(); ++i) {  //计算前缀和；
        counter[i] += counter[i-1];
    }
    vector<int> sortednums(n);    // 根据 sortednums, nums, counter 三者关系完成 sortednums 的输出
    for(int i = n - 1; i >= 0; -- i) {   // 逆序输出保持稳定性
        int countIdx = nums[i] - Min;   // nums[i] 元素对应 counter 中的下标
        int sortIdx = counter[countIdx] - 1;  // 在排序后数组中的下标
        sortednums[sortIdx] = nums[i];   // 在排序后数组中填入值
        counter[countIdx]--;   // counter[countIdx] 已排序一位，下一个该位置的数的排位要靠前一位
    }
    return sortednums;
}

复杂度分析：时间复杂度：朴素版为 $O(max)$，$max$ 为原数组中最大值。改进版涉及到遍历$nums$和$counter$,因此时间复杂度为 $O(n + k)$，$n$ 为元素个数， $k$ 计数数组大小。当元素个数较少但最大最小值差值很大时，复杂度取决于 $k$ 。

空间复杂度：不考虑输入数组 $nums$ ，朴素版的 $counter$ 的大小为 $k+1$ ，故空间复杂度为 $O(k)$。稳定性优化版为 $O(n + k)$， $n$ 为 $sortednums$ 的大小，等于 $nums$ 的大小。

稳定排序：由于向 sortednums 中填充元素的顺序是“从右向左”的，因此倒序遍历 nums 可以避免改变相等元素之间的相对位置，从而实现稳定排序。实际上，正序遍历 nums 也可以得到正确的排序结果，但结果是非稳定的。

局限性¶

看到这里，你也许会觉得计数排序非常巧妙，仅通过统计数量就可以实现高效的排序工作。然而，使用计数排序的前置条件相对较为严格。

普通的计数排序只适用于非负整数，即使改进后可以适用于负整数，但是仍然只适用于整数。

计数排序适用于数据量大但数据范围较小的情况。比如，在上述示例中 $max- min+1$ 不能太大，否则会占用过多空间。而当 $n \ll (max-min+1)$ 时，计数排序使用 $O(max-min+1)$ 时间，可能比 $O(n \log n)$ 的排序算法还要慢。不过在力扣上测试效果还是蛮好的，执行用时超过了97%的提交。

7.7.2 基数排序¶

该算法一般只会在选择题中考察

算法描述¶

非比较排序，「基」指的是数的位，例如十进制数 123，共有百十个位，共 3 「位」。基数排序 按数字的位进行循环，每一轮操作都是对当前位 (基数) 的计数排序，使得输出到 $arr$ 后所有数字在截止到当前位上 (即去掉未考察的位后) 是排序状态，考察完最大位后完成排序。具体过程如下：

求最大位。遍历待排序数组 $arr$ ，找到绝对值最大的数字，计算其位数 (称其为宽度 $width$ )，例如 $arr$ 中最大数为 123 ，则 $width = 3$ 。
数组的数字为 $n$ 进制，就创建大小为 $n$ 的计数数组 $countArr$ ，也可以称为 $n$ 个桶。
开始针对「位」的 $for$ 循环，循环次数等于 $width$ ，每一轮对 当前所有数字的当前位 执行一次 计数排序。
每次计数排序结束后将结果写回 $arr$ 。
$for$ 循环结束后返回排序结果 $arr$ 。

如下动图演示 ${6674, 1560, 5884, 2977, 2922, 4127, 5390, 7870, 1193, 7163}$ 的基数排序过程。

稳定性：稳定。

基数排序要求对每一位的排序 (计数排序或非计数排序) 必须是稳定排序，否则无法得到正确结果。例如对 ${25,13,24}$ 执行排序。第一轮针对个位的排序过后得到 ${13,24,25}$ ，若对位的排序不稳定，则第二轮针对十位上的 ${1,2,2}$ 的排序将可能得到 ${13,25,24}$ ，排序结束得到错误结果。基于稳定的位排序 (例如稳定的计数排序) 的基数排序，也一定是稳定的。

补充:最低位不受该限制，最低位用不稳定排序算法也没有影响

处理负数优化

若存在负数，可以先找到最小值 (负数) ，对 $arr$ 中的每个数，都加上此最小值的绝对值，排序完成后再减回去。但加法可能使得 数字越界，一种更好的办法是计数排序时将$countArr$的大小扩展为 19，以 $[0, 19]$ 对应可能出现的 $[-9, 9]$ 。因此在每轮求当前基数时，要在原基数结果上 +9 以对应 $countArr$ 的下标。

复杂度分析

时间复杂度：

$d$ 为绝对值最大的元素位数，总共进行 $d$ 轮计数排序，$O(n+k)$ 是计数排序的复杂度，其中 $k$ 是位的取值范围(即$k$进制)，如果是非负数，则 $k=10(0\sim 9)$，如果包含负数，则 $k=19(-9 \sim 9)$ 。所以总的时间复杂度为 $O(d(n+k))$。

空间复杂度：

利用计数排序的基数排序，空间复杂度与计数排序相同，为 $O(n + k)$。

为实现多关键字排序，通常有两种方法：第一种是最高位优先(MSD)法，按关键字位权重递减依次逐层划分为若干更小的子序列，最后将所有子序列依次连接成一个有序序列。第二种是最低位优先(LSD)法，按关键字权重递增依次进行排序，最后形成一个有序序列。不过，一般来说，都是从最低位开始排序：

在连续的排序轮次中，后一轮排序会覆盖前一轮排序的结果。举例来说，如果第一轮排序结果$a < b$，而第二轮排序结果$a > b$，那么第二轮的结果将取代第一轮的结果。由于数字的高位优先级高于低位，我们应该先排序低位再排序高位。

LSD 基数排序示例图：
若底层排序算法不稳定，采用基数排序算法后（）(2020年912)\ A.未必正确并且不稳定\ B.正确并且不稳定\ C.未必正确并且稳定\ D.正确并且稳定

选 A

基数排序的正确性依赖于对每个域分别排序时的稳定性，只有每个域的排序算法都是稳定的，才能保证最后的基数排序是正确且稳定的，否则就不一定正确，更何其谈稳定性呢。

算法流程及代码

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

// 定义链表节点结构
typedef struct Node {
  int data;
  struct Node* next;
} Node;

// 找到数字的最大位数(...、千、百、十、个)
int getMaxDigits (int arr[], int n) {
  // 默认最大值为第0个元素
  int maxNum = arr[0];
  // 找到数组中的最大值
  for (int i = 1; i < n; i++) {
    if (arr[i] > maxNum) {
      maxNum = arr[i];
    }
  }

  int digits = 0;
  // 计算最大的位数
  while (maxNum > 0) {
    maxNum /= 10;
    digits++;
  }

  return digits;
}

// 将数字插入到链表中
void insert (Node ** head, int data) {
  // 分配新节点内存并设置其数据和下一个节点指针为NUL
  Node* newNode = (Node*)malloc(sizeof(Node));
  newNode->data = data;
  newNode->next = NULL;

  if (!(*head)) {
    // 如果链表为空，将新节点作为头节点
    *head = newNode;
  } else {
    // 否则，找到链表的末尾，然后将新节点链接到末尾
    struct Node* current = *head;
    // 这里也可以使用头尾指针的方式，就避免循环找尾节点
    while (current->next) {
      current = current->next;
    }
    current->next = newNode;
  }
}

// 通过遍历链表，依次取出节点的数据，将数据存入数组，然后释放节点的内存
void extract(Node **head, int arr[], int *index) {
  while (*head) {
    // 保存当前头节点的指针
    Node* temp = *head;
    // 将头节点的数据存入数组
    arr[(*index)++] = (*head)->data;
    // 移动头节点到下一个节点
    *head = (*head)->next;
    // 释放先前的头节点的内存
    free(temp);
  }
}

// 基数排序
void Radix_Sort (int arr[], int n) {
  int maxDigits = getMaxDigits(arr, n);

  // 创建10个链表，用于存放每个位上的数字
  Node *Q[10] = {NULL};

  for (int digit = 1; digit <= maxDigits; digit++) {
    // 【分配】将数组中的元素分配到链表中
    for (int i = 0; i < n; i++) {
      // 取出当前的位数，找出0-9对应的链表
      int linkIndex = (arr[i] / (int)pow(10, digit - 1)) % 10;
      insert(&Q[linkIndex], arr[i]);
    }

    // 【收集】从桶中取回元素并重新排列数组
    int index = 0;
    for (int i = 0; i < 10; i++) {
      extract(&Q[i], arr, &index);
    }
  }

  // 释放内存
  for (int i = 0; i < 10; i++) {
    while (Q[i]) {
      Node *temp = Q[i];
      Q[i] = Q[i]->next;
      free(temp);
    }
  }
}

int main() {
  int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
  int n = sizeof(arr) / sizeof(arr[0]);

  Radix_Sort(arr, n);
  printf("归并排序结果：");
  for (int i = 0; i < n; i++) {
      printf("%d ", arr[i]);
  }

  return 0;
}

7.7.3 桶排序¶

「桶排序 Bucket Sort」是分治思想的一个典型应用。它通过设置一些具有大小顺序的桶，每个桶对应一个数据范围，将数据平均分配到各个桶中；然后，在每个桶内部分别执行排序；最终按照桶的顺序将所有数据合并。

算法流程¶

考虑一个长度为 $n$ 的数组，元素是范围 $[0, 1)$ 的浮点数。桶排序的流程如下：

初始化 $k$ 个桶，将 $n$ 个元素分配到 $k$ 个桶中。
对每个桶分别执行排序（本文采用编程语言的内置排序函数）。
按照桶的从小到大的顺序，合并结果。

这个结构类似于链式地址实现的哈希表

/* 桶排序 */
void bucketSort(vector<float> &nums) {
    // 初始化 k = n/2 个桶，预期向每个桶分配 2 个元素
    int k = nums.size() / 2;
    vector<vector<float>> buckets(k);
    // 1. 将数组元素分配到各个桶中
    for (float num : nums) {
        // 输入数据范围 [0, 1)，使用 num * k 映射到索引范围 [0, k-1]
        int i = num * k;
        // 将 num 添加进桶 bucket_idx
        buckets[i].push_back(num);
    }
    // 2. 对各个桶执行排序
    for (vector<float> &bucket : buckets) {
        // 使用内置排序函数，也可以替换成其他排序算法
        sort(bucket.begin(), bucket.end());
    }
    // 3. 遍历桶合并结果
    int i = 0;
    for (vector<float> &bucket : buckets) {
        for (float num : bucket) {
            nums[i++] = num;
        }
    }
}

"桶排序的适用场景是什么？"

桶排序适用于处理体量很大的数据。例如，输入数据包含 100 万个元素，由于空间限制，系统内存无法一次性加载所有数据。此时，可以将数据分成 1000 个桶，然后分别对每个桶进行排序，最后将结果合并。

算法特性¶

时间复杂度$O(n + k)$ ：假设元素在各个桶内平均分布，那么每个桶内的元素数量为 $\frac{n}{k}$ 。假设排序单个桶使用 $O(\frac{n}{k} \log\frac{n}{k})$ 时间，则排序所有桶使用 $O(n \log\frac{n}{k})$ 时间。当桶数量$k$比较大时，时间复杂度则趋向于$O(n)$ 。合并结果时需要遍历所有桶和元素，花费 $O(n + k)$ 时间。
自适应排序：在最坏情况下，所有数据被分配到一个桶中，且排序该桶使用 $O(n^2)$ 时间。
空间复杂度$O(n + k)$、非原地排序 ：需要借助 $k$ 个桶和总共 $n$ 个元素的额外空间。
桶排序是否稳定取决于排序桶内元素的算法是否稳定。

如何实现平均分配¶

桶排序的时间复杂度理论上可以达到 $O(n)$ ，关键在于将元素均匀分配到各个桶中，因为实际数据往往不是均匀分布的。例如，我们想要将淘宝上的所有商品按价格范围平均分配到 10 个桶中，但商品价格分布不均，低于 100 元的非常多，高于 1000 元的非常少。若将价格区间平均划分为 10 份，各个桶中的商品数量差距会非常大。

为实现平均分配，我们可以先设定一个大致的分界线，将数据粗略地分到 3 个桶中。分配完毕后，再将商品较多的桶继续划分为 3 个桶，直至所有桶中的元素数量大致相等。这种方法本质上是创建一个递归树，使叶节点的值尽可能平均。当然，不一定要每轮将数据划分为 3 个桶，具体划分方式可根据数据特点灵活选择。

如果我们提前知道商品价格的概率分布，则可以根据数据概率分布设置每个桶的价格分界线。值得注意的是，数据分布并不一定需要特意统计，也可以根据数据特点采用某种概率模型进行近似。如下图所示，我们假设商品价格服从正态分布，这样就可以合理地设定价格区间，从而将商品平均分配到各个桶中。

7.8 外部排序¶

上面介绍的算法都属于内部排序算法，即排序的整个过程只是在内存中完成。而当待排序的文件比内存的可使用容量还大时，文件无法一次性放到内存中进行排序，需要借助于外部存储器（例如硬盘、U盘、光盘），这时就需要用到本章介绍的外部排序算法来解决。

7.8.1 外部排序步骤¶

外部排序算法由两个阶段构成

按照内存大小，将大文件分成若干长度为 L 的子文件（L应小于内存的可使用容量），然后将各个子文件依次读入内存，使用适当的内部排序算法对其进行排序（排好序的子文件统称为“初始归并段”或者“顺段”），将排好序的归并段重新写入外存，为下一个子文件排序腾出内存空间；
对得到的顺段进行合并，直至得到整个有序的文件为止。

例如，有一个含有 10000个记录的文件，但是内存的可使用容量仅为1000个记录，毫无疑问需要使用外部排序算法，具体分为两步：

将整个文件其等分为 10 个临时文件（每个文件中含有 1000 个记录），然后将这 10 个文件依次进入内存，采取适当的内存排序算法对其中的记录进行排序，将得到的有序文件(初始归并段)移至外存。
对得到的 10 个初始归并段进行如下图的两两归并，直至得到一个完整的有序文件。

注意：此例中采用了将文件进行等分的操作，还有不等分的算法，后面章节会介绍

如图所示由10 个初始归并段到一个有序文件，共进行了 $4$ 次归并，每次都由 $m$ 个归并段得到 $⌈m/2⌉$ 个归并段，这种归并方式被称为 2-路平衡归并。

注意：在实际归并的过程中，由于内存容量的限制不能满足同时将 2 个归并段全部完整的读入内存进行归并，只能不断地取 2 个归并段中的每一小部分进行归并，通过不断地读数据和向外存写数据，直至 2 个归并段完成归并变为 1 个大的有序文件。如图所示

7.8.2 外部排序的开销及优化思路¶

外部排序时间开销 = 读写外存的时间 + 内部排序所需时间 + 内部归并所需时间

对于外部排序算法来说，影响整体排序效率的因素主要取决于读写外存的次数，即访问外存的次数越多，算法花费的时间就越多，效率就越低。

计算机中处理数据的为中央处理器（CPU），如若需要访问外存中的数据，只能通过将数据从外存导入内存，然后从内存中获取。同时由于内存读写速度快，外存读写速度慢的差异，更加影响了外部排序的效率。

对于同一个文件来说，对其进行外部排序时访问外存的次数同归并的次数成正比，即归并操作的次数越多，访问外存的次数就越多。上图使用的是 2-路平衡归并的方式，举一反三，还可以使用 3-路归并、4-路归并甚至是 10-路归并的方式，下图为 5-路归并的方式：

对比两图可以看出，对于 k-路平衡归并中 $k$ 值得选择，增加$k$可以减少归并的次数，从而减少外存读写的次数，最终达到提高算法效率的目的。除此之外，一般情况下对于具有 $r$ 个初始归并段进行 k-路平衡归并时，归并的次数为：$S=\left \lceil log_k⁡r \right \rceil$（其中 $S$ 表示归并趟数）。

从公式上可以判断出，想要达到减少归并次数从而提高算法效率的目的，可以从两个角度实现：

Note

增加$k$路平衡归并中的$k$值；

代价1：多路平衡归并算法，需要增加相应的输入缓冲区；
代价2：每次从$k$个归并段中选一个最小元素需要$(k-1)$次关键字对比。(可用“败者树”减少关键字对比次数“)

尽量减少初始归并段的数量$r$，即增加每个归并段的长度；

上面介绍的方法生成的初始归并段，若共 $N$ 个记录，内存工作区可以容纳 $L$ 个记录，则初始归并段数量$r = \left \lceil \frac{N }{L}\right \rceil$ , 可以用置换-选择排序算法增加归并段长度从而进一步减少归并段数量。

【注】：有个常见误区，认为$k$ 路平衡归并，归并树必须用严格$k$叉树(即只有度为0和$k$的结点的树)，事实上不是这样的，$k$路平衡归并指的是

最多只能有$k$个段归并为一个；
每一趟归并中，若有$m$个归并段参与归并，则经过这一趟处理得到$\left \lceil \frac{M}{K}\right \rceil$个新的归并段。

如下左图，只是一个4路归并排序，但并不是4路平衡归并排序，因为第一趟处理应该得到$\left \lceil \frac{8}{4}\right \rceil=2$ 个归并段而不是3个，如下右图属于4路平衡归并。

【例题】

假设某文件经内部排序得到100个初始归并段，试问:\ (1)若要使多路归并三趟完成排序，则应取归并的路数至少为多少？\ (2)假若操作系统要求一个程序同时可用的输入、输出文件的总数不超过13，则按多路归并至少需几趟可完成排序？如果限定这个趟数？则可取的最低路数是多少？

5，2，10；

假设一次I/O的物理块大小为150，每次可对750个记录进行内部排序，那么，对含有150000个记录的磁盘文件进行4-路平衡归并排序时，需进行多少次I/O？

150000个记录存放在150000/150=1000个物理块上，每次可对750/150= 5个物理块的记录进行内部排序，即经过内部排序后，可得到1000/5=200个初始归并段。200个初始归并段需要经过$\left \lceil log_4200 \right \rceil =4$趟 4路平衡归并排序。所以，总的$I/O$次数为: $1000*2+ 1000*2\*4=10000$次

7.8.3 败者树实现内部归并¶

通过上一节对于外部排序的介绍得知：对于外部排序算法来说，其直接影响算法效率的因素为读写外存的次数，即次数越多，算法效率越低。若想提高算法的效率，即减少算法运行过程中读写外存的次数，可以增加 $k$ 路平衡归并中的 $k$ 值。

但是经过计算得知，如果毫无限度地增加 $k$ 值，虽然会减少读写外存数据的次数，但会增加内部归并的时间，得不偿失。

例如在上节中，对于 10 个临时文件，当采用 2-路平衡归并时，若每次从 2 个文件中想得到一个最小值时只需比较 1 次；而采用 5-路平衡归并时，若每次从 5 个文件中想得到一个最小值就需要比较 4 次。以上仅仅是得到一个最小值记录，如要得到整个临时文件，其耗费的时间就会相差很大。

为了避免在增加$k$值的过程中影响内部归并的效率，在进行$k$- 路归并时可以使用“败者树”来实现，该方法在增加$k$值时不会影响其内部归并的效率。

败者树是树形选择排序的一种变形，本身是一棵完全二叉树 (多了一个头头)。$k$ 个叶子结点分别对应$k$ 个归并段中当前参与比较的元素。

败者树的双亲结点存储的是左右孩子比较之后的失败者，而胜利者则继续同其它的胜者去比较。

如图所示为一棵 5-路归并的败者树，其中$b_0—b_4$ 为树的叶子结点，分别为 5 个归并段中存储的记录的关键字。 $ls$ 为一维数组 , 表示的是非终端结点，其中存储的数值表示第几归并段（例如$b_0$ 为第 0 个归并段）。$ls[0]$ 中存储的为最终的胜者，结点值为$3$表示当前第 $3$ 归并段中的关键字最小。

当最终胜者判断完成后，只需要更新叶子结点 $b_3$ 的值，即导入关键字 $15$，然后让该结点不断同其双亲结点所表示的关键字进行比较，败者留在双亲结点中，胜者继续向上比较。

例如，叶子结点 $15$ 先同其双亲结点 $ls[4]$ 中表示的$b_4$ 中的12 进行比较，12 为胜利者，则 $ls[4]$ 改为 3，然后 $12$ 继续同 $ls[2]$ 中表示的 $10$ 做比较，$10$ 为胜者，然后 $10$ 继续同其双亲结点 $ls[1]$ 表示的 $b_1$（关键字 $9$）作比较，最终 $9$为胜者。整个过程如下图所示：

由于败者树是一棵完全二叉树，且初始归并段的个数就是叶子结点个数，因此计算高度时要把初始归并段算作叶子结点。

由此可知，对于$k$ 路归并，第一次构造败者树需要对比关键字$k-1$次，之后选出最小元素最多只需要对比$\left \lceil log_2k \right \rceil$ 次即可。

注意：为了防止在归并过程中某个归并段变为空，处理的办法为：可以在每个归并段最后附加一个关键字为最大值的记录。这样当某一时刻选出的冠军为最大值时，表明 5 个归并段已全部归并完成。（因为只要还有记录，最终的胜者就不可能是附加的最大值）

Note

例题：m个初始归并段采用k路平衡归并时，构建的败者树中共有()个节点(不计冠军节点)

A、2m-1 B、2m C、2k D、2k-1

解析

本题选D；败者树是一种用于多路归并的完全二叉树,由于每个叶子需要决出胜负(比较),故没有度为1的节点。其中每个非叶子节点表示输掉比较的元素，叶子节点对应于归并路数k。二叉树叶子节点数为k，那么度为2的结点数为k-1，总节点数为 2k-1。

【具体归并过程】：

初始阶段：假设我们有m个初始有序段，并且要进行K路归并。
第一轮归并：

使用败者树对这m个初始有序段中的K个段进行归并。
归并完成后，K个有序段合并成一个新的有序段，这个新的有序段长度大约为K个初始段长度之和。

后续轮次：

将新生成的有序段与剩下的初始有序段（还未参与归并的）放在一起。
从这些段中再次选取K个段进行下一轮归并。

重复过程：

每完成一轮归并，K个有序段合并成一个新的有序段。
继续从剩余的有序段和新生成的有序段中选取K个段进行归并。
重复上述过程，直到所有的初始段都被归并完毕，最终得到一个完整的有序段。

具体步骤：

初始归并段数量：假设有m个初始有序段。
第一轮归并：选择m个初始段中的K个段，进行败者树归并，得到一个新的有序段。此时，剩余段数为m-K+1（新生成的段加上未参与归并的段）。
第二轮归并：从剩余的段中再选K个段（包括新生成的段）进行归并，得到一个新的有序段。此时，剩余段数为m-2K+2。
继续上述步骤：直到所有初始段都被归并成一个完整的有序段。

通过这种方式，K路归并能够高效地将多个有序段合并成一个完整的有序段，而败者树在每一轮归并中能够有效减少比较次数，提高整体归并效率。

7.8.4 置换选择排序¶

建议看咸鱼的视频，讲的很清楚：https://www.bilibili.com/video/BV1b7411N798?vd_source=defcad5f62788968e79a5f75e0aca2f3&p=103&spm_id_from=333.788.videopod.sections

上一节介绍了增加 $k-$路归并排序中的 $k$ 值来提高外部排序效率的方法，而除此之外，还有另外一条路可走，即减少初始归并段的个数，也就是本章第一节中提到的减小 $r$ 的值。

$r$的求值方法为：$r=⌈n/l⌉$（$n$表示为外部文件中的记录数，$l$表示初始归并段中包含的记录数）

如果要想减小 $r$ 的值，在外部文件总的记录数 $n$ 值一定的情况下，只能增加每个归并段中所包含的记录数$l$ 。而对于初始归并段的形成，就不能再采用上一章所介绍的内部排序的算法，因为所有的内部排序算法正常运行的前提是所有的记录都存在于内存中，而内存的可使用空间是一定的，如果增加 $l$ 的值，内存是盛不下的。

所以要另想它法，探索一种新的排序方法：置换选择排序算法。

例如已知初始文件中总共有 $24$ 个记录，假设内存工作区最多可容纳 $6$个记录，按照之前的选择排序算法最少也只能分为 $4$个初始归并段。而如果使用置换选择排序，可以实现将 24 个记录分为 3 个初始归并段，如图所示：

置换选择排序算法的具体操作过程为：

首先从初始文件中输入 6 个记录到内存工作区中；
从内存工作区中选出关键字最小的记录，将其记为 $MINIMAX$ 记录；
然后将 $MINIMAX$ 记录输出到归并段文件中；
此时内存工作区中还剩余 5 个记录，若初始文件不为空，则从初始文件中输入下一个记录到内存工作区中；
从内存工作区中的所有比 $MINIMAX$值大的记录中选出值最小的关键字的记录，作为新的 $MINIMAX$ 记录；
重复过程 3—5，直至在内存工作区中选不出新的 $MINIMAX$ 记录为止，由此就得到了一个初始归并段；
重复 2—6，直至内存工作为空，由此就可以得到全部的初始归并段。

拿图中的初始文件为例，首先输入前 6 个记录到内存工作区，其中关键字最小的为 29，所以选其为 MINIMAX 记录，同时将其输出到归并段文件中，如下图所示：

此时初始文件不为空，所以从中输入下一个记录 14 到内存工作区中，然后从内存工作区中的比 29 大的记录中，选择一个最小值作为新的 MINIMAX 值输出到归并段文件中，如下图所示：

初始文件还不为空，所以继续输入 61 到内存工作区中，从内存工作区中的所有关键字比 38 大的记录中，选择一个最小值作为新的 MINIMAX 值输出到归并段文件中，如下图所示：

如此重复性进行，直至选不出 MINIMAX 值为止，如下图所示：

当选不出 MINIMAX 值时，表示一个归并段已经生成，则开始下一个归并段的创建，创建过程同第一个归并段一样，这里不再赘述。

在上述创建初始段文件的过程中，需要不断地在内存工作区中选择新的MINIMAX 记录，即选择不小于旧的 MINIMAX 记录的最小值，此过程需要利用“败者树”来实现。

【例题】：设内存有大小为6个记录的区域可供内部排序之用，文件的关键字序列为(51, 49, 39, 46, 38, 29, 14, 61, 15, 30, 1, 48, 52, 3, 63, 27, 4, 13, 89, 24, 46, 58, 33, 76)。试列出：

(1)用普通的内部排序方法求出的初始归并段；

(2)用置换-选择排序得出的初始归并段。

(1 )内部排序法:

RUN1: 29,38,39,46,49,51

RUN2: 1,14,15,30,48,61

RUN3: 3,4,13,27,52,63

RUN4: 24,33,46,58,76,89

(2)置换选择排序:

RUN1: 29,38,39,46,49,51,61

RUN2: 1,3,14,15,27,30,48,52,63,89

RUN3: 4,13,24,33,46,58,76

试问输入文件在哪种状态下经由置换-选择排序得到的初始归并段长度最长？其最长的长度是多少？

当记录关键字呈非递减有序序列时，可以得到最长的归并段，其长度为所有记录总数。

试问输入文件在哪种状态下经由置换-选择排序得到的初始归并段长度最短？其最短的长度是多少？

当序列为递减时最短，最短为缓冲区长度.

假若一个经由置换-选择排序得到的输出文件再次进行置换-选择排序，试问该文件将产生什么变化？

由于已经经过一次排序，因此再来一次保持原样。

7.8.5 最佳归并树¶

通过上一节对置换-选择排序算法的学习了解到，通过对初始文件进行置换选择排序能够获得多个长度不等的初始归并段，相比于按照内存容量大小对初始文件进行等分，大大减少了初始归并段的数量，从而提高了外部排序的整体效率。

本节带领大家思考一个问题：无论是通过等分还是置换-选择排序得到的归并段，如何设置它们的归并顺序，可以使得对外存的访问次数降到最低？

例如，现有通过置换选择排序算法所得到的 9 个初始归并段，其长度分别为：9，30，12，18，3，17，2，6，24。在对其采用 3-路平衡归并的方式时可能出现如图所示的情况：

\ 图 3路平衡归并

提示：图中的叶子结点表示初始归并段，各自包含记录的长度用结点的权重来表示；非终端结点表示归并后的临时文件。

假设在进行平衡归并时，操作每个记录都需要单独进行一次对外存的读写，那么图中的归并过程需要对外存进行读或者写的次数为：

$(9+30+12+18+3+17+2+6+24)*2*2=484$（图中涉及到了两次归并，对外存的读和写各进行 2 次）

从计算结果上看，对于图中的 3 叉树来讲，其操作外存的次数恰好是树的带权路径长度$WPL$的 2 倍。所以，对于如何减少访问外存的次数的问题，就等同于考虑如何使 k-路归并所构成的 k 叉树的带权路径长度最短。

若想使树的带权路径长度最短，就是构造哈夫曼树。

在学习赫夫曼树时，只是涉及到了带权路径长度最短的二叉树为赫夫曼树，其实扩展到一般情况，对于$k$叉树，只要其带权路径长度最短，亦可以称为哈夫曼树。

若对上述 9 个初始归并段构造一棵赫夫曼树作为归并树，如下所示：

其对外存的读写次数为：

$(2*3+3*3+6*3+9*2+12*2+17*2+18*2+24*2+30)\*2=446$

通过以构建哈夫曼树的方式构建归并树，使其对读写外存的次数降至最低（$k$-路平衡归并，需要选取合适的$k$ 值，构建哈夫曼树作为归并树）。所以称此归并树为最佳归并树。

附加“虚段”的归并树

上述图中所构建的为一颗真正的 3叉树（树中各结点的度不是 3 就是 0），而若 9 个初始归并段改为 8 个，在做 3-路平衡归并的时候就需要有一个结点的度为 2。

对于具体设置哪个结点的度为 2，为了使总的带权路径长度最短，正确的选择方法是：附加一个权值为 0 的结点（称为“$虚段$”），然后再构建赫夫曼树。例如若去掉权值为 30 的结点，其附加虚段的最佳归并树如下图所示：

图 3 附加虚段的最佳归并树

注意：虚段的设置只是为了方便构建赫夫曼树，在构建完成后虚段自动去掉即可。

对于如何判断是否需要增加虚段，以及增加多少虚段的问题，有以下结论直接套用即可：

在一般情况下，对于 k–路平衡归并来说，若 $(m-1)MOD(k-1)=0$，则不需要增加虚段；否则需附加$k-(m-1)MOD(k-1)-1$ 个虚段。

因为$k$叉的最佳归并树一定是一棵严格的k叉树，即树中只包含度为k、度为0的结点。设度为k的结点有$n_k$个，度为0的结点有$n_0$个，归并树总结点为$n$个，则

初始归并段数量 + 虚段数量 = $n_0$

$n = n_0 + n_k;$

$k\*n_k = n - 1$（边 = 结点数 - 1）可推得$n_0= (k-1)n_k+1$ —–> $n_k = \frac{n_0-1}{k-1}$

若(初始归并段数量 - 1) % $(k-1) = 0$, 说明刚好可以构成严格$k$叉树，此时不需要添加虚段；

若(初始归并段数量 - 1) % $(k-1) = u$, 则需要补充$(k - 1)-u$个虚段。

外部排序小结

本节介绍了实现外部排序的两个过程：

将整个初始文件分为多个初始归并段;
将初始归并段进行归并，直至得到一个有序的完整文件；

为了提高整个外部排序的效率，本章分别从以上两个方面对外部排序进行了优化：

在实现将初始文件分为 $r$ 个初始归并段时，为了尽量减小 $r$ 的值，采用置换-选择排序算法，可实现将整个初始文件分为数量较少的长度不等的初始归并段。
同时在将初始归并段归并为有序完整文件的过程中，为了尽量减少读写外存的次数，采用构建最佳归并树的方式，对初始归并段进行归并，而归并的具体实现方法是采用败者树的方式。

排序算法	平均/最佳/最差时间复杂度	空间复杂度	就地性	适用数据对象	比较次数是否与序列初始状态有关	元素的移动(交换)次数是否与序列初始状态有关	排序趟数是否与序列初始状态有关
插入	\(O(n^2)/O(n)/O(n^2)\)	\(O(1)\)	原地	数组/链表	有关	有关	无关
折半插入	\(O(n^2)\)	\(O(1)\)	原地	数组	无关	有关	无关
希尔	\(O(n^{1.3})/O(nlogn)/O(n^2)\)不准确，复杂度取决于增量序列	\(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(1)\)	原地	数组	有关（不同情况堆化比较的次数不同）	有关	无关
归并	\(O(nlogn)/O(nlogn)/O(nlogn)\)	\(O(n)\)	非原地	数组/链表	有关（不同状态两两归并次数不同）	无关(因为非原地排序)	无关
计数	\( O(n + k) \)\( k \)为数据范围	\( O(n + k) \)	非原地	数组/链表	非比较排序，无关	非比较(不基于移动元素)排序，无关	无关
基数	\( O(d(n + r)) \)\( d \)为最大位数(即排序趟数)，待排序数据为\( r \)进制	\( O(n+r) \)	非原地	数组/链表	非比较排序，无关	非比较排序，无关	无关
桶	\( O(n+k)/O(n+k)/O(n^2) \)\( k \)为桶的数量	\( O(n+k) \)	非原地	数组	非比较排序，无关	非比较排序，无关	无关