【八大排序】选择排序 | 堆排序 + 图文详解！！

📷 江池俊： 个人主页
🔥个人专栏： ✅数据结构冒险记 ✅C语言进阶之路
🌅 有航道的人，再渺小也不会迷途。

---

一、选择排序

1.1 基本思想

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

1.2 算法步骤 + 动图演示

1. 在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素
2. 若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
3. 在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余 1 个元素

1.3 代码实现

这里我们的代码可以稍作优化，在每次选数的时候一次性选出最大和最小的
数，然后依次与数组最后一个和第一个数进行交换。

void Swap(int* p1, int* p2)
{int temp = *p1;*p1 = *p2;*p2 = temp;
}// 选择排序
// 时间复杂度：O(N^2)
// 最好的情况下：O(N^2)
void SelectSort(int* a, int n)
{int begin = 0;int end = n - 1;while (begin < end){int mini = begin, maxi = begin;for (int i = 1; i <= end; i++){if (a[i] < a[mini]){mini = i;}if (a[i] > a[maxi]){maxi = i;}}Swap(&a[begin], &a[mini]);if (maxi == begin){maxi = mini;}Swap(&a[end], &a[maxi]);++begin;--end;}
}

1.4 选择排序特性总结

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

---

二、堆排序

堆排序传送门：二叉树堆的应用实例分析：堆排序 | TOP-K问题

虽然上面已经讲解过堆排序，但在此我们最好还是继续回顾一下堆排序的算法思想。

2.1 堆排序概念

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

2.2 算法步骤 + 动图演示

1. 创建一个堆 H[0……n-1]；（建议使用向下调整建堆）
2. 把堆首（最大值）和堆尾互换；
3. 把堆的尺寸缩小 1（即确定最后一个数的位置），并调用 向下调整算法，目的是把新的数组顶端数据调整到相应位置；
4. 重复步骤 2，直到堆的尺寸为 1。

2.3 代码实现

以下代码以升序排序为例，降序排序类似。
注意：建堆时，使用向下调整法要从倒数第一个非叶子节点（即最后一个叶子节点的父节点）开始。

// 向下调整
void AdjustDown(int* a, int size, int parent)
{int child = parent * 2 + 1;while (child < size){// 假设左孩子小，如果假设错了，更新一下if (child + 1 < size && a[child + 1] > a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}// 堆排序 --- 升序
void HeapSort(int* a, int n)
{// O(N)// 建大堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n,i);}// O(N*logN)int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}

2.4 堆排序特性总结

1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

---