选择排序

直接选择排序（Selection Sort）是一种简单的排序算法。它的基本思想是每次从未排序的部分中选择最小（或最大）的元素，将其放到已排序部分的末尾。

版本一：

//直接选择排序1
void SelectSort_1(int* a, int n) {for (int j = n; j > 1; j--) {	//逐渐缩小未排序范围，剩一个元素时不用再进循环int max = 0;for (int i = 1; i < j; i++) {if (a[i] > a[max]) {max = i;}}//找到最大的元素，交换到末尾int tmp = a[j - 1];a[j - 1] = a[max];a[max] = tmp;}
}

版本二：

//直接选择排序2
void SelectSort_2(int* a, int n) {int left = 0;int right = n - 1;while (left < right) {int maxi = left;int mini = right;for (int i = left; i <= right; i++) {	//每次循环，找出一个最大一个最小值if (a[i] < a[mini]) {mini = i;}else if(a[i] > a[maxi]) {maxi = i;}}//最大最小值分别与首尾交换，左右下标指针向中间收缩int tmp = a[left];a[left] = a[mini];a[mini] = tmp;//可能会出现 mini/maxi 在 left/right 位置上//交换一次后，mini/maxi 的位置会改变//修正if (maxi == left) {maxi = mini;}tmp = a[right];a[right] = a[maxi];a[maxi] = tmp;left++;right--;}
}

版本区别

版本二从首尾开始，向中间收缩；消耗的时间减少一半，虽然并没什么用......

时间复杂度

两个循环嵌套，O(n^2)

空间复杂度

原地修改，O(1)

稳定性

存在元素的交换，不稳定

堆排序

堆排序（Heap Sort）是一种基于选择 or 比较的排序算法，它利用了二叉堆数据结构。堆排序分为两个主要的步骤：构建大堆（或小堆）和执行排序。

大致思想：

先建堆、如果升序，就建大堆；

接着对大堆执行排序：首尾元素交换（此时尾元素最大）、将尾元素视作堆之外的元素，将刚刚的首元素向下调整以保证大堆性质；

之后重复上一步操作，即可

//向下调整
void AdjustDown(int* a, int n, int parent) {int child = parent * 2 + 1;	//左孩子while (child < n) {//找出较大的孩子、和父节点对比-->是否需要交换if (child < n - 1 && a[child] < a[child + 1]) {child++;}if (a[child] > a[parent]) {	//建立大堆int tmp = a[child];a[child] = a[parent];a[parent] = tmp;parent = child;child = parent * 2 + 1;}else {break;}}
}

//堆排序
void HeapSort(int* a, int n) {//循环来调整每个子树、以建立大堆for (int i = (n - 1 - 1) / 2; i >= 0; i--) {	//(n-1-1)/2 为最后一个节点的父节点，因为 n-1 是数组最后一个下标AdjustDown(a, n, i);}//对大堆进行操作，以完成升序for (int i = n - 1; i > 0; i--) {//首尾交换int tmp = a[0];a[0] = a[i];a[i] = tmp;//首元素向下调整AdjustDown(a, i, 0);}//此时数组已为升序
}

时间复杂度

堆排序的时间复杂度取决于建堆时的调整次数O(n*logn)、执行排序时每次取出一个元素然后调堆O(n*logn)，所以总体为O(n*logn)

空间复杂度

原地修改，O(1)

稳定性

堆排序依赖于堆的性质和排序过程中的交换操作，不稳定