堆排序

概述

堆排序基于完全二叉树进行排序，

稳定性

堆排序不稳定

时间复杂度

堆排序的时间复杂度为 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;
}