堆排序

  基本思想:先把数组构造成一个大顶堆(父亲节点大于其子节点),然后把堆顶(数组最大值,数组第一个元素)和数组 最后一个元素交换,这样就把最大值放到了数组最后边。把数组长度n-1,再进行构造堆,把剩余的第二大值放到堆顶,输出堆顶(放到 剩余未排序数组最后面)。依次类推,直至数组排序完成。
  将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆,此堆为初始的无序区;
  将堆顶元素R[1]与最后一个元素R[n]交换,此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n];
  由于交换后新的堆顶R[1]可能违反堆的性质,因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆,然后再次将R[1]与无序 区最后一个元素交换,得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1,则整个 排序过程完成。

动图演示

堆排序1

堆排序2

C代码

#include<stdio.h>

//  创建大堆顶,i为当节点,n为堆的大小
//    从第一个非叶子结点i从下至上,从右至左调整结构
//    从两个儿子节点中选出较大的来与父亲节点进行比较
//    如果儿子节点比父亲节点大,则进行交换
void CreatHeap(int a[], int i, int  n) {

    //    注意数组是从0开始计数,所以左节点为2*i+1,右节点为2*i+2
    for (; i >= 0; --i)
    {
        int left = i * 2 + 1;    //左子树节点
        int right = i * 2 + 2;    //右子树节点
        int j = 0;
        //选出左右子节点中最大的
        if (right < n) {
            a[left] > a[right] ? j= left : j = right;
        }
        else
            j = left;
        //交换子节点与父节点
        if (a[j] > a[i]) {
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    }
}

//    进行堆排序,依次选出最大值放到最后面
void HeapSort(int a[], int n) {
    //初始化构造堆
    CreatHeap(a, n/2-1, n);
  //交换第一个元素和最后一个元素后,堆的大小减1
    for (int j = n-1; j >= 0; j--) {

        //最后一个元素和第一个元素进行交换
        int tmp = a[0];
        a[0] = a[j];
        a[j] = tmp;

        int i = j / 2 - 1;
        CreatHeap(a, i, j);
    }
}
int main() {
    int a[] = { 10,6,5,7,12,8,1,3,11,4,2,9,16,13,15,14 };
    int n = sizeof(a) / sizeof(int);
    HeapSort(a, n);
    printf("排序好的数组为:");
    for (int l = 0; l < n; l++) {
        printf("%d ", a[l]);
    }
    printf("\n");
    return 0;
}

分析:

  最差、最优‘平均时间复杂度都为O(nlogn),其中堆的每次创建重构花费O(lgn),需要创建n次。辅助空间O(1)。稳定性 :不稳定。

Copyright © liyang.com 2019 all right reserved,powered by Gitbook该文件修订时间: 2019-07-01 15:22:50

results matching ""

    No results matching ""