目录
一、直接选择排序
（一）算法思想
（二）优化版本：双向选择
（三）算法步骤
（四）代码实现
（五）复杂度与稳定性
二、堆排序
（一）排序原理
（二）实现代码（升序，建大根堆）
（三）关键说明
一、直接选择排序
（一）算法思想
每一次从待排序区间中选出最小（或最大）元素，将其与区间起始（或末尾）元素交换，缩小待排序区间，重复操作直至区间长度为 1。【升序选最小放在起始】
（二）优化版本：双向选择
同时查找当前待排序区间的最大值和最小值，将最小值放在区间起始位置，最大值放在区间末尾位置，缩小待排序区间，减少循环次数。
（三）算法步骤
1、初始化边界
设 begin = 0（待排序区间起始），end = n – 1（待排序区间末尾）。
2、查找极值
在[ begin, end ]区间内遍历，记录最小值下标 mini 和最大值下标 maxi，它们的初始值都是begin。然后赋值 i = begin + 1，该指针从前往后遍历：
若arr[ i ] < arr[ mini ]，更新 mini = i；若arr[ i ] > arr[ maxi ]，更新 maxi = i。
3、交换元素
一般我们先交换最小值，再交换最大值。
若 maxi == begin，即最大值在起始位置，此时交换最小值后会被覆盖，需先更新maxi = mini，记录此时最大值被交换的位置。
随即进行交换即可，最小值放起始，交换 arr[mini] 与 arr[begin]；最大值放末尾，交换 arr[maxi] 与 arr[end]。
如果先交换最大值，再交换最小值，也是会遇到相同情况的，如果最小值再末尾就会被覆盖。此时的解决方法就是让mini = maxi，都是一个逻辑 —— 记录最值被交换的位置。
4、缩小区间
begin++，end–，重复步骤 2-3，直至begin >= end。
（四）代码实现
#include"Sort.h"
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
// 直接选择排序
void SelectSort(int* arr, int n)
{
int begin = 0, end = n – 1;
while (begin < end)
{
// 初始极值下标为begin
int mini = begin, maxi = begin;
// 遍历区间找最小、最大值下标
for (int i = begin + 1; i <= end; i++)
{
if (arr[i] < arr[mini])
mini = i;
if (arr[i] > arr[maxi])
maxi = i;
}
// 处理最大值在begin位置的情况
if (maxi == begin)
maxi = mini;
// 进行数据的交换
Swap(&arr[mini], &arr[begin]);
Swap(&arr[maxi], &arr[end]);
// 下次遍历，最值无需参与比较
begin++;
end–;
}
}
（五）复杂度与稳定性
1、时间复杂度
无论数组是否有序，均需遍历 (n-1)+(n-3)+…+1 = n²/2 次，时间复杂度为 O(n²) 。
2、空间复杂度：仅使用常数个额外变量，空间复杂度为O(1)。
3、稳定性
不稳定。例如数组[5, 8, 5, 2, 9]，第一次选择最小值2与5交换后，两个5的相对顺序改变。这种也是属于跳跃式交换，会造成相同数据相对位置的变化。
二、堆排序
（一）排序原理
1、升序排序：建大根堆，每次将堆顶（最大值）与堆尾元素交换，调整剩余元素为大根堆，重复直至数组有序；
2、降序排序：建小根堆，每次将堆顶（最小值）与堆尾元素交换，调整剩余元素为小根堆，重复直至数组有序。
（二）实现代码（升序，建大根堆）
void HeapSort(int* arr, int n)
{
// 第一步：将数组直接建堆（向下调整，O(n)）
// 从最后一个非叶结点开始
for (int i = (n – 1 – 1) / 2; i >= 0; –i) {
AdjustDown(arr, i, n); // 注意调整函数为建立大堆的
}
/*
for (int i = 0; i < n; i++)
AdjustUp(arr, i);
*/
// 第二步：堆顶与堆尾交换，调整堆（O(n log n)）
int end = n – 1;
while (end > 0) {
Swap(&arr[0], &arr[end]); // 堆顶（最大值）放到末尾
AdjustDown(arr, 0, end);// 调整剩余end个元素为大根堆
//AdjustUp(arr, i);
end–; // 缩小堆的范围
}
}
（三）关键说明
1、叶结点无需调整
最后一个非叶结点之后的所有结点都是叶结点，本身满足堆性质，从这里开始能跳过无意义的操作。
2、时间复杂度
单次向下调整的时间复杂度 O (logn)；而 “构建整个堆” 的总时间复杂度是 O (n)。
所以第一个 for 循环的时间复杂度为O(n)，第二个 while 循环的时间复杂度为 O(nlogn)；所以总时间复杂度为 O(n) + O (nlogn)，保留高阶项为 O (nlogn)。
如果换为向上调整建堆，单次的时间复杂度是O (logn)，整体是O (nlogn)；所以总的时间复杂度为O (nlogn) + O (nlogn)，同阶项忽略系数，故依旧为O (nlogn)。
3、空间复杂度：O (1)
Tip：原地排序，无需额外空间。
4、稳定性：不稳定排序，相等元素可能因交换改变相对位置。
以上即为 排序（二）“选择排序” 的全部内容，创作不易，麻烦三连支持一下呗~
