排序六 堆排序

堆的概念

在介绍堆排序之前,首先需要说明一下,堆是个什么玩意儿。

是一棵顺序存储完全二叉树

其中每个结点的关键字都不大于其孩子结点的关键字,这样的堆称为小根堆

其中每个结点的关键字都不小于其孩子结点的关键字,这样的堆称为大根堆

举例来说,对于n个元素的序列{R0, R1, ... , Rn}当且仅当满足下列关系之一时,称之为堆:

(1) Ri <= R2i+1 且 Ri <= R2i+2 (小根堆)

(2) Ri >= R2i+1 且 Ri >= R2i+2 (大根堆)

其中i=1,2,…,n/2向下取整; 

如上图所示,序列R{3, 8, 15, 31, 25}是一个典型的小根堆。

堆中有两个父结点,元素3和元素8。

元素3在数组中以R[0]表示,它的左孩子结点是R[1],右孩子结点是R[2]。

元素8在数组中以R[1]表示,它的左孩子结点是R[3],右孩子结点是R[4],它的父结点是R[0]。可以看出,它们满足以下规律

设当前元素在数组中以R[i]表示,那么,

(1) 它的左孩子结点是:R[2*i+1];

(2) 它的右孩子结点是:R[2*i+2];

(3) 它的父结点是:R[(i-1)/2];

(4) R[i] <= R[2*i+1] 且 R[i] <= R[2i+2]。

要点

首先,按堆的定义将数组R[0..n]调整为堆(这个过程称为创建初始堆),交换R[0]和R[n];

然后,将R[0..n-1]调整为堆,交换R[0]和R[n-1];

如此反复,直到交换了R[0]和R[1]为止。

以上思想可归纳为两个操作:

(1)根据初始数组去构造初始堆(构建一个完全二叉树,保证所有的父结点都比它的孩子结点数值大)。

(2)每次交换第一个和最后一个元素,输出最后一个元素(最大值),然后把剩下元素重新调整为大根堆。

当输出完最后一个元素后,这个数组已经是按照从小到大的顺序排列了。

先通过详细的实例图来看一下,如何构建初始堆。

设有一个无序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 }。

构造了初始堆后,我们来看一下完整的堆排序处理:

还是针对前面提到的无序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 } 来加以说明。

相信,通过以上两幅图,应该能很直观的演示堆排序的操作处理。

核心代码

public void HeapAdjust(int[] array, int parent, int length) {
 int temp = array[parent]; // temp保存当前父节点
  int child = 2 * parent + 1; // 先获得左孩子
  
 while (child < length) {
 // 如果有右孩子结点,并且右孩子结点的值大于左孩子结点,则选取右孩子结点
  if (child + 1 < length && array[child] < array[child + 1]) {
             child++;
         }
 
 // 如果父结点的值已经大于孩子结点的值,则直接结束
  if (temp >= array[child])
 break;
 
 // 把孩子结点的值赋给父结点
         array[parent] = array[child];
 
 // 选取孩子结点的左孩子结点,继续向下筛选
         parent = child;
         child = 2 * child + 1;
     }
 
     array[parent] = temp;
 }
 
 public void heapSort(int[] list) {
 // 循环建立初始堆
  for (int i = list.length / 2; i >= 0; i--) {
         HeapAdjust(list, i, list.length);
     }
 
 // 进行n-1次循环,完成排序
  for (int i = list.length - 1; i > 0; i--) {
 // 最后一个元素和第一元素进行交换
  int temp = list[i];
         list[i] = list[0];
         list[0] = temp;
 
 // 筛选 R[0] 结点,得到i-1个结点的堆
         HeapAdjust(list, 0, i);
         System.out.format("第 %d 趟: \t", list.length - i);
         printPart(list, 0, list.length - 1);
     }
 }

算法分析

堆排序算法的总体情况

排序类别

排序方法

时间复杂度

空间复杂度

稳定性

复杂性

平均情况

最坏情况

最好情况

选择排序

堆排序

O(nlog2n)

O(nlog2n)

O(nlog2n)

O(1)

不稳定

较复杂

时间复杂度

堆的存储表示是顺序的。因为堆所对应的二叉树为完全二叉树,而完全二叉树通常采用顺序存储方式。

当想得到一个序列中第k个最小的元素之前的部分排序序列,最好采用堆排序。

因为堆排序的时间复杂度是O(n+klog2n),若k≤n/log2n,则可得到的时间复杂度为O(n)

算法稳定性

堆排序是一种不稳定的排序方法。

因为在堆的调整过程中,关键字进行比较和交换所走的是该结点到叶子结点的一条路径,

因此对于相同的关键字就可能出现排在后面的关键字被交换到前面来的情况。

完整参考代码

JAVA版本

代码实现

以下范例是对上文提到的无序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 } 进行排序。

public class HeapSort {
 
    public void HeapAdjust(int[] array, int parent, int length) {
        int temp = array[parent]; // temp保存当前父节点
        int child = 2 * parent + 1; // 先获得左孩子
 
        while (child < length) {
            // 如果有右孩子结点,并且右孩子结点的值大于左孩子结点,则选取右孩子结点
            if (child + 1 < length && array[child] < array[child + 1]) {
                child++;
            }
 
            // 如果父结点的值已经大于孩子结点的值,则直接结束
            if (temp >= array[child])
                break;
 
            // 把孩子结点的值赋给父结点
            array[parent] = array[child];
 
            // 选取孩子结点的左孩子结点,继续向下筛选
            parent = child;
            child = 2 * child + 1;
        }
 
        array[parent] = temp;
    }
 
