【数据结构】选择排序

🍬个人主页：Yanni.—

🌈数据结构：Data Structure.​​​​​​

🎂C语言笔记：C Language Notes

🏀OJ题分享： Topic Sharing

目录

前言：

基本思想

直接选择排序

思路分析

 代码实现

堆排序

知识补充

代码思路分析

向下调整算法

建堆算法

堆排序实现

代码实现

---

前言：

在前面学习了直接插入排序和希尔排序，今天实现选择排序中的直接选择排序和堆排序。堆排序的效率非常高，认真学习之后会学到一个很好的排序方法！

基本思想

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

直接选择排序

思路分析

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

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

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

 代码实现

这里的代码优化了一下，在正常的普通直接选择排序选择出最小的排在第一位情况下，我这里用了头begin和尾end可以同时把最大值和最小值选出来，然后分别给到相应的位置，这样时间上会比普通的快上一倍。 

void SelectSort(int* a, int n)
{int begin = 0;int end = n-1;while (begin < end){int maxi = begin;int mini = begin;for (int i = begin; i <= end; i++){if (a[i] < a[mini]){mini = i;}if (a[i] > a[maxi]){maxi = i;}}Swap(&a[begin], &a[mini]);//如果maxi与begin位置重叠，需要矫正if (begin == maxi){maxi = mini;}Swap(&a[end], &a[maxi]);begin++;end--;}
}

堆排序

知识补充

1.堆的逻辑结构是一颗完全二叉树

2.堆的物理结构是一个数组

其中父子节点的关系:（这个很重要！！！）

leftchild = parent*2 +1

rightchile = parent*2 +2

parent = (child-1)/2

      

 要用到堆排序，首先要知道两个重要的概念大顶堆和小顶堆。

大顶堆（最大堆）：所有的父亲大于等于孩子。

小顶堆（最小堆）：所以的父亲小于等于孩子。

代码思路分析

向下调整算法

向下调整算法的前提是左右子树必须是小堆（栈顶的数据是最小的）或着大堆（栈顶数据是最大的）。

 如图，图中左右子树都是小堆，那么就可以使用向下调整。

1.将孩子中最大的选出来。

2.将孩子中最大的与父亲比较大小，如果实现的是建小堆的话，孩子比父亲小，孩子就与父亲交换位置。孩子比父亲大，反之。

void AdjustDown(int* a, int n, int root)
{int parent = root;int child = parent*2 + 1;//默认是左孩子 因为右孩子等于左孩子加一while (child < n){//选择出孩子中最大的一个去与父母比较if (child + 1 < n && a[child] < a[child + 1]){child += 1;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent*2 + 1;}else{break;}}
}

建堆算法

如下图，我们知道了向下调整算法，可如果左右子树不是小堆或大堆呢？我们该怎么实先小顶堆或者大顶堆。

可以发现，如果从8这个最后一个父亲节点开始向下调整，再到7，2，5，3。那么就可以实现了。

总而言之就是建堆的思路就是：从倒数第一个非叶子节点开始调整。

for (int i = (n - 1 - 1)/2; i >= 0; i--)
{AdjustDown(a, n, i);
}

图中n-1表示最后一个节点，根据parent = (child -1)/2可以计算出倒数第一个非叶子节点。

堆排序实现

接下来将数据排成升序，那么建堆是建小堆还是建大堆，这就要我们去分析了。

因为如果是建小堆，那么堆顶的数就是最小的，会被直接选择出去作为第一个数，那么只能第二个数作为根，这样剩下的数关系就全乱了，再重新建堆，时间复杂度就会增加跟多，那就失去了堆排序的意义。所以我们这里建大堆。

建大堆之后，再将最大的数据换到最后，不把他看作堆里面的数据，然后进行向下调整算法就可以选出次小，次小换到倒数第二个位置，再继续调堆，选出第三小....

int end = n - 1;
while (end > 0)
{Swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;
}

代码实现

//向下调整
void AdjustDown(int* a, int n, int root)
{int parent = root;int child = parent*2 + 1;//默认是左孩子 因为右孩子等于左孩子加一while (child < n){//选择出孩子中最大的一个去与父母比较if (child + 1 < n && a[child] < a[child + 1]){child += 1;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent*2 + 1;}else{break;}}
}
//堆排序
//升序  建大堆 整体时间复杂度o（N*logN）
void HeapSort(int* a, int n)
{//建堆，时间复杂度为o(N)for (int i = (n - 1 - 1)/2; i >= 0; i--){AdjustDown(a, n, i);}// 排升序，建大堆还是小堆？建大堆int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}
}

好啦，这就是今天学习的分享啦！看到希望大家的三连呀！

如果有不当之处，欢迎大佬指正！