开发者社区> shiyanjuncn> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

内部排序算法:堆排序

简介:
+关注继续查看

基本思想

  • 堆的定义

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看做是一棵完全二叉树,这样数组每个索引位置上的元素都对应到二叉树中的结点,如图所示:

heapsort
其中需要在这棵树中找到最后一个有孩子最大的一个结点的索引:
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,交换后如图所示:

heapsort-1
继续对下一个结点(也就是array[8] = 55)进行调整;

调整结点array[7] = 37:

显然,不需要交换;

调整结点array[6] = 0:

调整结果如图所示:

heapsort-2

调整结点array[5] = 9:

调整结果如图所示:

heapsort-3

调整结点array[4] = 26:

调整结果如图所示:

heapsort-4

调整结点array[3] = 76:

显然,不需要交换。

调整结点array[2] = 34:

调整结果如图所示:

heapsort-5

调整结点array[1] = 12:

调整结果如图所示:

heapsort-6

调整结点array[0] = 94:

显然,不需要交换。

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

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

heapsort-7
此时,数组为:
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)。

  • 排序稳定性

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

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
八大排序算法~堆排序
八大排序算法~堆排序
22 0
排序算法
排序之PHP实现
649 0
排序算法(五):堆排序
从二叉搜索树和平衡二叉树的介绍中,可以发现二叉树这种结构具有一个很好的特性,当有序的二叉树构造完成之后,更改树中节点后,只需要 的时间复杂度即可将二叉树重新调整为有序状态。
924 0
排序算法
https://en.wikipedia.org/wiki/Sorting_algorithm http://www.cnblogs.com/eniac12/p/5329396.html   Theory Computational complexity theory Big O nota...
1018 0
堆排序算法---属于选择排序
1.堆   堆实际上是一棵完全二叉树,其任何一非叶节点满足性质:   Key[i]=key[2i+2]   即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。   堆分为大顶堆和小顶堆,满足Key[i]>=Key[2i+1]&&key>=key[2i+2]称为大顶堆,满足 Ke...
558 0
排序算法
简单排序 冒泡排序 public class BubbleSort { public static void main(String[] args) { ArrayBub a = new ArrayBub(20); a.insert(14); a.insert(144); a.insert(142); a.insert(56); a.insert(23);
959 0
+关注
85
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载