iOS之【算法快排、堆排】

快排序

把数组第一个当作基数，从右开始执行一趟排序得到
1.如果当前被选中的值小于基数
从左向右填充
2.如果当前被选中的值等于基数
不移动
3.如果当前被选中的值大于基数
从最右往左填充

- (NSArray *)quickSort:(NSArray *)sort {
    
    if (![sort isKindOfClass:[NSArray class]]) {
        return @[];
    }
    if (sort.count < 2) {
        return sort;
    }
    
    NSMutableArray *mutSort = [[NSMutableArray alloc] initWithArray:sort];
    
    NSMutableArray *leftArray = [[NSMutableArray alloc] init];
    NSMutableArray *rightArray = [[NSMutableArray alloc] init];
    
    if (sort.count > 3) {//长度大于3的数组值得使用随机锚点
        int midIndex = arc4random()%mutSort.count;
        //将随机找到的元素与位置为0的元素交换
        [mutSort exchangeObjectAtIndex:0 withObjectAtIndex:midIndex];
    }
    
    //设定锚点为位置0的元素，在这用固定位置的锚也是可行的，但易被特殊数据针对
    int mid = [mutSort[0] intValue];
    for (int i=1; i<mutSort.count; i++) {
        if ([mutSort[i] intValue] < mid) {
            //当元素小于锚点值 就把它推入左边
            [leftArray addObject:mutSort[i]];
        } else {
            //大于或等于锚点值的元素推入右边
            [rightArray addObject:mutSort[i]];
        }
    }
    
    NSMutableArray *resultArray = [[NSMutableArray alloc] init];

    //递归左右段，最后将所有锚点拼起来
    [resultArray addObjectsFromArray: [self quickSort:leftArray]];
    [resultArray addObject:mutSort[0]];
    [resultArray addObjectsFromArray: [self quickSort:rightArray]];

    return resultArray;
    
}

堆排序

堆通常是一个可以被看做一棵树的数组对象。
堆的时间复杂度O(N*logN),额外空间复杂度O(1),是一个不稳定的排序
堆的数据结构
大根堆：每个结点的值都大于其左孩子和右孩子结点的值
小根堆：每个结点的值都小于其左孩子和右孩子结点的值

- (void)heapSort:(NSMutableArray *)list
{
    
    list = [[NSMutableArray alloc] initWithObjects:@"50",@"10",@"90",@"30",@"70",@"40",@"80",@"60",@"20", nil];
    NSInteger i ,size;
    size = list.count;
    //找出最大的元素放到堆顶
    for (i= list.count/2-1; i>=0; i--) {
        [self createBiggesHeap:list withSize:size beIndex:i];
    }
    
    while(size > 0){
        [list exchangeObjectAtIndex:size-1 withObjectAtIndex:0]; //将根(最大) 与数组最末交换
        size -- ;//树大小减小
        [self createBiggesHeap:list withSize:size beIndex:0];
    }
    NSLog(@"堆排序：%@",list);
}

- (void)createBiggesHeap:(NSMutableArray *)list withSize:(NSInteger) size beIndex:(NSInteger)element
{
    NSInteger lchild = element *2 + 1,rchild = lchild+1; //左右子树
    while (rchild < size) { //子树均在范围内
        if ([list[element] integerValue] >= [list[lchild] integerValue] && [list[element] integerValue] >= [list[rchild]integerValue]) return; //如果比左右子树都大，完成整理
        if ([list[lchild] integerValue] > [list[rchild] integerValue]) { //如果左边最大
            [list exchangeObjectAtIndex:element withObjectAtIndex:lchild]; //把左面的提到上面
            element = lchild; //循环时整理子树
        }else{//否则右面最大
            [list exchangeObjectAtIndex:element withObjectAtIndex:rchild];
            element = rchild;
        }
        
        lchild = element * 2 +1;
        rchild = lchild + 1; //重新计算子树位置
    }
    //只有左子树且子树大于自己
    if (lchild < size && [list[lchild] integerValue] > [list[element] integerValue]) {
        [list exchangeObjectAtIndex:lchild withObjectAtIndex:element];
    }
}