九大经典算法之选择排序、堆排序发布时间：2022/5/31 12:53:16
05 选择排序 （Selection Sort）
原理：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。
void selection_sort(int arr[], int n) {
for (int i = 0;i 1;i++) {
int temp = a;
int t = i;
for (int j = i + 1;j ) {
if (a[j] temp) {
temp = a[j];
t = j;
}
}
a[t] = a;
a = temp;
}
}
空间效率：O(1)
时间效率：最好情况：O(N) 平均情况：O(N^2) 最坏情况：O(N^2)
稳定性（相同元素相对位置变化情况）：不稳定
比较次数与初始状态无关
06 堆排序（Heap Sort）
堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
void heap_sort(int arr[], int n) {
int i,temp;
for (i = (n - 2) / 2; i >= 0; i--)
percdown(arr, n, i);
for (i = n - 1;i > 0;i--) {
temp = arr;
arr = arr[0];
arr[0] = temp;
percdown(arr, i, 0);
}
}
void percdown(int arr[], int n, int i) {
int child;
int x = arr;
for (;i * 2 + 1 1;i = child) {
child = i * 2 + 1;
if (child 1 && arr[child + 1] > arr[child])
child++;
if (x >= arr[child]) break;
else arr = arr[child];
}
arr = x;
}
空间效率：O(1)
时间效率：最好情况：O(Nlog2N) 平均情况：O(Nlog2N) 最坏情况：O(Nlog2N)
稳定性（相同元素相对位置变化情况）：不稳定
转载于:https://www.cnblogs.com/wanghao-boke/p/10424339.html
 |
