C/C++排序算法（二） —— 选择排序和堆排序

---

前言

今天我们将学习排序算法中的 直接选择排序 和 堆排序，它们的本质就是在选择，所以这两个可以统称为 选择排序。

1. 直接选择排序

🍑 基本思想

选择排序（Selection-sort）是一种简单直观的排序算法。

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

🍑 具体步骤

相信大家都上过体育课吧，一般第一节体育课的时候，老师都会让大家排好队然后按照个头从矮到高进行排序，假设有 5 名同学。

首先老师找到了个子最矮的 5 号同学，然后老师说：5 号同学，你是最矮的，跟 1 号交换一下位置！

这时候，老师又说：4 号同学，你是第二矮的，跟 2 号交换一下位置！

老师又说：2 号同学，你是第三矮的，你和 3 号交换一下位置！

最后，老师说：1 号同学，你是第四矮的，你和 3 号交换一下位置吧！

如此一来，每一轮选出最小者直接交换到左侧的思路，就是选择排序的思路。这种排序的最大优势就是省去了多余的元素交换。

🍑 具体步骤

算法实现：

（1）在元素集合 array[i] 到 array[n-1] 中选择关键码最大(小)的数据元素。

（2）若它不是这组元素中的最后一个（第一个）元素，则将它与这组元素中的最后一个（第一个）元素交换。

（3）在剩余的 array[i] 到 array[n-2]（array[i+1] 到 array[n-1]）集合中，重复上述步骤，直到集合剩余 1 个元素。

🍑 动图演示

我们来看看选择排序的动图演示吧

🍑 代码实现

代码示例

//交换函数
void Swap(int* pa, int* pb) {int tmp = *pa;*pa = *pb;*pb = tmp;
}//选择排序(一次选一个数)
void SelectSort(int* a, int n)
{int i = 0;for (i = 0; i < n; i++)//i代表参与该趟选择排序的第一个元素的下标{int start = i;int min = start;//记录最小元素的下标while (start < n){if (a[start] < a[min])min = start;//最小值的下标更新start++;}Swap(&a[i], &a[min]);//最小值与参与该趟选择排序的第一个元素交换位置}
}

🍑 代码升级

实际上，我们可以一趟选出两个值，一个最大值和一个最小值，然后将其放在序列开头和末尾，这样可以使选择排序的效率快一倍。

代码示例

