排序算法☣全TIPS收集企划

排序的基本概念

排序问题可以简单描述如下：
输入含有$n$ 个数的序列$(a_1,a_2,\cdots,a_n)$
输出该序列的重排列结果$(a_1',a_2',\cdots,a_n')$ 使得$a_1'\leq a_2'\leq\cdots\leq a_n'$（升序）

排序的数据结构

在实际应用中，待排序的数很少是单独的数值，它们通常是数据集的一部分。每个数据集中的记录包含一个关键字 (key)，这个 key 就是排序问题中要重排的值。值得注意的是，当一个排序算法重排关键字时，一般也“捆绑式”地要重排数据顺序。

可以想象在 Excel 表格中，对学生的期末成绩降序排列。我们显然是希望降序之后，第一行对应最高分且该行的学生姓名也和排列前是对应的，而不是姓名不变，单纯把分数重排。
在这个场景下，(学生姓名, 分数) 就构成了数据集中的一项数据，而关键字就是 分数。

排序稳定性与原址性

稳定性

假设待排序列中元素$A$ 排在 元素$B$ 之前，且它们的关键字相同，即$A.key=B.key$ 。
若经过某个排序算法对该序列进行排序之后，$A$ 仍然在$B$ 之前，则称该排序算法是稳定的。

意义：稳定性本质是维持具有相同属性的数据的插入顺序，如果后面需要使用该插入顺序排序，则稳定性排序可以避免这次排序。

仍然以学生成绩表为例。若学校想根据“总成绩”和“数学成绩”作为学生排名的参考，并且总成绩已经按照降序排列了。现在要再对整个数据集把“数学成绩”作为关键字进行排序。
假设$A$ 和$B$ 的数学成绩相当但$A$ 的总成绩不如$B$ ，如果选择的排序算法不稳定，则第二次排序（即根据数学成绩排序）之后，就可能出现$A$ 排在$B$ 之前的情况。即$A$ 的总成绩低、$B$ 的总成绩高，但$A$ 名次比$B$ 高。
这种情况则还需要再按照“总成绩”再排序一次，会增加系统开销。

希尔、快排、选择、堆排序均是不稳定的排序算法。（希尔快选堆）

原址性

原址（in place, 也叫：就地) 性是指：基本上不需要额外辅助的的空间，允许少量/常数量级的额外的辅助变量进行的排序。

也就是在原来的排序数组中就地比较和交换的排序。如选择排序，插入排序，希尔排序，快速排序，堆排序等，都会有一项比较且交换操作的过程，因此他们都是属于原址排序；而合并排序，计数排序，基数排序等则不是原址排序。

初始序列无关性

选择排序（包括简单选择排序和堆排序）、基数排序、快速排序和归并排序算法都与初始序列无关

内部排序与外部排序

注1：拓扑排序是将有向图中所有结点排成一个线性序列，虽然也是在内存中进行的，但它不属于这里所提到的内部排序范畴，也不满足前面排序的定义。

注2：多路归并排序属于外部排序，

比较次数的界

对于任意$n$ 个关键字进行基于比较的排序，至少要进行$\lceil \log_2(n!)\rceil$ 次关键字之间的两两比较。

题干询问的是任意序列，故最少的比较次数考虑的其实应该是最坏情况。
每次比较两个关键字后仅出现两种可能的转移，假设要做$k$ 次比较，则就有$2^k$ 种情况。
而$n$ 个记录有$A_n^n=n!$ 种情况，因此有$2^k\geq n!$ ，即$k\geq \log_2(n!)$ 。
考虑到$k$ 是整数，所以结果就是$\lceil \log_2(n!)\rceil$ 。

复杂度比较

排序方法	时间复杂度(平均)	时间复杂度(最坏)	时间复杂度(最好)	空间复杂度	稳定性	复杂性
直接插入排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	稳定	简单
希尔排序	$O(n\log_2n)$	$O(n^2)$	$O(n^{1.3})$	$O(1)$	不稳定	较复杂
直接选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定	简单
堆排序	$O(n\log_2n)$	$O(n\log_2n)$	$O(n\log_2n)$	$O(1)$	不稳定	较复杂
冒泡排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	稳定	简单
快速排序	$O(n\log_2n)$	$O(n^2)$	$O(n\log_2n)$	$O(n\log_2n)$	不稳定	较复杂
归并排序	$O(n\log_2n)$	$O(n\log_2n)$	$O(n\log_2n)$	$O(n)$	稳定	较复杂
基数排序	$O(d(n+r))$	$O(d(n+r))$	$O(d(n+r))$	$O(n+r)$	稳定	较复杂

