堆排序

堆排序实际上是对选择排序的一个优化，选择排序每次都要选出一个最大值，相当于从头遍历到尾去选择最大值，时间复杂度为O(n)，在加上外层遍历n-1次，所有时间复杂度为O(n^2)，而堆排序在选择最大值的时候有优势，所以堆排序是对选择排序的一个优化。

这里如果不了解怎样建堆，不了解什么是上滤或者下滤，是没办法完成堆排序的，关于堆，可以看我的这篇文章,先明白这些才能完成堆排序.

操作流程

1. 对数组元素进行原地建堆，然后执行后面的操作，直到堆的元素数量为1
2. 交换堆顶元素与尾元素，相当于最大值和最小值的交换
3. 然后将堆的数量减去一
4. 因为堆顶元素被交换之后不符合大顶堆或者小顶堆的要求，需要对0位置的元素进行一次 siftDown 下滤操作。、

时间复杂度分析

原地建堆需要遍历每一个元素，所以时间复杂度为 O(n),交换元素的位置为O(1),数量减去一为iO(1),siftDown 操作为logn，因为每找一个最大值就需要log，所以为nlog

所以总的复杂度为 O(n) + O(1) + O(1) + nlogn = nlogn

代码及注释

//
//  SCXHeapSoft.m
//  TestArithmetic
//
//  Created by 孙承秀 on 2020/7/11.
//  Copyright © 2020 孙承秀. All rights reserved.
//

#import "SCXHeapSoft.h"
@interface SCXHeapSoft(){
    
    int _size;
}

@end
@implementation SCXHeapSoft
-(NSArray *)soft:(NSArray *)arr{
    // 建堆
    NSMutableArray *soft = arr.mutableCopy;
    _size = soft.count;
    // 自下而上下滤
    for (NSInteger i = (_size >> 1) - 1; i >= 0; i --) {
        [self siftDown:i arr:soft];
    }
    while (_size > 1) {
        // 将堆顶和堆尾元素互换
        // size --
        NSNumber *tmp = soft[--_size];
        soft[_size] = soft[0];
        soft[0] = tmp;
        
        // 将第0个元素下滤，保证除了最后一个元素之外，其余的元素组成一个堆
        [self siftDown:0 arr:soft];
    }
    return soft.copy;
}
// 下滤
- (void)siftDown:(NSInteger)index arr:(NSMutableArray *)_array{
    //第一个叶子节点的索引就是非叶子节点的数量，因为为完全二叉树，所以，要么没有左右子节点，要么只有左节点，不可能出现只有右子节点的情况
    // index < 第一个叶子节点的索引，这样就能保证他能和有子节点的进行交换
    // 必须保证index 位置为非叶子节点，因为这样可以找到左节点，或者左右节点，进行交换
    // 非叶子节点的数量为 二叉树节点数量除以二
    if (index >= _array.count) {
        return;
    }
    id obj = _array[index];
    // 第一个非叶子节点的索引
    NSInteger half = _size >> 1;
    while (index < half) {
        // 要么只有左子节点
        // 要么右左右子节点
        // 左子节点的索引为 2i +1 ,右子节点的索引为 2i+2
        NSInteger leftIndex = (index << 1) + 1;
        id leftObjf = _array[leftIndex];
        NSInteger rightIndex = leftIndex +1;
        
        
        // 选出最大值
        id maxObj = leftObjf;
        NSInteger maxIndex = leftIndex;
        if (rightIndex < _size ) {
            id rightObj = _array[rightIndex];
            if ([self compareA:rightObj valueB:leftObjf]) {
                // 右节点比左节点大
                maxObj = rightObj;
                maxIndex = rightIndex;
            }
        }
        
        // 选出左右最大的节点和index之后，和当前节点进行比较
        if ([self compareA:obj valueB:maxObj]) {
            // 如果当前节点比左右子节点中最大的那一个都打大，就退出不用交换了
            break;
        }
        // 如果当前节点比左右节点中的其中一个小，那么将当前位置，赋值为最大值,将最大值一次上滤，然后自己下沉，记住位置
        _array[index] = maxObj;
        index = maxIndex;
    }
    _array[index] = obj;
}
- (BOOL)compareA:(NSNumber *)valueA valueB:(NSNumber *)valueB{
    return valueA.intValue > valueB.intValue;
}
@end

demo