堆排序(详情讲解)

1.概述

     

  小顶堆：每个节点的值都小于或者等于它的左右子节点的值

 

2.0示意图

 大堆顶：

• 堆排序是一种重要的选择排序方法，它只需要一个记录大小的辅助存储空间，每个待排序的记录仅占用一个记录大小的存储空间，因此弥补了树形选择排序的弱点。

• 大顶堆：每个节点的值都大于或者等于它的左右子节点的值。

• 一般升序采用大顶堆，降序采用小顶堆

• 基本思想：

  • 首先将这n条记录按关键字值的大小建立堆（称为初始堆），将堆顶元素r[0]与r[n-1]交换

  • 然后，将剩下的{r[0]..r[n-2]}序列调整成堆

  • 再将 r[0]与r[n-2]交换，再将剩下的{r[0]..r[n-3]}序列调整成堆

  • 如此反复，直到整个序列有序。

  • 这个过程称为堆排序

• 要实现堆排序需解决以下两个主要问题：

  1. 将n条记录的序列按关键字值的大小建成初始堆。

  2. 将堆顶记录r[0]与r[i]交换后，如何将序列{r[0]..r[i-1]}按其关键字值的大小调整成一个新堆

3.0筛选法调整堆：算法

• 代码

//将以low为根的子树调整成小顶堆，low、high是序列下界和上界public void sift(int low, int high) {    int i = low;    //子树的根    int j = 2 * i + 1;    //j为i结点的左孩子    RecordNode temp = r[i];    while (j < high) {  //沿较小值孩子结点向下筛选 if (j  0) {     j++; //数组元素比较,j为左右孩子的较小者 } if (temp.key.compareTo(r[j].key) > 0) { //若父母结点值较大     r[i] = r[j];    //孩子结点中的较小值上移     i = j;     j = 2 * i + 1; } else {     j = high + 1;   //退出循环 }    }    r[i] = temp;     //当前子树的原根值调整后的位置//  System.out.print("sift  " + low + ".." + high + "  ");//  display();

• 测试

public class TestSeqList11_sift {    public static void main(String[] args) throws Exception { int[] arr = {13,25,18,33,58,95,46,63}; SeqList seqList = new SeqList(arr.length); System.out.print("序列号:"); for (int i = 0; i < arr.length; i++) {     System.out.print("  " + i);     seqList.insert(i, new RecordNode(arr[i])); } System.out.println(); System.out.print("原数据："); seqList.display(); // 树形选择排序(锦标赛排序) RecordNode temp = seqList.r[0]; seqList.r[0] = seqList.r[arr.length - 1]; seqList.r[arr.length-1] = temp; System.out.print("交换值："); seqList.display(); seqList.sift(0, arr.length-1); System.out.print("调整后："); seqList.display();    }}//树形选择排序(锦标赛排序)//序列号:  0  1  2  3  4  5  6  7//原数据： 13 25 18 33 58 95 46 63//交换值： 63 25 18 33 58 95 46 13//调整后： 18 25 46 33 58 95 63 13

4.0建初始堆

• 为一个无序序列构建堆的过程，就是对完全二叉树从下往上反复筛选的过程。也就是说每一个结点与自己的孩子结点进行比较，从而选择出最小元素。

• 有孩子的结点，称为非叶子结点，在完全二叉树中，最后一个非叶子结点的编号为 ⌊n/2⌋ -1

• 因此我们从最后一个非叶子结点开始调整，最后调整到根节点

       //序列号:          0  1  2  3  4  5  6  7
       //sift  3..8   33 25 46 13 58 95 18 63
       //sift  2..8   33 25 18 13 58 95 46 63
       //sift  1..8   33 13 18 25 58 95 46 63
       //sift  0..8   13 25 18 33 58 95 46 63

 

5.0堆排序：分析

• 步骤：

1. 首先通过对 ⌊n/2⌋ -1记录进行调整，构建堆。

2. 然后将堆顶的元素，与最后一个元素交换，获得最小元素。

3. 接着将剩余无序序列，调整成小顶堆，重复步骤2，获得每一次调整后的最小值

4. 直到调整到根，从而获得排序序列

6.0堆排序：算法

• 代码

//【算法7.12】 堆排序算法public void heapSort() {   // System.out.println("堆排序");    int n = this.curlen;    RecordNode temp;    for (int i = n / 2 - 1; i >= 0; i--) {//创建堆 sift(i, n);    }    System.out.println("堆构建完成");    for (int i = n - 1; i > 0; i--) {//每趟将最小值交换到后面，再调整成堆 temp = r[0]; r[0] = r[i]; r[i] = temp; sift(0, i);    }}

• 测试

public class TestSeqList12_heap {    public static void main(String[] args) throws Exception { int[] arr = {33,25,46,13,58,95,18,63}; SeqList seqList = new SeqList(arr.length); System.out.print("序列号:\t\t"); for (int i = 0; i < arr.length; i++) {     System.out.print("  " + i);     seqList.insert(i, new RecordNode(arr[i])); } System.out.println(); // 树形选择排序(锦标赛排序) seqList.heapSort();    }}//树形选择排序(锦标赛排序)//序列号:    0  1  2  3  4  5  6  7//sift  3..8   33 25 46 13 58 95 18 63//sift  2..8   33 25 18 13 58 95 46 63//sift  1..8   33 13 18 25 58 95 46 63//sift  0..8   13 25 18 33 58 95 46 63//堆构建完成//sift  0..7   18 25 46 33 58 95 63 13//sift  0..6   25 33 46 63 58 95 18 13//sift  0..5   33 58 46 63 95 25 18 13//sift  0..4   46 58 95 63 33 25 18 13//sift  0..3   58 63 95 46 33 25 18 13//sift  0..2   63 95 58 46 33 25 18 13//sift  0..1   95 63 58 46 33 25 18 13

7.0性能分析

• 空间复杂度：需要一个记录辅助存储空间，O(1)

• 最坏时间复杂度：O(nlog2n)

• 堆排序是==不稳定==的排序算法。