1. 快速排序被认为是目前基于比较的内部排序法中最好的方法。
2. 若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。
3. 当文件的$n$ 个关键字随机分布时，任何借助于“比较”的排序算法，至少需要$O(n\log_2n)$ 的时间。
4. 若$n$ 较小$(n\leq 50)$，则可采用直接插入排序或简单选择排序。
5. 若$n$ 较大，则应采用时间复杂度为$O(n\log_2n)$ 的排序方法：快速排序、堆排序或归并排序。
6. 若$n$ 很大，记录的关键字位数较少且可以分解时，采用基数排序较好。

插入排序

插入排序是一种简单而且直观的排序方法。
其基本思想是每次都将一个新的待排序的元素根据排序规则（通常是升序或降序）插入到之前已经排序好的序列中，直到所有元素插入完毕。

根据插入排序的主要思想，我们在算法执行过程中始终对排序表维护这样的结构（《算法导论》中把这种结构称为循环不变式）：

有序序列$L[1..i-1]$	$L[i]$	待插入序列$L[i+1..n]$

初始时，默认$L[1]$ 是已排列好的个数为 1 的子表，我们需要依次将$L[2]\sim L[n]$ 按照关键字递增（不减）地插入其中：找到插入元素$x:=L[2]$ 应该插入的位置(下标)$k$，然后将之后的元素全部后移一个单位之后，再放入$x$ 。之后将$x:=L[3]$ 插入到刚刚得到的有序序列$L[1..2]$ 中，以此类推。

因为插入排序算法涉及插入过程，即需要找到$L[i]$ 在$L[1..i-1]$ 中的位置。这就涉及到了查找问题。

直接插入排序| Straight Insertion Sort

直接插入排序使用了顺序查找方式。这里我们采用从后往前的顺序查找，为此我们还引入“哨兵”的概念。

具体算法如下：

void InsertSort(vector<int> &nums){
	int i, j, n = nums.size();
	int tmp; //哨兵
	for(i = 1; i < n; i++){
		if(nums[i] < nums[i-1]){
			tmp = nums[i];
			for(j = i-1; j >= 0 && tmp < nums[j]; j--){
				nums[j+1] = nums[j];
			} //边比较边把大于tmp的元素后移
			nums[j+1] = tmp; //for循环结束时，j--，所以j+1是插入点
		}//if
	}//for
}

动图展示

算法分析

直接插入排序的时间效率依赖于待排表的初始状态。

• 最好情况下，表已有序，则每个元素只需比较一次，时间复杂度$O(n)$；
• 最坏情况下，表是逆序，$L[i]$ 需要比较$i$ 次，总共比较$\sum\limits_{i=2}^ni$ 次，移动$\sum\limits_{i=2}^n(i+1)$ 次；
• 平均情况下，表元素随机，可取最好与最坏的平均值，约为$n^2/4$。

综上所述，直接插入排序的时间复杂度为$O(n^2)$.

稳定性：由于每次都是从后往前查找并移动，所以具有稳定性；
适用性：适用于顺序表和链表，后者可以改为从前往后查找。

对有$n$ 个元素的顺序表采用直接插入排序算法进行排序.
在最坏情况下所需的比较次数是：$n(n-1)/2$；
在最好情况下所需的比较次数是：$n-1$。

直接插入排序可能出现：在最后一趟排序开始前，所有元素都不在最终位置上

折半插入排序| Binary Insertion Sort

二分排序，是二分插入排序/折半插入排序的简称。
是一种基于二分法和直接插入排序的思想而构造出来的一种排序算法。

算法思想主要是：
对于给定的序列$L$，先对待插入元素$x$ 利用 二分查找算法 找到插入位置$i$ ，然后整体调整元素位置以让出目标元素的位置进行插入.

算法分析

二分排序由二分查找和插入两部分组成。

二分查找问题可以利用分治策略。
给定一个有序数组$A$，要查找某个元素$x$ 在$A$ 中的位置，可以利用二分法的思想，先将$x$ 与$A[n/2]$ 进行比较（$n$ 是数组长度），从而可以根据比较结果，锁定$x$ 是属于子数组$A[1..n/2]$ 还是子数组$A[n/2+1..n]$。进而将原问题分解为了规模更小的子问题。迭代求解子问题就可以综合得到原问题的解。

下面给出二分排序的伪码：

