【排序算法】第二章：选择排序----普通选择排序与堆排序的详解和对比

🫡和我一起感受两种算法>排序算法的魅力吧！
在这里插入图片描述

前言：本文可能稍微涉及到一点其他算法>排序算法，若想要了解可以看看：第一章：插入排序`

一、普通选择排序

注意下面几种写法的 Max 和 Min 指的都是元素下标，不是元素本身的值

1.1.一般写法

这种写法，我认为是最好理解的算法>排序算法了，直接暴力遍历找最值交换即可，思路很直接

void SelectSort(int* a, int n) {for (int i = 0; i < n - 1; ++i) {int Min = i;for (int j = i + 1; j < n; ++j) {if (a[Min] > a[j]) Min = j;}Swap(&a[i], &a[Min]);}
}

1.2.一般写法动图演示

在这里插入图片描述

2.1.优化版本

优化思路：既然每一轮都要遍历数组，可以直接将最大值和最小值一起找出来，不用像一般写法：每一轮只找出一个最值，效率较低

每轮找到最大值和最小值就和头尾交换即可

2.2.优化版本的错误写法

void SelectSort2(int* a, int n) {int begin = 0, end = n - 1;while (begin < end) {int Min = begin, Max = end;for (int i = begin + 1; i <= end; ++i) {if (a[i] < a[Min]) Min = i;if (a[i] > a[Max]) Max = i;}Swap(&a[end], &a[Max]);Swap(&a[begin], &a[Min]);begin++;end--;Print(a, 10);}
}

比如下面这种情况

注意： Max 和 Min 指的都是元素下标，不是元素本身的值

遍历一遍记录最值下标是 Max == 8， Min == 9

在这里插入图片描述

若直接交换：Swap(a[Max], a[end]) : {2, 5, 8, 1, 4, 7, 3, 6, 0, 9}

可以发现，原本的 Min == 9 的位置，数值变成了 a[Min] = 9 ??!

此时若直接进行：Swap(a[Min], a[begin]) 必然会出错

⭐原因：Min 的位置和 Max 要交换的目标位置 end 重叠了

⭐方案：加一个 if 语句判断：若 Min == end 则 Min = Max 代表 Min 变成 Max 交换后的位置，就是原有的 Min

if(Min == end) {Min = Max;
}

反过来一样：

若先进行 Swap(a[Min], a[begin]); 则要判断

if(Max == begin) {Max = Min;
}

2.3.优化版本的正确写法：

void SelectSort2(int* a, int n) {int begin = 0, end = n - 1;while (begin < end) {int Min = begin, Max = end;for (int i = begin + 1; i <= end; ++i) {if (a[i] < a[Min]) Min = i;if (a[i] > a[Max]) Max = i;}Swap(&a[end], &a[Max]);if(Min == end) {Min = Max;}Swap(&a[begin], &a[Min]);begin++;end--;Print(a, 10);}
}

3.1.一般的选择排序和优化后选择排序(以及其他几种排序)的性能对比

下面我用代码随机生成 100000 个数据，执行几个算法>排序算法，显示的数据为时间，以 ms 为单位

在这里插入图片描述

可以看到一般选择排序和优化选择排序的在十万数据量的差别较小，但是还是有一定优化的

~~（另外说一下：冒泡“真强”，希尔真强 doge）~~

直接选择排序的特性总结：

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

二、堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种算法>排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

在这里插入图片描述

想要升序排列，应该使用大根堆

而不是常理所想的小根堆：常理中，想要升序，top 应该是最小值才对，但是….

若使用小根堆的堆排序

每轮排序出 top 为最小值，和最后一个元素交换：

依此类推从后往前的序列元素分别是：第 n 小的、第 n-1 小的 … 第 2 小的、第 1 小的

反而是降序排序

因此，依照堆排序的原理，排序应该反着来

// 堆排序void HeapSort(HPDataType* a, int n)
{// 建堆// 因为 Parent = (child - 1) / 2// 需要从最后一个节点的父节点开始向前循环比较// 最后一个节点的下标是 (n-1)// 则 最后一个节点的父节点 是 (  (n - 1)   - 1) / 2for (int i = ((n - 1) - 1) / 2; i >= 0; --i) {AdjustDown(a, n, i);}// 单独一个元素向下调整时间复杂度为 O(logN)  一共调整约 N 轮，时间复杂度为 O(NlogN)int end = n-1;while (end > 0) {Swap(&a[0], &a[end]);   // 把处在第一位置的最优值 和 最后位置的值替换AdjustDown(a, end, 0);  // 再 将 a[0] 进行向下调整end--;}
}void AdjustDown(HPDataType* a, int size, int Parent) {// 孩子取较大的那个: 为了结果为 升序排列int LeftChild = Parent * 2 + 1;int RightChild = Parent * 2 + 2;int child = (RightChild < size && a[LeftChild] < a[RightChild]) ? RightChild : LeftChild;// 注意：这里必须加上：RightChild < size ：因为 若 RightChild 越界，越界的值是随机的，也是可能大于另一方的，也可能被计算进去，// 当 child 为越界下标时，下面的循环就不能进去，导致较小的但是合法的 左孩子LeftChild 没有参与向下调整，则会漏掉一个值没有计算while (child < size && a[child] > a[Parent]) {  //  只要孩子 ：child < size 说明孩子的下标就是合法的Swap(&a[child], &a[Parent]);Parent = child;LeftChild = Parent * 2 + 1;RightChild = Parent * 2 + 2;child = (RightChild < size && a[LeftChild] < a[RightChild]) ? RightChild : LeftChild;}
}

堆排序的特性总结：

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

三、选择排序和堆排序的性能对比

下面我用代码随机生成 100000 个数据，执行两个算法>排序算法，显示的数据为时间，以 ms 为单位
在这里插入图片描述

可以见识到堆排序 O(nlogn) 的威力了吧，（薄纱 O(n^2)）

四、浅谈各种算法>排序算法的意义

上一章节讲解的希尔排序中提到

希尔排序时间复杂度大概在 $O(n^{1.3})$ 略大于 $O (n l o g n)$

我们在此将希尔排序 ( $O(n^{1.3})$ ) 和堆排序（ $O (n l o g n)$ ）对比一下

十万数据量级：在这里插入图片描述

千万数据量级：在这里插入图片描述

一亿 数据量级：在这里插入图片描述

希尔排序在后面数据量级升级后，反超了堆排序，说明了一点

时间复杂度，看的是最坏的情况，有时候不能用于真正的速度对比，算法的运行速度和算法思想、数据的实际情况等等相关

同时要注意，我们堆排序之前，还要进行 O(n) 的建堆，我们也不能忽略 O(n) 的影响

⭐总结：每个排序都有其存在的意义，不能只盯着算法>排序算法的时间复杂度大小的比较，更多的是看适不适合当前实际的应用场景，，比如堆排序虽然时间复杂度较为优秀，但是，例如当数据基本有序时，使用插入排序都能秒了堆排，不信？🤣 看下面

如图：我先用希尔排序将数组 a2 排序成有序的，营造数据有序场景，来测试插入排序和堆排序

在这里插入图片描述

😎😎谁更强一目了然！！

🫡至此，第二章完结！

【若文章有什么错误或则可以改进的地方，非常欢迎评论区讨论或私信指出】**