内部排序算法：堆排序

基本思想

  • 堆的定义

n个关键字序列kl，k2，…，kn称为堆，当且仅当该序列满足如下性质之一（简称堆性质）：

  1. ki≤k2i且ki≤k2i+1 或
  2. ki≥k2i且ki≥k2i+1（1≤i≤FLOOR(n/2)）

若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于（或不小于）其左右孩子（若 存在）结点的关键字。

  • 小根堆：根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最小的。
  • 大根堆：根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最大的。

我们可以选择大根堆或者小根堆中的任意一个来进行排序。

  • 排序思想

用大根堆排序的基本思想：

  1. 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区。
  2. 再将关键字最大的记录R[1]（即堆顶）和无序区的最后一个记录R[n]交换，由此得 到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key。
  3. 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。 然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由 此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系 R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。

算法实现

堆排序算法，Java实现，代码如下所示：

01 public abstract class Sorter {
02 public abstract void sort(int[] array);
03 }
04
05 public class HeapSorter extends Sorter {
06
07 public void sort(int[] array) {
08 heapSort(array);
09 }
10
11 /**
12 * <p>堆排序方法
13 * <p>基于大根堆的堆排序方法
14 */
15 private void heapSort(int[] array) {
16 Integer tmp; // 用于交换的暂存单元
17 buildHeap(array); // 执行初始建堆，并调整
18 for (int i = 0; i < array.length; i++) {
19 // 交换堆顶元素array[0]和堆中最后一个元素array[array.length-1-i]
20 tmp = array[0];
21 array[0] = array[array.length - 1 - i];
22 array[array.length - 1 - i] = tmp;
23 // 每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整
24 adjustHeap(array, 0, array.length - 1 - i);
25 }
26 }
27
28 /**
29 * <p>
30 * 建堆方法
31 * <p>
32 * 调整堆中0~array.length/2个结点，保持堆的性质
33 *
34 */
35 private void buildHeap(int[] array) {
36 // 求出当前堆中最后一个存在孩子结点的索引
37 int pos = (array.length - 1) / 2;
38 // 从该结点结点开始，执行建堆操作
39 for (int i = pos; i >= 0; i--) {
40 adjustHeap(array, i, array.length); // 在建堆过程中，及时调整堆中索引为i的结点
41 }
42 }
43
44 /**
45 * <p>
46 * 调整堆的方法
47 *
48 * @param s 待调整结点的索引
49 * @param m 待调整堆的结点的数量(亦即：排除叶子结点)
50 */
51 private void adjustHeap(int[] array, int s, int m) {
52 Integer tmp = array[s]; // 当前待调整的结点
53 int i = 2 * s + 1; // 当前待调整结点的左孩子结点的索引(i+1为当前调整结点的右孩子结点的索引)
54 while (i < m) {
55 if (i + 1 < m && array[i] < array[i + 1]) { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点)
56 i = i + 1;
57 }
58 if (array[s] < array[i]) {
59 array[s] = array[i]; // 孩子结点大于当前待调整结点，将孩子结点放到当前待调整结点的位置上
60 s = i; // 重新设置待调整的下一个结点的索引
61 i = 2 * s + 1;
62 } else { // 如果当前待调整结点大于它的左右孩子，则不需要调整，直接退出
63 break;
64 }
65 array[s] = tmp; // 当前待调整的结点放到比其大的孩子结点位置上
66 }
67 }
68 }

堆排序算法，Python实现，代码如下所示：

01 class Sorter:
02 '''
03 Abstract sorter class, which provides shared methods being used by
04 subclasses.
05 '''
06 __metaclass__ = ABCMeta
07
08 @abstractmethod
09 def sort(self, array):
10 pass
11
12 class HeapSorter(Sorter):
13 '''
14 Heap sorter
15 '''
16 def sort(self, array):
17 length = len(array)
18 self.__heapify(array)
19 i = 0
20 while i<length:
21 array[0], array[length-1-i] = array[length-1-i], array[0]
22 self.__sift_down(array, 0, length-1-i)
23 i = i + 1
24
25 def __heapify(self, array):
26 length = len(array)
27 pos = (length-1) // 2
28 i = pos
29 while i>=0:
30 self.__sift_down(array, i, length)
31 i = i - 1
32
33 def __sift_down(self, array, s, m):
34 tmp = array[s]
35 i = 2 * s + 1
36 while i<m:
37 if i+1<m and array[i]<array[i+1]:
38 i = i + 1
39 if array[s]<array[i]:
40 array[s] = array[i]
41 s = i
42 i = 2 * s + 1
43 else:
44 break
45 array[s] = tmp

