笔记

首先构建初始堆，如果是从小到大，那么构建大顶堆，否则构建小顶堆

将堆顶与末尾元素置换

重新调整以0号节点为顶点的堆

注意

不稳定排序

//
// Created by Administrator on 2021/12/13.
//

#include<bits/stdc++.h>

using namespace std;


/**
 * 堆排序
 * */

/**
 * 调整堆
 * @param a
 * @param k 非叶子节点下标，该堆以k为顶点
 * @param len 整个数组的长度
 */
void adjust(int a[], int k, int len) {
    int temp = a[k]; // 记录非叶子节点，它作为该次调整的根
    for(int i = 2*k+1; i < len; i = 2*i+1) {
        if(i+1 < len && a[i] < a[i+1]) {
            i++;
        }
        if(a[i] > temp) {
            a[k] = a[i];
            k = i;
        }
        else {
            break;
        }
    }
    a[k] = temp;
}
void heap_sort(int a[], int len) {
    // 建堆
    for(int k = len/2-1; k >= 0; k--) { // 从后往前选择第一个非叶子节点，调整堆
        adjust(a, k, len);
    }

    for(int j = len-1; j > 0; j--) { // 将堆顶与末尾交换，然后重新调整以0为顶点的堆
        swap(a[j], a[0]);
        adjust(a, 0, j);
    }
}

int main() {
    int a[] = {9, 3, 1, 4, 2, 7, 8, 6, 5};

    int len = sizeof(a)/sizeof(a[0]);

    heap_sort(a, len);

    for(int i = 0; i < len; i++) {
        printf("%d%c", a[i], " \n"[i==len-1]);
    }
    return 0;
}

参考链接

堆排序 (opens new window)