$$\begin{aligned} &\text{Algorithm: }\;\text{Binary-InsertSort}(L,n)\\\\ 1.&\;\mathbf{for}\;i\;=2\;\mathbf{to}\;n\;\mathbf{do}\\ 2.&\;\qquad x\leftarrow L[i]\\ 3.&\;\qquad\;low\leftarrow1;\;high\leftarrow i-1\\ 4.&\;\qquad\mathbf{while}\;low\leq high\;\mathbf{do}\\ 5.&\;\qquad\qquad mid\leftarrow \left \lfloor(low+high)/2\right \rfloor\\ 6.&\;\qquad\qquad\mathbf{if}\;L[mid]\gt x\;\mathbf{then}\\ 7.&\;\qquad\qquad\qquad high\leftarrow mid-1\\ 8.&\;\qquad\qquad\mathbf{else}\; low\leftarrow mid+1\\ 9.&\;\qquad\mathbf{for}\;j=i-1\;\mathbf{downto}\;high+1\;\mathbf{do}\\ 10.&\;\qquad\qquad L[j+1]\leftarrow L[j]\\ 11.&\;\qquad L[high+1]\leftarrow x\\ 12.&\;\mathbf{return}\;nums \end{aligned}$$

折半法出现$high<low$ 的情况即为：$high$ 位置的值小于关键字，$low$ 位置的值大于关键字，所以，$low$ 的位置（即$high+1$ ）为插入元素位置。

对于二分查找，其时间复杂度存在递推方程$W(n)=W(\lfloor n/2\rfloor)+1,W(1)=1$.
解得$W(n)=\lfloor \log n\rfloor+1$

一共进行$n$ 次查找和$n$ 次移位，一次移位需要进行$O(n)$ 次，与直接插入相比，仅减少了比较元素次数。

综上所述，二分排序的时间复杂度为$O(n^2)$，空间复杂度$O(1)$.

数据量小的排序表，折半插入往往能表现出很好的性能。

编程实现

void BinaryInsertSort(vector<int> &nums){
    int i, j;
    int x;
    int low, high, mid;

    for(i = 1; i < nums.size(); i++){
    
        x = nums[i];
        low = 0; high = i-1;

        while(low <= high){
            mid = low+high >> 1;
            if(nums[mid] > x) high = mid - 1;
            else low = mid + 1;
        }

        for(j = i-1; j >= high+1; j--){
            nums[j+1] = nums[j];
        }
        nums[high+1] = x;
    }
}

希尔排序| Shell’s Sort

希尔排序（又称，缩小增量排序 Diminishing Increment Sort），其主要思想是将待排序表事先分割成若干个特殊的子表。
一般来说是将序列按照某一增量/步长$d,\;d\lt n$ ，将原表中，间隔$d$ 的元素共同组成一个表$L[i,i+d,i+2d,\cdots,i+kd]$。【如分割成$L[1,3,5,7,...,2k-1]$ 和$L[2,4,6,8,...,2k]$】
然后，对各个子表进行直接插入排序，最后，再对整个表进行一次直接插入排序。

希尔排序的提出是因为直接插入排序对数据量小且基本有序的表效果良好，所以才考虑分割子表降低数据量，分别排序使得基本有序。

事实上，希尔排序并不只进行一次分割排序，而是多次的：步长大小依次减少，第$i$ 次对间隔$d_i$ 的子表进行排序，直到步长为1，此时就是对整个表的排序。

把每一次排序所用的步长组成的序列称为一个增量序列，根据增量序列的不同选取，希尔排序的时间复杂度也有所不同。

动图演示

下面是利用“除二序列”实现的希尔排序的动图演示。

算法分析

我们最常用的是除二序列，即$d_i=n/2^i$。下面也以此用代码实现希尔排序。

void ShellSort(vector<int> &nums){
	int d, n = nums.size();
	int i, j, tmp;
    for(int d = n/2; d >= 1; d = d/2){
        i = 0;
        //下面是直接插入排序思想
        for(i = i + d; i < n; i++){
            if(nums[i] < nums[i-d]){
                tmp = nums[i];
                for(j = i-d; j >= 0 && nums[j] > tmp; j = j-d){
                    a[j+d] = a[j];
                }
	            a[j+d] = tmp;
            }//if
        }//for
    }
}

虽然插入排序是稳定的排序算法，但是希尔排序因为将序列进行了拆分再进行插入排序，如此不同组中的相等元素相对位置不能保证不变，所以相等元素的相对位置会发生改变。
故希尔排序是不稳定排序。