    public void heapSort(int[] list) {
        // 循环建立初始堆
        for (int i = list.length / 2; i >= 0; i--) {
            HeapAdjust(list, i, list.length);
        }
 
        // 进行n-1次循环,完成排序
        for (int i = list.length - 1; i > 0; i--) {
            // 最后一个元素和第一元素进行交换
            int temp = list[i];
            list[i] = list[0];
            list[0] = temp;
 
            // 筛选 R[0] 结点,得到i-1个结点的堆
            HeapAdjust(list, 0, i);
            System.out.format("第 %d 趟: \t", list.length - i);
            printPart(list, 0, list.length - 1);
        }
    }
 
    // 打印序列
    public void printPart(int[] list, int begin, int end) {
        for (int i = 0; i < begin; i++) {
            System.out.print("\t");
        }
        for (int i = begin; i <= end; i++) {
            System.out.print(list[i] + "\t");
        }
        System.out.println();
    }
 
    public static void main(String[] args) {
        // 初始化一个序列
        int[] array = {
                1, 3, 4, 5, 2, 6, 9, 7, 8, 0
        };
 
        // 调用快速排序方法
        HeapSort heap = new HeapSort();
        System.out.print("排序前:\t");
        heap.printPart(array, 0, array.length - 1);
        heap.heapSort(array);
        System.out.print("排序后:\t");
        heap.printPart(array, 0, array.length - 1);
    }
}

运行结果

排序前:    1   3   4   5   2   6   9   7   8   0  
 第 1 趟:   8   7   6   5   2   1   4   3   0   9  
 第 2 趟:   7   5   6   3   2   1   4   0   8   9  
 第 3 趟:   6   5   4   3   2   1   0   7   8   9  
 第 4 趟:   5   3   4   0   2   1   6   7   8   9  
 第 5 趟:   4   3   1   0   2   5   6   7   8   9  
 第 6 趟:   3   2   1   0   4   5   6   7   8   9  
 第 7 趟:   2   0   1   3   4   5   6   7   8   9  
 第 8 趟:   1   0   2   3   4   5   6   7   8   9  
 第 9 趟:   0   1   2   3   4   5   6   7   8   9  
 排序后:    0   1   2   3   4   5   6   7   8   9  

参考资料

《数据结构习题与解析》(B级第3版)

相关阅读

欢迎阅读 程序员的内功——算法 系列

示例源码:https://github.com/dunwu/algorithm-notes

说明

感谢 @放学路上的小学生 的指正,他提到的第一种修改方法是有效的。本文已修改。

在我的 github 中,提供了单元测试来进行排序验证:

样本包含:数组个数为奇数、偶数的情况;元素重复或不重复的情况。且样本均为随机样本,实测有效。

https://github.com/dunwu/algorithm-notes/blob/master/codes/src/test/java/io/github/dunwu/algorithm/sort/SortStrategyTest.java

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏二进制文集

LeetCode 动态规划 题目分类汇总

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the...

996
来自专栏小樱的经验随笔

HDU 1024 Max Sum Plus Plus【动态规划求最大M子段和详解 】

Max Sum Plus Plus Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/...

2954
来自专栏武培轩的专栏

剑指Offer-翻转单词顺序列

牛客最近来了一个新员工Fish,每天早晨总是会拿着一本英文杂志,写些句子在本子上。同事Cat对Fish写的内容颇感兴趣,有一天他向Fish借来翻看,但却读不懂它...

662
来自专栏Bingo的深度学习杂货店

从M走到N最少步数

假设一个人站在 X 轴的正半轴上,起始点在 M 点(0 <= M <= 100000),他每次可以向左走一步,向右走一步,或者走到所在坐标乘以2的位置,最终来到...

422
来自专栏决胜机器学习

PHP数据结构(十五) ——哈希表​

PHP数据结构(十五)——哈希表 (原创内容,转载请注明来源,谢谢) 一、概述 查找的效率与查找的次数有关,查找的次数越少速度越快。因此,希望能够一次查找出结...

3909
来自专栏互联网大杂烩

二分查找

在对线性表的操作中,经常需要查找某一个元素在线性表中的位置。此问题的输入是待查元素x和线性表L,输出为x在L中的位置或者x不在L中的信息。

633
来自专栏有趣的Python

算法与数据结构(四)堆排序:优先队列实现

堆排序 排序次要的,接触新的数据结构;堆 堆和优先队列 Heap and Priority Queue 什么是优先队列? 普通队列:先进先出;后进后出 优先队...

3325
来自专栏用户画像

7.2.1 直接插入排序

插入排序是一种简单直观的排序方法,其基本思想在于每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子序列,直到全部记录插入完成。

752
来自专栏算法channel

1800字普林斯顿大学课程浓缩笔记:程序员必知的算法之查找和排序算法

老生常谈,偶尔遇到阐述这两类问题相关的极好素材,它们结合示意图,言简意赅,清晰明了。故分享出来。

510
来自专栏积累沉淀

hash算法原理详解

一.概念 哈希表就是一种以 键-值(key-indexed) 存储数据的结构,我们只要输入待查找的值即key,即可查找到其对应的值。 哈希的思路很简单,如果所有...

3295

扫码关注云+社区