顾名思义就是跟堆有关的排序算法
O(nlogn)
x
for (int i = n >> 1; i >= 1; i--) { //线性建堆法
downUpdate(arr, n, i);
}
void downUpdate(int *arr, int n, int ind) { //小顶堆
if (arr == NULL) return ;
while ((ind << 1) <= n) {
int max_root = ind, l = ind << 1, r = ind << 1 | 1;
if (arr[l] < arr[max_root]) max_root = l;
if (arr[r] < arr[max_root] && r <= n) max_root = r;
if (max_root == ind) break;
swap(arr[ind], arr[max_root]);
ind = max_root;
}
return ;
}
看代码注释
xxxxxxxxxx
//堆为大顶堆的话,堆排序后的元素为升序
//堆为小顶堆的话,堆排序后的元素为降序
void downUpdate(int *arr, int n, int ind) { //建立小顶堆
if (arr == NULL) return ;
while ((ind << 1) <= n) { //自上而下调整堆
int max_root = ind, l = ind << 1, r = ind << 1 | 1;
if (arr[l] < arr[max_root]) max_root = l;
if (arr[r] < arr[max_root] && r <= n) max_root = r;
if (max_root == ind) break;
swap(arr[ind], arr[max_root]);
ind = max_root;
}
return ;
}
void output(int *arr, int n) {
printf("[");
for (int i = 0; i < n; i++) {
i && printf(", ");
printf("%d", arr[i]);
}
printf("]\n");
return ;
}
void heap_sort(int *arr, int n) {
if (arr == NULL) return ;
arr -= 1; //因为数组arr得到的数据从0开始,故使数组0号位置为1号位置
//线性建堆法
// 从最后一个度为大于0的节开始建树
for (int i = n >> 1; i >= 1; i--) { //自下而上建堆
downUpdate(arr, n, i); //建堆
}
printf("建立好的堆如下:\n");
output(arr + 1, n), printf("\n");
for (int i = n; i > 1; i--) {
swap(arr[i], arr[1]);
/*
建立堆后,第一个元素就是最值,
第一次交换第一个元素arr[1]和最后一个元素arr[i],
最后一个元素就是最值了,把最后一个元素不划入待调整的元素内
进行一次调整堆downUpdate(arr, i - 1, 1);
第一个元素就是除了最后一个元素的最值
第二次交换第一个元素arr[1]和最后一个元素arr[i](不把得到的有序数算进去)
依次类推
*/
downUpdate(arr, i - 1, 1);
printf("第%d次调整的堆如下\n", n - i + 1);
output(arr + 1, n), printf("\n");
}
return ;
}
//堆排序
//线性建堆法O(n)
//数组模拟堆
//堆的根节点存在数组一号位置
int main() {
int *arr = (int *)malloc(sizeof(int) * n);
for (int i = 0; i < n; i++) { //构造数据
arr[i] = rand() % 100;
}
printf("排序前:\n"), output(arr, n), printf("\n");
heap_sort(arr, n);
printf("排序后:\n"), output(arr, n);
free(arr);
return 0;
}