【排序3】选择排序：高效的排序算法之美

👻选择排序 选择排序的基本思想： 每一趟(第i趟)在后面n-i+1(i=1，2，···，n-1)个待排序元素中 选取关键字最小的元素，作为有序子序列的第i个元素，直到n—1趟做完，待排序元素只剩下一个，就不用再选了。

🎡1、直接选择排序

直接选择排序是一种简单直观的排序算法。它的基本思想是每次从未排序的部分中找到最小（或最大）的元素，将其与未排序部分的第一个元素交换位置，然后缩小未排序部分的范围，继续进行选择和交换，直到整个序列有序。

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

如图：

在这里插入图片描述

🪄代码示例：

🎉【直接选择排序的特性总结】

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

🎡2、堆排序

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

在这里插入图片描述

堆排序的关键是构造初始堆。n个结点的完全二叉树，最后一个结点是第[n/2]个结点的孩子。对第[n/2]个结点为根的子树进行筛选，使该子树成为堆。之后向前依次对各结点为根的子树进行筛选，看该结点值是否大于其左右子结点的值，若不大于，则将左右子结点中的较大值与之交换，交换后可能破坏下一级的堆，于是继续采用上述方法构造下一级的堆，直到以该结点为根的子树构成堆为止。反复利用上述调整堆的方法建堆，直到根结点。

如图：

在这里插入图片描述

输出栈顶元素后，将堆的最后一个元素与栈顶元素交换，此时堆的性质被破坏。

在这里插入图片描述

同时，堆也支持插入操作。对堆进行插入操作时，先将新结点放在堆的末端，再对这个新结点向上执行调整操作。

在这里插入图片描述

🪄代码示例：

🎉【堆排序的特性总结】

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

🎉OK！今天的分享就到这里了，后面还会分享更多排序算法，敬请关注喔！！！✌️