前面我们说根据增量序列的不同选取，希尔排序的时间复杂度也有所不同。 目前已知策略中，希尔排序可达到$O(n^{1.3})$ 。最坏情况下也是$O(n^2)$。

交换排序

冒泡排序 |Bubble Sort

冒泡排序的算法思想：升序排序，从前往后进行比对和交换，先确定最大元素位置（或从后向前冒泡，先确定小元素位置）。

每趟排序都会将一个元素放在最终位置，冒泡排序最多做$n−1$ 趟

动图演示

下图是以【从前往后，优先确定最大元素位置】为思路的冒泡排序示例。

算法分析

从前向后对两两元素比较大小，若$L[j]>L[j+1]$ 则交换两元素，将$j$ 加1后 继续比较。
第一趟结束后，最大元素则被放在了最后，其位置确定。所以下一趟它也就不参与比较，然后再进行第二趟排序。
为了减少多余的比较次数，我们还可以在循环中设置标志，每趟排序判断是否发生交换元素，若未发生则排序完成。

void BubbleSort(vector<int> &nums){
	int flag; //用于标志本趟排序是否交换了元素
	int n = nums.size();
	for(int i = 0; i < n-1; i++){ //最多执行 n-1 趟
		flag = false;
		for(int j = 0; j < n-1-i; j++){
			if(nums[j] > nums[j+1]){
				swap(nums[j],nums[j+1]);
				flag = true;
			}
		}
		if(flag == false)
			return; //一趟下来并没有发送交换时，说明已经有序，可直接退出
	}
}

当初始序列有序时，只需一趟冒泡即可，此时比较$n-1$ 次，交换/移动$0$ 次；
当初始序列逆序时，需要进行$n-1$ 趟排序，每趟$n-i$ 次比较，交换元素需要3次简单赋值操作，即：

$$比较次数=\sum_{i=1}^{n-1}(n-i)=\frac{n(n-1)}2$$

$$移动次数=\sum_{i=1}^{n-1}3(n-i)=\frac{3n(n-1)}{2}$$

综上，最好情况下时间复杂度$O(n)$；最坏情况下$O(n^2)$.

稳定性：冒泡排序是稳定的排序方法。

快速排序| Quick Sort

快速排序 是一种基于分治策略的排序算法。
它的最差情况时间复杂度为$\Theta(n^2)$ ，但是平均时间复杂度在$\Theta(n\log n)$，且常数因子很小。这使得快排成为实际排序应用中的一种较好选择。

算法分析

快速排序利用分治思想将把给定序列$L[p..r]$ 的排序问题划分为如下三个部分：

1. 分解：任取一个元素$x$ 作为枢轴（pivot 也叫基准，通常取首元素） 将$L$ 划分为两个连续子序列$L[p..q-1],\;L[q+1..r]$（可以为空）使得左边的元素均小于$x:=L[q]$，右边的元素均大于或等于$L[q]$。而下标$q$ 即是元素$x$ 排列完毕后最终的位置。
2. 求解：递归调用快排程序，两个子序列$L[p..q-1],\;L[q+1..r]$ 成为子问题，对其分别进行排序。
3. 合并：由于快排是对$L[1..n]$ 进行的原址排序，因此无需合并，递归求解之后数组即为排列完成的数组。

关于上述的 【求解】 中，每一次的迭代过程被称为一趟快速排序。这个过程事实上是通过交替搜索和元素交换实现的。下面用一具体图示展示这个过程：

我们需要的第一趟排序结果如图最后一行所示，使得序列中大于$x$ 和小于$x$ 的序列被分割开来。

建立双指针$i,j$ . 初始时分别在数组的左右两端，$j$ 不断向左移动，$i$ 不断向右移动。
移动过程中，$j$ 主要目的是从右向左找到第一个不满足最终要求的位置，即$A[j]\lt x$ ，$i$ 类似，找到这样的$i$ 使得$A[i]\geq x$，为了得到目标排序，对两个元素进行交换，然后继续。

【注】 一趟排序的搜索与交换方法有很多种，这里展示的只是其中一种

下面是对子数组$A[p..r]$ 进行一趟排序的搜索交换算法的伪码。其中，为了方便我们假设把首元素作为一个基准/枢纽进行排序。