//交换函数
void Swap(int* pa, int* pb) {int tmp = *pa;*pa = *pb;*pb = tmp;
}//直接选择排序（优化版本）
void SelectSort(int* a, int n) {int left = 0;int right = n - 1;while (left < right) {int mini = left;int maxi = left;//遍历区间：[left+1, right]//选出最小的和最大的，然后交换for (int i = left + 1; i <= right; ++i) {//选出最小的数if (a[i] < a[mini]) {mini = i;}//选出最大的数if (a[i] > a[maxi]) {maxi = i;}}Swap(&a[left], &a[mini]); //把最小的数放在最左边//如果left和maxi重叠，修正一下maxi即可if (left == maxi) {maxi = mini;}Swap(&a[right], &a[maxi]); //把最大的数放在最右边left++;right--;}
}

🍑 特性总结

• 直接选择排序思考非常好理解，但是效率不是很好，实际中很少使用。

• 时间复杂度：$O(N^2)$

• 空间复杂度：$O(1)$

• 稳定性：不稳定

2. 堆排序

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

堆是具有以下性质的完全二叉树：

（1）每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；

（2）或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

如下图所示，就是两种堆的类型：

同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子：

该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：

• 大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

• 小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

🍑 向下调整算法

既然要进行堆排序，那么就要建堆，而建堆的方式有两种：

• 使用向上调整，插入数据的思想建堆，但是时间复杂度为：$O(N\ast logN)$

• 使用向下调整，插入数据的思想建堆，时间复杂度为：$O(N)$

所以我们这里推荐使用 堆的向下调整算法，那么建堆也是有 2 个前提的：

（1）如果需要从⼤到⼩排序，就要将其调整为小堆，那么根结点的左右子树必须都为小堆。

（2）如果需要从⼩到⼤排序，就要将其调整为大堆，那么根结点的左右子树必须都为大堆。

但是我们先了解一下什么叫做大堆，如下图：

注意：有一个概念别搞错了，调整大堆并不是把元素从大到小排列，而是每个根节点都比它的叶子节点大

向下调整建大堆算法的基本思想：

（1）从根结点处开始，选出左右孩子中值较大的孩子，让大的孩子与其父亲进行比较

（2）若大的孩子比父亲还大，则该孩子与其父亲的位置进行交换。并将原来大的孩子的位置当成父亲继续向下进行调整，直到调整到叶子结点为止。

（3）若大的孩子比父亲小，则不需处理了，调整完成，整个树已经是大堆了。

如下图所示：

堆的向下调整算法代码

//向下调整大堆
void AdjustDownBig(HPDataType* a, size_t size, size_t root) {size_t parent = root;size_t child = 2 * parent + 1; //默认左孩子最大while (child < size){//1.找出左右孩子中小的那个//如果右孩子存在，且右孩子小于size(元素个数)，那么就把默认小的左孩子修改为右孩子if (child + 1 < size && a[child + 1] > a[child]) {++child;}//2.把小的孩子去和父亲比较，如果比父亲小，就交换if (a[child] > a[parent]) {Swap(&a[child], &a[parent]);parent = child;child = 2 * parent + 1;}else {break; //如果孩子大于等于父亲，那么直接跳出循环}}
}

使用堆的向下调整算法，最坏的情况下（即一直需要交换结点），需要循环的次数为：$h-1$ 次（ h 为树的高度）。

而 $h=log2(N+1)$（ N 为树的总结点数）。

所以堆的向下调整算法的时间复杂度为：$O(logN)$ 。

🍑 任意树调整为堆的思想

上面说到，使用堆的向下调整算法需要满足其根结点的左右子树均为大堆或是小堆才行，那么如何才能将一个任意树调整为堆呢？

答案很简单，我们只需要从 倒数第一个非叶子结点 开始，从后往前，按下标，依次作为根去向下调整即可。

注意：倒数第一个非叶子结点，即为最后一个节点的父亲，也被叫做根。

如图所示：

建堆代码

//从倒数第一个非叶子节点开始（最后一个节点的父亲）
//n-1是最后一个节点的下标，(n-1-1)/2最后一个节点的父亲的下标
for (int i = (n - 1 - 1) / 2; i >= 0; --i) {AdjustDownBig(a, n, i);
}

那么建堆的时间复杂度又是多少呢？

当结点数无穷大时，完全二叉树与其层数相同的满二叉树相比较来说，它们相差的结点数可以忽略不计，所以计算时间复杂度的时候我们可以将完全二叉树看作与其层数相同的满二叉树来进行计算。

 
我们计算建堆过程中总共交换的次数：$T(n)=1\ast (h-1)+2\ast (h-2)+...+2^{h-3}\ast 2+2^{h-2}\ast 1$
 
两边同时乘 2 得：$2T(n)=2\ast (h-1)+2^2\ast (h-2)+...+2^{h-2}\ast 2+2^{h-1}\ast 1$
 
两式相减得：$T(n)=1-h+2^1+2^2+...+2^{h-2}+2^{h-1}$
 
运用等比数列求和得：$T(n)=2^h-h-1$
 
由二叉树的性质，有 $N=2^h-1$ 和 $h=lo{g}_2(N+1)$
 
所以：$T(n)=N-lo{g}_2(N+1)$
 
那么用大 O 的渐进表示法：$T(N)=O(N)$

总结一下：

• 堆的向下调整算法的时间复杂度：$O(logN)$

• 建堆的时间复杂度：$O(N)$

🍑 堆排序

堆排序的基本思想是：

• 将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;

• 将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;

• 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

堆排序代码

void HeapSort(int* a, int n) {//建堆：使用向下调整 --> O(N)//从倒数第一个非叶子节点开始（最后一个节点的父亲）//n-1是最后一个节点的下标，(n-1-1)/2最后一个节点的父亲的下标for (int i = (n - 1 - 1) / 2; i >= 0; --i) {AdjustDownBig(a, n, i);}//升序 --> 建大堆size_t end = n - 1; //最后一个元素的下标while (end > 0){Swap(&a[0], &a[end]); //交换第一个元素和最后一个元素AdjustDownBig(a, end, 0);--end;}
}

🍑 动图演示

我们来看一个堆排序的动图过程吧

🍑 完整代码

代码实现

//调整算法里面的交换函数
void Swap(HPDataType* pa, HPDataType* pb) {HPDataType tmp = *pa;*pa = *pb;*pb = tmp;
}//向下调整算法 --> 建大堆
void AdjustDownBig(HPDataType* a, size_t size, size_t root) {size_t parent = root;size_t child = 2 * parent + 1; //默认左孩子最大while (child < size){//1.找出左右孩子中小的那个//如果右孩子存在，且右孩子小于size(元素个数)，那么就把默认小的左孩子修改为右孩子if (child + 1 < size && a[child + 1] > a[child]) {++child;}//2.把小的孩子去和父亲比较，如果比父亲小，就交换if (a[child] > a[parent]) {Swap(&a[child], &a[parent]);parent = child;child = 2 * parent + 1;}else {break; //如果孩子大于等于父亲，那么直接跳出循环}}
}//堆排序代码
void HeapSort(int* a, int n) {//建堆：使用向下调整 --> O(N)//从倒数第一个非叶子节点开始（最后一个节点的父亲）//n-1是最后一个节点的下标，(n-1-1)/2最后一个节点的父亲的下标for (int i = (n - 1 - 1) / 2; i >= 0; --i) {AdjustDownBig(a, n, i);}//升序 --> 建大堆size_t end = n - 1; //最后一个元素的下标while (end > 0){Swap(&a[0], &a[end]); //交换第一个元素和最后一个元素AdjustDownBig(a, end, 0);--end;}
}//主函数
int main()
{int a[] = { 4,2,7,8,5,1,0,6 };HeapSort2(a, sizeof(a) / sizeof(int));for (int i = 0; i < sizeof(a) / sizeof(int); ++i) {printf("%d ", a[i]);}return 0;
}

🍑 特性总结

堆排序是一种选择排序，整体主要由 构建初始堆 + 交换堆顶元素和末尾元素并重建堆 两部分组成。

其中构建初始堆经推导复杂度为 $O(n)$，在交换并重建堆的过程中，需交换 $n-1$ 次，而重建堆的过程中，根据完全二叉树的性质，$[log2(n-1),log2(n-2)...1]$ 逐步递减，近似为 $nlogn$。

所以堆排序时间复杂度一般认为就是O(nlogn)级。

• 堆排序使用堆来选数，效率就高了很多。

• 时间复杂度：$O(N\ast logN)$

• 空间复杂度：$O(1)$

• 稳定性：不稳定

3. 总结