排序算法 - 快速排序

前言

平时开发中常见有需要排序的场景，例如淘宝客户端中商品搜索结果页，可以根据综合数据、信用、价格进行排序，这里就涉及到大量的各种商品数据，甚至有可能产品经理拿出七尺长的砍刀，要求你根据商品上架时间、价格、地区、销量、折扣等等的数据进行排序，那你为了不被拿去祭天，随即高举算法的大旗，拼了。。。

原理

在需要排序的数组中选取一个数作为切点元素，从右往左查找直到找到比切点元素小的元素并记录元素位置，排到切点元素左边，从左往右查找直到找到比切点元素大的元素并记录元素位置，排到切点元素右边，循环从右往左、从左往右这个步骤，直到元素位置相同则结束一趟循环，此时将数组切分成了两个新数组，再分别对两个新数组执行上面的循环步骤，直到数组不能再切分，完成排序。

适用

适合使用快速排序算法一般有如下特征：

1. 排序数组数据量非常大；
2. 排序数组是无序的；
3. 排序的效率要求很高；

运用

NSMutableArray *array = [NSMutableArray arrayWithArray:@[@111, @23, @89, @31, @63, @35, @35, @57, @71, @99]];

NSLog(@"快速排序后的数组: %@", [self quickSortArray: array withLeftIndex:0 rightIndex:array.count-1]);

排序方法封装成方法：

- (NSMutableArray *)quickSortArray: (NSMutableArray *)array withLeftIndex: (NSInteger)left rightIndex: (NSInteger)right {

    if (left >= right) {
        return array;
    }

    NSInteger i = left, j = right;
    NSInteger key = [array[left] integerValue]; // 切分元素

    while (i < j) {
    
        while ([array[j] integerValue] >= key && i < j) {
        
            j--;
        }
    
        array[i] = array[j];
    
        while ([array[i] integerValue] <= key && i < j ) {
        
            i++;
        }
    
        array[j] = array[i];
    }

    array[i] = @(key);

    [self quickSortArray:array withLeftIndex:left rightIndex:j-1];
    [self quickSortArray:array withLeftIndex:i+1 rightIndex:right];

    return array;
}

引用

http://www.cnblogs.com/joey-hua/p/4983618.html
http://www.baike.com/wiki/快速排序
https://baike.baidu.com/item/快速排序算法/369842?fr=aladdin#3_6