$$\begin{aligned} &\text{Algorithm: }\;\text{Partition}(A,p,r)\\\\ 1.&\;x\leftarrow A[p]\\ 2.&\;i\leftarrow p;\;j\leftarrow r\\ 3.&\;\mathbf{while}\;i\lt j\;\mathbf{do}\\ 4.&\;\qquad\mathbf{while}\;i\lt j\;\text{and}\;A[j]\gt x\;\mathbf{do}\\ 5.&\;\qquad\qquad j\leftarrow j-1\\ 6.&\;\qquad\mathbf{while}\;i\lt j\;\text{and}\;A[i]\leq x\;\mathbf{do}\\ 7.&\;\qquad\qquad i\leftarrow i+1\\ 8.&\;\qquad A[i]\;\leftrightarrow\;A[j]\\ 9.&\; A[i]\leftrightarrow A[p]\\ 10.&\;\mathbf{return}\;i \end{aligned}$$

得到一趟排序的算法之后，我们便可以根据分治法的思想，递归地分解子问题然后调用函数实现快排，伪代码如下：

$$\begin{aligned} &\text{Algorithm: }\;\text{QuickSort}(A,p,r)\\\\ 1.&\;\mathbf{if}\;p\lt r\;\mathbf{then}\\ 2.&\;\qquad q\leftarrow \text{Partition}(A,p,r)\\ 3.&\;\qquad \text{QuickSort}(A,p,q-1)\\ 4.&\;\qquad \text{QuickSort}(A,q+1,r)\\ \end{aligned}$$

算法性能

当每一次划分（Partition）时，都把数组分别划分为长度分别是$n,0$ 的两个数组时，算法一共要执行$n$ 次时间为$\Theta(n)$ 的划分操作，从而快排的最坏时间复杂度为$O(n^2)$.

当每次都正好能够平分数组，即每次都能将数组划分为$A[1..n/2],\;A[n/2+1..n]$ 时，算法运行时间的递推方程为：

$$T(n)=2T(n/2)+\Theta(n)$$

可利用主定理解得$T(n)=\Theta(n\log n)$. 这是快排的最优时间复杂度.

当然这是$1:1$ 的情况。
《算法导论》给出，如果每次递归下都是固定的某一常数比例的划分（例如$1:9$），那么快排的时间复杂度仍是$O(n\log n)$.

而 平均时间复杂度 已在本站文章【算法设计基础与综述】中的【差消法】部分介绍，此处不再赘述。
可以得出假设 枢轴/基准/首元素 在一趟排序后的位置服从于均匀分布$U(p,r)$. 即其在每一个位置的概率相等且为$1/n$. 那么快排的平均实际复杂度为$\Theta(n\log n)$.

对于空间复杂度，由于需要利用到递归工作栈，所以：

• 分配均匀时达到最好情况，此时空间复杂度为$\lfloor\log_2(n+1)\rfloor$
• 分配不平衡时到达最坏情况，此时为$O(n)$
• 平均情况就是$O(\log_2n)$

快速排序的元素比较次数与序列的初始序列无关，始终是$n(n−1)/2$
快速排序当待排序表已经基本有序时，反而属于最坏情况

随机化快速排序| Randomized QuickSort

在快排的性能分析时，我们假设数组元素在每个位置的概率相同且为$1/n$
然而在实际工程中这种假设却往往不成立。

因此，对于大数据的排列问题时，往往引入 随机性 来优化算法的性能。这样的快排被称为快速排序的随机化版本，或直接叫随机快速排序。

算法分析

引入一种随机抽样（random sampling）的概念，区别于直接将首元作为枢轴，我们每一次划分时都随机地从数组$A[p..r]$ 中选取一个元素$x$ 将其作为枢轴来进行划分，因枢轴是等概率的随机选取，所以这个划分也是尽量均衡的。

算法很简单，只需在$Partition()$ 时，将首元和数组中随机选择出的任意元素进行交换即可。

$$\begin{aligned} &\text{Algorithm: }\;\text{Randomized-Partition}(A,p,r)\\\\ 1.&\;i\leftarrow \text{Random}(p,r)\\ 2.&\;A[p]\leftrightarrow A[i]\\ 3.&\;x\leftarrow A[p]\\ 4.&\;i\leftarrow p;\;j\leftarrow r\\ 5.&\;\mathbf{while}\;i\lt j\;\mathbf{do}\\ 6.&\;\qquad\mathbf{while}\;i\lt j\;\text{and}\;A[j]\gt x\;\mathbf{do}\\ 7.&\;\qquad\qquad j\leftarrow j-1\\ 8.&\;\qquad\mathbf{while}\;i\lt j\;\text{and}\;A[i]\leq x\;\mathbf{do}\\ 9.&\;\qquad\qquad i\leftarrow i+1\\ 10.&\;\qquad A[i]\;\leftrightarrow\;A[j]\\ 11.&\; A[i]\leftrightarrow A[p]\\ 12.&\;\mathbf{return}\;i \end{aligned}$$

