第五讲 堆排序

算法原理：

1.将长度为n的待排序的数组进行堆有序化构造成一个大根堆(小根堆)
2.将根节点与尾节点交换并输出此时的尾节点
3.将剩余的n -1个节点重新进行堆有序化
4.重复步骤2，步骤3直至构造成一个有序序列

@[@(40),@(60),@(20),@(30),@(50),@(80),@(10),@(90),@(70),@(100)]

Snip20181209_9.png

首先要做的是将堆有序化，这里我们以大根堆为例，将有孩子节点的父节点标记为0，1，2，3，4，先从后往前对有孩子节点的父节点开始，将50和100互换，然后一次往前，将30和90互换，然后将20与80互换，将100与60互换，再将100与40互换，当40在节点1的位置时，要保证互换后也是大根堆，所以将40与90互换之后，再与70互换，最后得到的就是一个堆化后的二叉树。

堆有序化.png

接下来执行第2步，将100与50互换，再做一次堆有序化，

100与50互换后堆化.png

然后再将90与40互换，并且堆化，

90与40互换后堆化.png

重复上述的步骤，直到输出根节点。

20与10互换后.png

至此，一个无序化的数组就排序完成了，接下来我们是这用代码实现一下。

- (void)viewDidLoad {
    [super viewDidLoad];
    
    NSArray * array = @[@(40),@(60),@(20),@(30),@(50),@(80),@(10),@(90),@(70),@(100)];
    NSMutableArray * temp = [NSMutableArray arrayWithArray:array];
    // 构造一个大根堆
    // 有子节点的节点 n／2-1 = 4
    // 所以需要调整的父节点为 4，3，2，1，0
    NSInteger size = temp.count;
    for (NSInteger i = array.count/2 - 1; i >= 0; i--) {
        [self creatHeapWithArray:temp size:size parent:i];
    }
    while (size > 0) {
        [temp exchangeObjectAtIndex:size-1 withObjectAtIndex:0];
        size--;
        [self creatHeapWithArray:temp size:size parent:0];
    }
    NSLog(@"Heap Sort  --------> %@",temp);
}


- (void)creatHeapWithArray:(NSMutableArray *)array size:(NSInteger)size parent:(NSInteger)parent {
    NSInteger leftChildNode = 2*parent + 1;
    NSInteger rightChildNode = leftChildNode + 1;//2*index + 2;
    //  左右节点都有的情况
    while (rightChildNode < size) {
        // 如果父节点比两个子节点都大,直接返回
        if (array[parent] >= array[leftChildNode] && array[parent] >= array[rightChildNode]) {
            return;
        }
        
        // 两个子节点其中至少有一个比父节点大
        if (array[leftChildNode] > array[rightChildNode]) {
            // 左子节点和父节点的值交换
            [array exchangeObjectAtIndex:parent withObjectAtIndex:leftChildNode];
            parent = leftChildNode;
        }
        else{
            // 右子节点和父节点的值交换
            [array exchangeObjectAtIndex:parent withObjectAtIndex:rightChildNode];
            parent = rightChildNode;
        }
        
        leftChildNode = 2*parent + 1;
        rightChildNode = leftChildNode + 1;
    }
    
    // 只有左子节点的情况
    if (leftChildNode < size && array[leftChildNode] >= array[parent]) {
        [array exchangeObjectAtIndex:parent withObjectAtIndex:leftChildNode];
    }
}

输出的结果：

Heap Sort  --------> (
    10,
    20,
    30,
    40,
    50,
    60,
    70,
    80,
    90,
    100
)