堆排序
堆排序(Heap Sort)是一种树形选择排序，是对直接选择排序的有效改进。
堆的概念
堆是一棵顺序存储的完全二叉树。
其中每个结点的关键字都不大于其孩子结点的关键字，这样的堆称为小根堆。
其中每个结点的关键字都不小于其孩子结点的关键字，这样的堆称为大根堆。
举例来说，对于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]。
算法思想
- 根据初始数组去构造初始堆（构建一个完全二叉树，保证所有的父结点都比它的孩子结点数值大）。
每次交换第一个和最后一个元素，输出最后一个元素（最大值），然后把剩下元素重新调整为大根堆。
当输出完最后一个元素后，这个数组已经是按照从小到大的顺序排列了。
范例代码
/**
堆排序
@param array 需要排序的Array
*/
+ (void)heapSort:(NSMutableArray *)array
{
/**
设当前元素在数组中以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]。
*/
//最后一个元素的索引
NSInteger endIndex = array.count - 1;
//构建初始堆
array = [self heapCreate:array];
// 进行n-1次循环，完成排序
while (endIndex > 0) {
// NSLog(@"将list[0]:\%@与list[\(endIndex)]:\%@交换", ascendingArr[0], ascendingArr[endIndex]);
// 最后一个元素和第一元素进行交换
NSNumber *temp = array[0];
array[0] = array[endIndex];
array[endIndex] = temp;
//堆调整
array = [self heapAdjast:array withFatherIndex:0 withEndIndex:endIndex];
// 下一次循环
endIndex -= 1;
}
NSLog(@"堆排序结果：%@", array);
}
//循环建立初始堆
+ (NSMutableArray *)heapCreate:(NSMutableArray *)array
{
NSInteger i = array.count/2;
while (i >= 0) {
array = [self heapAdjast:array withFatherIndex:i withEndIndex:array.count];
i -= 1;
}
return array;
}
//排序
+ (NSMutableArray *)heapAdjast:(NSMutableArray *)items withFatherIndex:(NSInteger)fatherIndex withEndIndex:(NSInteger)endIndex
{
//开始元素
NSNumber *temp = items[fatherIndex];
//先获得左子索引
NSInteger childIndex = 2 * fatherIndex+1;
while (childIndex < endIndex) {
// 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
if (childIndex+1 < endIndex && [items[childIndex] floatValue] < [items[childIndex+1] floatValue]) {
childIndex++;
}
// 如果父结点的值已经大于孩子结点的值，则直接结束
if ([temp floatValue] >= [items[childIndex] floatValue]) {
break;
}
// 把孩子结点的值赋给父结点
items[fatherIndex] = items[childIndex];
fatherIndex = childIndex;
childIndex = 2 * fatherIndex +1;
}
items[fatherIndex] = temp;
return items;
}
算法分析
堆排序算法的性能
时间复杂度
堆的存储表示是顺序的。因为堆所对应的二叉树为完全二叉树，而完全二叉树通常采用顺序存储方式。
当想得到一个序列中第k个最小的元素之前的部分排序序列，最好采用堆排序。
因为堆排序的时间复杂度是O(N+k*log N)，若k≤N/log N，则可得到的时间复杂度为O(N)。
空间复杂度
我们在排序过程中，需要一个临时变量存储要插入的值，所以空间复杂度为 1 。
算法稳定性
堆排序是一种不稳定的排序方法。在堆的调整过程中，关键字进行比较和交换所走的是该结点到叶子结点的一条路径，因此对于相同的关键字就可能出现排在后面的关键字被交换到前面来的情况。
