前言

平時開發(fā)中常見有需要排序的場景，例如淘寶客戶端中商品搜索結(jié)果頁，可以根據(jù)綜合數(shù)據(jù)、信用、價格進行排序，這里就涉及到大量的各種商品數(shù)據(jù)，甚至有可能產(chǎn)品經(jīng)理拿出七尺長的砍刀，要求你根據(jù)商品上架時間、價格、地區(qū)、銷量、折扣等等的數(shù)據(jù)進行排序，那你為了不被拿去祭天，隨即高舉算法的大旗，拼了。。。

原理

在需要排序的數(shù)組中選取一個數(shù)作為切點元素，從右往左查找直到找到比切點元素小的元素并記錄元素位置，排到切點元素左邊，從左往右查找直到找到比切點元素大的元素并記錄元素位置，排到切點元素右邊，循環(huán)從右往左、從左往右這個步驟，直到元素位置相同則結(jié)束一趟循環(huán)，此時將數(shù)組切分成了兩個新數(shù)組，再分別對兩個新數(shù)組執(zhí)行上面的循環(huán)步驟，直到數(shù)組不能再切分，完成排序。

適用

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

1. 排序數(shù)組數(shù)據(jù)量非常大；
2. 排序數(shù)組是無序的；
3. 排序的效率要求很高；

運用

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

NSLog(@"快速排序后的數(shù)組: %@", [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