编程实现

int Partition(vector<int> &A, int p, int r){
    int i, j;

    // 取消注释即为 随机化版本
    // i = rand() % (r-p+1) + p;
    // swap(A[p],A[i]);

    i = p+1;
    j = r;
    int x = A[p];
    while(i < j){
        while(i < j && A[j] >= x) j--;
        while(i < j && A[i] < x) i++;
        swap(A[i],A[j]);
    }
    swap(A[p],A[i]);
    return i;
}

void QuickSort(vector<int> &A, int p, int r){
    if(p < r){
        int q = Partition(A, p, r);
        QuickSort(A, p, q-1);
        QuickSort(A, q+1, r);
    }
}

选择排序

选择排序的基本思想是：每一趟（如第$i$ 趟）在后面的$n-i+1$ 个待排序元素中，选择最小的元素放入第$i$ 个位置。直到$n-1$ 趟做完。

根据对不同的数据结构操作，对数组或链表操作的叫简单选择排序，对堆进行操作的叫堆排序。

简单选择排序| Selection Sort

根据上面选择排序的算法思想，可以很直观得出简单选择排序的算法步骤：

1. 初始化变量 min = 0 作为序列中最小元素的下标；
2. 第 1 趟排序，依次判断$L[j]\lt L[min]$ ，若是则更新 min 的值，找到最小值后，将其与$L[0]$ 交换位置，即最小值放在最前面，其位置固定；
3. 以此类推，第$i$ 趟排序，从$L[i]\sim L[n]$ 中选出最小元素，与$L[i]$ 交换，以固定第$i$ 小元素的位置。

动图演示

算法分析

void SelectSort(vector<int> &nums){
	int min, n = nums.size();
	for(int i = 0; i < n-1; i++){
		min = i;
		for(int j = i+1; j < n; j++){
			if(nums[min] > nums[j]) min = j;
		}
		if(min != i) swap(nums[min],nums[i]);
	}
}

不难得出，简单选择排序元素移动操作的次数最少，不会超过$3(n-1)$ 次，但元素间的比较次数与初始序列无关，始终为$n(n-1)/2$ 次。
即：空间复杂度$O(1)$，时间复杂度$O(n^2)$。

堆排序

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序。

它的最坏，最好，平均时间复杂度均为$O(n\log_2n)$，它也是不稳定排序。

堆的定义

堆(heap)是计算机科学中一类特殊的数据结构的统称，可以把它视为利用数组$L[1..n]$ 存储的完全二叉树，并且满足下列条件中的其中一条（即要么是大根堆要么是小根堆）。

• 大根堆/大顶堆：满足$L[i]\geq L[2i]$ 且$L[i]\geq L[2i+1]$，即父结点的值始终大于或等于左右孩子结点的值。
• 小根堆/小顶堆：满足$L[i]\leq L[2i]$ 且$L[i]\leq L[2i+1]$，即父结点的值始终小于或等于左右孩子结点的值。

一个大根堆的示例如下图所示。

大根堆结构	数组

STL 中的堆

堆在 C++ 标准库 STL 中支持以下的基本操作：

#include <algorithm> //头文件
#include <vector>