排序过程

假设待排序数组为array = {94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}，数组大小为20。

第一步：初始建堆
首先执行的初始建堆（在建堆的过程中需要调整堆）。过程如下：

  • 求出当前堆中最后一个存在孩子结点的索引

这里，把数组array看做是一棵完全二叉树，这样数组每个索引位置上的元素都对应到二叉树中的结点，如图所示：


其中需要在这棵树中找到最后一个有孩子最大的一个结点的索引：
pos = (array.length-1)/2 = (20-1)/2 = 9
也就是索引为9的array[9] = 76，由后至前层次遍历，从array[9]一直到array[0]，对初始堆进行调整。

  • 对初始堆进行调整
  1. 调整结点array[9] = 76：

先比较array[9] = 76的左右孩子：s = 9，i = 2*s+1 = 2*9 + 1 = 19，而i+1 = 19 + 1 = 20 > m = array.length-1 = 20 -1 = 19(array[9] = 76没有右孩子)，只需要将array[9] = 76与array[i] = array[19] = 49比较，因为array[9] = 76>array[i] = array[19] = 49，则不需要交换array[9] = 76与array[i] = array[19] = 49，继续对下一个结点（也就是array[8] = 55）进行调整；

调整结点array[8] = 55：

先比较array[8] = 55的左右孩子：s = 8，i = 2*s+1 = 2*8 + 1 = 17,，而i+1 = 17 + 1 = 18 < m = array.length-1 = 20-1 = 19(array[8] = 55存在右孩子)，左孩子array[i] = array[17] = 65小于右孩子array[i+1] = array[18] = 76，只需要将array[8] = 76与右孩子array[i+1] = array[18] = 76比较，因为array[8] = 55<array[i+1] = array[18] = 76，则需要交换array[8] = 55与array[i+1] = array[18] = 76，交换后如图所示：


继续对下一个结点（也就是array[8] = 55）进行调整；

调整结点array[7] = 37：

显然，不需要交换；

调整结点array[6] = 0：

调整结果如图所示：


调整结点array[5] = 9：

调整结果如图所示：


调整结点array[4] = 26：

调整结果如图所示：


调整结点array[3] = 76：

显然，不需要交换。

调整结点array[2] = 34：

调整结果如图所示：


调整结点array[1] = 12：

调整结果如图所示：


调整结点array[0] = 94：

显然，不需要交换。

至此，对初始堆的调整完成。

第二步：第一次交换
将堆顶元素与最后一个元素交换，即array[0] = 94与最后一个元素array[19] = 49交换，如图所示：


此时，数组为：
array = {49,76,90,12,76,68,34,37,76,26,37,5,9,83,0,37,12,65,55,94}
数组中最大的元素被交换到了数组的末尾，也就是array[19] = 94是最终排好序的固定位置。

第三步：调整堆
过程同前面类似。
……
最后经过堆排序得到有序的数组。

算法分析

  • 时间复杂度

堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成。
堆排序的最坏时间复杂度为O(nlgn)。堆排序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。

  • 空间复杂度

堆排序过程中，需要调整堆，交换待排序记录需要一个临时存储单元，所以空间复杂度为O(1)。

  • 排序稳定性

堆排序是就地排序，它是不稳定的排序方法。

时间： 2024-10-30 10:45:01

内部排序算法：堆排序的相关文章

基于C++实现的各种内部排序算法汇总_C 语言

