堆排序

何为堆排序？

顾名思义就是跟堆有关的排序算法

堆排序的时间复杂度为？

O(nlogn)

分析

• 堆排序就是利用优先队列弹出元素达到排序的目的
• 其中建堆有个线性方法，时间复杂度接近O(n)
• 而堆调整元素时间复杂度为O(logn)，而有 n - 1个元素，故弹出元素总时间复杂度为O((n - 1)logn)
• 故堆排序的时间复杂度为O(n + nlogn) ，也就是O(nlogn)

建堆方法

• 以线性建堆法为主

线性建堆法

• 自下而上建堆
• 建立的堆为大顶堆，堆排序后的元素为升序
• 建立的堆为小顶堆，堆排序后的元素为降序

代码如下

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 ;
}

堆排序讲解

看代码注释

代码演示

#include <stdio.h>
#include <stdlib.h>

#define swap(a, b) {\
    __typeof(a) __temp = a;\
    a = b; b = __temp;\
}
//堆为大顶堆的话，堆排序后的元素为升序
//堆为小顶堆的话，堆排序后的元素为降序
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() {
    #define n 10
    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);
    #undef n
    
    return 0;
}