int main(void){
	vector<int> nums = {9, 43, -54, 4, -13, 10, 36};
	
	// 建立大顶堆
	make_heap(nums.begin(),nums.end());//等价于下一行
	make_heap(nums.begin(),nums.end(),less<int>()); 

	// 建立小顶堆
	make_heap(nums.begin(),nums.end(),greater<int>());

	/*  上述处理过后的 nums 数组次序会得到调整  */

	//弹出堆顶元素，进行pop_back()操作
	pop_heap(nums.begin(),nums.end(),less<int>());

堆的维护

当一个堆在下标$i$ 处的结构遭到破坏时，我们需要对其进行维护，以使得其通过我们的调整后再次符合堆的定义。

我们定义$\text{Max-Heapify}()$ 函数是一个用于维护最大堆性质的过程。输入为一个需要调整的最大堆，即数组$A$ 和一个用于开始调整的下标$i$。

我们假定$A[i]$ 的左右子树代表的二叉树已经都是最大堆，而$A[i]$ 本身有可能小于其孩子，这样就违背了最大堆的性质。于是我们可以调用$\text{Max-Heapify}()$ 函数，让$A[i]$ 的值在最大堆中“逐级下降”，从而使得以下标$i$ 为根结点的子树重新遵循最大堆的性质。

$\text{Max-Heapify}()$ 堆结点$i$ 调整时，若其子结点的值大于父结点(即它本身)，则进行交换；若本次交换破坏了下一级堆，则再递归地过去调整下一级的堆。

下图是一个调用$\text{Max-Heapify}(A,i=2)$ 的示例。

因为结点$i=2$ 的左孩子的值$A[2i]\gt A[i]$ ，于是将二者交换，此交换可能破坏了左子树代表的堆，于是递归地对结点$2i=4$ 进行新的调整。发现此时结点$2i+1=9$ 有$A[2i+1]\gt A[i]$ ，所以二者交换。

算法实现：

void MaxHeapify(vector<int> &nums, int i){
	int max; //用于存放父结点与左右孩子值最大的结点下标
	int left = 2*i+1; //左右孩子的下标
	int right = 2*i+2; //数组从0开始，所以写法区别于文中描述

	// 比较左右孩子
	if(left < nums.size() && nums[left] > nums[i])
		max = left;
	else
		max = i;
	if(right < nums.size() && nums[right] > nums[max])
		max = right;

	if(max != i){
		swap(nums[i], nums[max]); //交换
		MaxHeapify(nums, max); //破坏结构，调整下一级堆
	}

可以证明，对于树高为$h$ 的堆，其维护所需时间复杂度为$O(h)$.

堆的创建

堆的创建通常是指对于一个给定的无序序列$L$ ，将其调整为符合堆定义的顺序。

而这个创建过程一般有两种方式。
方式一是利用在堆中插入元素的思路。
尽管数组中包含$n$ 个元素，也可以假设起初堆中只包含一个元素，然后不断调用插入操作，将后续$2\sim n$ 的元素依次插入到堆中，这样就将包含$n$ 个元素的数组，组织成堆。

方式二是先按照完全二叉树的存储方法对其进行存储，然后再从下往上地进行元素交换调整，使得数组排序满足堆的定义，这个过程也叫“堆化”。

这里我们主要介绍方式二。

---

对于有$n$ 个结点的完全二叉树，利用完全二叉树的特性，我们知道最后一个结点的父结点下标是$\lfloor n/2\rfloor$，即$L[\lfloor n/2\rfloor]$ 是最后一个分支结点/非终端结点。

自底向上的堆化过程要求：先对$\lfloor n/2\rfloor$ 为根的子树进行调整，然后向前依次对$\lfloor n/2\rfloor-1\to1$ 为根的子树进行调整，每次调整时若子结点的值大于父结点，则进行交换；若本次交换导致破坏了下一级堆，则再转过去调整该堆，然后回来继续比对上一个子树，直到根结点结束。

从描述上不难看出，这就是一个从最后一个非终端结点开始不断在调用$\text{Max-Heapify}()$ 的过程。因此其算法实现也很简单：

void BuildMaxHeap(vector<int> &nums){
	for(i = nums.size()/2-1; i >= 0; i--){
		MaxHeapify(nums, i);
	}
}

结合$\text{Max-Heapify}()$ 的时间复杂度，可以证明，堆的建立可以直接在线性时间内完成，即其时间复杂度为$O(n)$.

上图是一个建堆的示例，根据前面的描述，$i$ 分别取$\{\lfloor 10/2\rfloor=5,4,3,2,1\}$ （与代码实现不同，默认下标从1开始）

堆的插入

堆的插入问题是指：假设数组中从$0$ 到$i-1$ 位置的元素是一个大根堆，然后把第$i$ 个位置的元素插入大根堆中以便构造一个新的大根堆。

堆的创建有三种方法：交换法、下移法、哨兵法。

交换法

交换法的思想是：将要插入的结点插入末尾，此时其下标为$i$ ，则从第$i$ 个结点开始，依次和它的父结点进行比较，如果父结点的值小于它就进行交换，依次从下往上比较，直到父结点的值大于它或者到了大根堆的最顶端的根结点时，彻底结束。

下移法

哨兵法

堆的删除

堆排序| Heap Sort

归并排序

归并排序是建立在归并操作的基础上的一种有效的排序算法。
算法核心是采用分治思想：将已经有的子序列排序后合并，得到完全有序的序列；即先使每个子序列有序，在使子序列段间有序。

二分归并排序| 2-Route Merge Sort

若归并排序中，递归地将待排序表分为两个表进行排序，然后再将两个有序表合并成一个有序表，则称为 2-路归并，也叫二分归并排序。

算法分析

由于采用了分治策略，所以我们需要从分解子问题和子问题合并两个方向进行考虑，如下图所示。

---

先考虑将两个有序表进行合并的问题。

为了尽可能降低辅助空间的开辟，我们可以考虑仅通过下标定界的方式进行“分割”，即采用 low, high 下标来界定当前子序列的边界，而不是真的开辟一个空间copy出一个子序列。
然而合并的比较过程以及最终元素的位置确定上，则不可避免地需要依赖新的空间，所以我们可以动态申请一个新的数组空间临时使用。

从而，得到如下的合并函数：

void merge(vector<int> &nums, int low, int mid, int high){
	// 将 nums[low..mid], nums[mid+1..high] 两张有序表合并

	int i, j, k;
    int *tmp = new int[nums.size()]; //动态创建临时数组
	for(i = low; i <= high; i++)
		tmp[i] = nums[i]; // 将nums 复制到 tmp 中
    
    k = low; //指示目标数组当前的最低位
    i = low; j = mid+1;
    while(i <= mid && j <= high){
        if(tmp[i] <= tmp[j]){
	        nums[k++] = tmp[i++];
	    }else {
		    nums[k++] = tmp[j++];
		}
    }// 将两表中最小者依次放入 nums 中
    
    while(i <= mid) { nums[k++] = tmp[i++];} // 若左子序列还剩，继续填装
    while(j <= high){ nums[k++] = tmp[j++];} // 若右子序列还剩，继续填装

    delete tmp; //释放空间
}

对于分解。假设我们已经实现了归并排序的算法 MergeSort() ，则一个序列的归并结果，就是其左子序列排序、右子序列排序，最后两个序列合并的过程。
从而可以得到二路归并排序的递归函数：

void MergeSort(vector<int> &nums, int low, int high){
    if(low < high){//递归退出条件
        int mid = (low+high)/2;
        MergeSort(nums, low, mid);
        MergeSort(nums, mid+1, high);
        merge(nums, low, mid, high) ;
    }
}

算法性能

显然，归并排序与初始序列无关。

• 空间复杂度：$O(n)$（merge()中占$n$ 个辅助空间）
• 时间复杂度：$O(n\log_2n)$（每趟归并$O(n)$，共进行$\lceil\log_2n\rceil$ 趟归并）
• 稳定性：稳定

其他排序

计数排序| Counting Sort

计数排序要求输入的数据必须是有明确的范围的整数，这一点尤为重要。

在此基础上，我们通过增加辅助空间，如数组$C[1..n]$ 对每个元素出现的次数进行计数。该计数过程十分类似于 Hash 表 的单一映射，若$L[i]=k$ 则$C[k]\leftarrow C[k]+1$。

计数完毕之后，再执行$C[k]\leftarrow C[k]+C[k-1]$ ，这一步将$C[·]$ 中的值更新为 原表$L$ 中不大于$k$ 的元素的个数，也就是说，此时$C[·]$ 中的值就是元素$k$ 最后的位置的下标。（针对$L$ 中元素各不相同的情况）

于是，再覆盖回到$L$ 中：$L[C[k]]\leftarrow k$ ，则得到最终结果。

若$L$ 中有相同元素，则只需$C[k]\leftarrow C[k]-1$ ，然后再覆盖$L[C[k]]\leftarrow k$ 。相当于在原来的基础上将下标左移一位，并放入$k$。

动图演示如下：

编程实现。

void CountingSort(vector<int> &nums, int min, int max){
	int i, *C = new int[max+1]; //计数数组
    vector<int> tmp(nums.size(),0); //临时存放最终结果
	memset(C,0,sizeof(C)); // 计数数组初始化

	for(i = 0; i < nums.size(); i++)
		C[nums[i]]++; // 计数

	for(i = min; i < max; i++)
		C[i+1] += C[i]; // 统计位置

	for(i = 0; i < nums.size(); i++){
		tmp[C[nums[i]]-1] = nums[i]; // -1是因为nums、tmp的下标从0开始
        C[nums[i]]--; //重复元素处理
	} //在tmp中对应放入正确元素
    nums = tmp; //将结果返回给nums（此处的“=”是vector类特有的重载）
}

可以得出，计数排序可以实现线性时间内的排序。
时空复杂度均为$O(k+n)$。

基数排序| Radix Sort

待更

桶排序| Bucket Sort

待更

🎲特典：洗牌算法综述