概述
堆排序基于完全二叉树进行排序,
稳定性
堆排序不稳定
时间复杂度
堆排序的时间复杂度为 nlogn
C代码
#include <stdio.h>
#define leftChild(i) (2 * (i) + 1)
void percDown(int array[], int i, int n) {
int tmp;
int child;
// 大顶堆:每次循环都是将父节点与两个孩子的值比较,并将大的值赋给父节点,然后将交换后的孩子节点与孩子节点的孩子节点值比较。。。直到以i为父节点的子树是大顶堆为止
for (tmp = array[i]; leftChild(i) < n; i = child) {
// 1. 找到左孩子
child = leftChild(i);
// 2. 找出两个孩子中较大的一个
if (child != n - 1 && array[child] < array[child + 1]) {
child ++;
}
// 3. 与父节点比较,将孩子中最大的值赋给父节点
if (tmp < array[child]) {// 如果孩子节点比父节点大,则将孩子节点值赋给父节点
array[i] = array[child];
} else {// 孩子节点不如父节点大,证明子树已经有序
break;
}
}
array[i] = tmp;
}
/// 如果 a > b,则交换 a、b的值
void swap(int *a, int *b) {
if (*a > *b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
}
void heapSort(int array[], int n) {
int i;
for (i = n / 2; i >= 0; i --) { // 构建二叉堆,从最后一个父节点开始调整
percDown(array, i, n);
}
for (i = n - 1; i > 0; i --) {
swap(&array[0], &array[i]);
percDown(array, 0, i);
}
}
int main(int argc, const char * argv[]) {
// insert code here...
int i;
// 读入数据
int array[100];
int n;
printf("请输入总数 n = ");
scanf("%d", &n);
for (i = 0; i < n; i ++) {
scanf("%d", &array[i]);
}
heapSort(array, 10);
printf("排序后的数据:");
for (i = 0; i < n; i ++) {
printf("%d", array[i]);
printf(", ");
}
printf("排序完毕");
getchar(); getchar();
printf("Hello, World!\n");
return 0;
}
网友评论