每日回顾：简单用C写 选择排序、堆排序
选择排序
直接选择排序（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)
稳定性
堆排序依赖于堆的性质和排序过程中的交换操作，不稳定
原文地址：https://blog.csdn.net/kaneki_11/article/details/142984517
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！