堆排序

作者: NapoleonY | 来源:发表于2018-11-21 12:50 被阅读9次

    概述

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

    稳定性

    堆排序不稳定

    时间复杂度

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

    相关文章

      网友评论

          本文标题:堆排序

          本文链接:https://www.haomeiwen.com/subject/ocaqqqtx.html