提起排序算法相信大家都不陌生,或许很多人已经把它们记得滚瓜烂熟,甚至随时可以写出来.是的,这些都是最基本的算法.这里就把各种内部排序算法总结归纳了一下,包括插入排序(直接插入排序,折半插入排序,希尔排序).交换排序(冒泡排序,快速排序).选择排序(简单选择排序,堆排序).2-路归并排序.(另:至于堆排序算法,前面已经有一篇文章针对堆排序的算法实现做了详细的描述) C++实现代码如下: /*******************************************************

常用内部排序算法之五：希尔排序

前言 在前面介绍常用内部排序算法的文章中,我们知道在简单排序算法中,直接插入排序算法的时间复杂度是要优于冒泡排序和简单选择排序的.而这里要讲的希尔排序则是优于直接插入排序的.而且希尔排序打破了原来简单排序中时间复杂度不能超过O(n2)的神话.这也是希尔排序伟大的地方,而且希尔排序不同于之前三种简单排序,希尔排序是以一个科学家的名字进行命名的. 希尔排序的原理 由于希尔排序是在直接插入排序的基础上进行改进的,所以为了更好理解希尔排序,需要再次将直接插入排序请出来.我们知道直接插入排序的基本思想是将

常用内部排序算法之二：快速排序

前言 快速排序可以说是内部排序算法中的高手,之所以称为快速排序,是因为快速排序算法从整体性能上讲是排序冠军.快速排序算法的思想是:通过一趟快速排序将待排序的记录分割成独立的两部分,其中一部分记录的关键字均比另一部分的记录的关键字小,则可分别对这两部分记录继续进行排序,达到整个记录有序.实现快速排序算法的核心是partition函数,这个函数的主要目的先选取当中的一个关键字(称为枢轴),然后尽可能将他放在一个位置,使得它左边的值都比它小,右边的值比它大. 快速排序算法实现 package com.

常用内部排序算法之三：堆排序

前言 堆排序是以堆为原型的排序.堆首先是一棵二叉树,具有以下两个性质:每个节点的值大于或者等于其左右孩子结点的值,称为大顶堆:或者每个节点的值都小于或者等于其左右孩子结点的值,称为小顶堆.从这个定义中可以发现,堆得根节点要么是最大值要么是最小值.实现堆排序的基本思想是:将待排序的序列构造成一个大顶堆或者小顶堆.此时整个堆满足根节点是最大值或者最小值.将根节点移走,并与堆数组的最后一个值进行交换,这样的话最后一个值就是最大值或者最小值了.然后将剩余n-1(假设原来总共有n个元素)未排序的序列重新构

内部排序算法的总结

内部排序总结 这篇博文我们简要地总结下各种内部排序方法. 这10种排序算法中,前面7种属于建立在"比较"基础上的排序算法,通过决策树已经证明,任何基于比较进行的排序算法的时 间复杂度不可能再优于O(n*logn).后面3种不是建立在比较的基础上的,因此,可以达到线性运行时间. 下面我们给出各种排序方法的时空复杂度的表格(属于自己总结,有不对的地方,希望大家指正或补充). 返回栏目页:http://www.bianceng.cnhttp://www.bianceng.cn/Program

内部排序：堆排序

前言 堆排序.快速排序.归并排序(下篇会写这两种排序算法)的平均时间复杂度都为O(n*logn).要弄清楚堆排序,就要先了解下二叉堆这种数据结构.本文不打算完全讲述二叉堆的所有操作,而是着重讲述堆排序中要用到的操作.比如我们建堆的时候可以采用堆的插入操作(将元素插入到适当的位置,使新的序列仍符合堆的定义)将元素一个一个地插入到堆中,但其实我们完全没必要这么做,我们有执行操作更少的方法,后面你会看到,我们基本上只用到了堆的删除操作,更具体地说,应该是删除堆的根节点后,将剩余元素继续调整为堆的操作.

内部排序之堆排序的实现详解_C 语言

堆排序(Heap Sort)只需要一个记录大小的辅助空间,每个待排序的记录仅占有一个存储空间.(1)基本概念a)堆:设有n个元素的序列:{k1, k2, ..., kn}对所有的i=1,2,...,(int)(n/2),当满足下面关系:                                                                  ki≤k2i,ki≤k2i+1                                                  或

内部排序算法：基数排序

基本思想 基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较.由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数. 基数排序可以采用两种方式: LSD(Least Significant Digital):从待排序元素的最右边开始计算(如果是数字类型,即从最低位个位开始). MSD(Most Significant Digital):从待排序元素的最左边开始计算(如果是数字类型,即从最高位开始). 我们以L

常用内部排序算法之四：简单选择排序、直接插入排序和冒泡排序

前言 之所以把这三类算法放在一块,是因为除此之外的算法都是在这三类算法的基础上进行优化的.简单选择排序的思想是每一趟n−i+1(i=1,2,...,n−1)个记录中选择最小的记录作为有序序列的第i个记录.直接插入排序的思想是将一个记录插入到已经排好序的有序序列中,从而得到一个新的.记录数增加1的有序表.冒泡排序的算法思想是不断在交换,通过交换完成最终的排序,每一趟的交换就会把最大的记录取出来,下一趟则会把第二大的记录取出来,这样每进行一趟交换就把一个记录取出来的过程称为冒泡. 简单选择排序算法