Fork me on GitHub

堆排序(oc代码实现)

概念

堆是一棵顺序存储的完全二叉树,分为大根堆和小根堆

分类

  • 小根堆

    每个结点的关键字都不大于其孩子结点的关键字。

  • 大根堆

    每个结点的关键字都不小于其孩子结点的关键字

举例

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

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

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

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

318837-20160422104522335-1248911478.png

如上图所示,序列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]。

OC代码实现

思路

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

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

其实思路很简单,最重要的是怎么将一个初始化的数组构建一个大根堆呢??

采用的方式是自下而上,从右到左自下而上,从右到左的思路,以3个为一个单元,进行构建。

这么说大家可能还会搞不懂,接下来让我们举例说明!

假设有一个无序数组[1, 3, 4, 5, 2, 6, 9, 7, 8, 0]
318837-20160422104522991-406805984.png

这其中有个很重要的操作就是递归操作,图中的(4)

具体代码

代码中我加了很多注释,相信大家能够看懂。:-D

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
//  ViewController.m
// Copyright © 2017年 FlyOceanFish. All rights reserved.
//

#import "ViewController.h"

@interface ViewController ()
{
NSMutableArray *array;
}
@end

@implementation ViewController

- (void)viewDidLoad {
[super viewDidLoad];
array = [@[@20,@1,@4,@3,@40,@22,@9,@35,@6,@11,@18,@0] mutableCopy];
for (NSInteger i=array.count/2; i>=0; i--) {
[self headpSort:array parent:i length:array.count];//初始化建立大根堆
}
for (NSInteger i=array.count-1; i>0; i--) {//循环交换将最大的R0放到最后边
NSInteger tem = [array[0] integerValue];
[array replaceObjectAtIndex:0 withObject:@([array[i] integerValue])];
[array replaceObjectAtIndex:i withObject:@(tem)];
[self headpSort:array parent:0 length:i];//交换完成后,树中最大的自然排到了最后边,故只要对剩余的i个数重新调整为大根堆
NSLog(@"排序后:%@",array);
}
}

/**
这种遍历比较是自下而上的进行比较方式(从树的下部往上比较,以三个数为一个部分(假设左右子节点都有))
*/
- (void)headpSort:(NSMutableArray *)array parent:(NSInteger)parent length:(NSInteger)length{
NSInteger parentValue = [array[parent] intValue];
NSInteger rightChild = 2*parent+2;
NSInteger maxChildIndex = -1;
NSInteger maxChild = -1;
if (rightChild<length) {//这里的操作是先比较左右子节点的大小,那其中最大的再去跟父节点比较
if (array[rightChild]<array[rightChild-1]) {
maxChild =[array[rightChild-1] intValue];
maxChildIndex = rightChild-1;
}else{
maxChild =[array[rightChild] intValue];
maxChildIndex = rightChild;
}
}else if (rightChild-1<length){
maxChild = [array[rightChild-1] intValue];
maxChildIndex = rightChild-1;
}
if (maxChild>0) {
if ([array[parent] intValue]<maxChild) {
[array replaceObjectAtIndex:parent withObject:@(maxChild)];
[array replaceObjectAtIndex:maxChildIndex withObject:@(parentValue)];
[self headpSort:array parent:maxChildIndex length:length];//如果子节点是其他子节点的父节点的话,有可能比其子节点小,故需要递归
}
}
}
@end

总结

看的过程可能很爽,一看就明白,也有可能云里雾里。实践出真知!所以建议大家用代码根据原理亲自去实现一遍,相信一切皆明了。

参考

堆排序

0%