【数据结构】选择排序
🍬个人主页：Yanni.—
🌈数据结构：Data Structure.
🎂C语言笔记：C Language Notes
🏀OJ题分享： Topic Sharing
目录
前言：
基本思想
直接选择排序
思路分析
代码实现
堆排序
知识补充
代码思路分析
向下调整算法
建堆算法
堆排序实现
代码实现
前言：
在前面学习了直接插入排序和希尔排序，今天实现选择排序中的直接选择排序和堆排序。堆排序的效率非常高，认真学习之后会学到一个很好的排序方法！
基本思想
每一次从待排序的数据中选出最小（或最大）的一个元素，存放在序列的起始位置，知道全部待排序的数据元素排完。
直接选择排序
思路分析
代码实现
这里的代码优化了一下，在正常的普通直接选择排序选择出最小的排在第一位情况下，我这里用了头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--;}
}好啦，这就是今天学习的分享啦！看到希望大家的三连呀！
如果有不当之处，欢迎大佬指正！