快速排序（Quick Sort）

1. 算法描述

快速排序的基本思想：通过一趟排序确定关键值(keyIndex一般选择序列第一个)的准确位置，既关键值左边的数都比关键值小,关键值右边的数都比关键值大.然后对两边分别进行快速排序。

• 确定起始位置、结束位置和关键值位置;
• 先从后往前遍历序列找到比关键值小的位置,并且和关键值位置交换；
• 从前往后遍历序列找到比关键值大的位置,并且和关键值位置交换；
• 一趟排序确定关键值位置,对两边进行分别快速排序(递归);

2. 过程演示

Quick Sort.gif

快速排序

原始数据

34 54  12  78 3  45  9  


l   低位
h  高位
k   关键值位置

34 54  12  78 3  45  9   (l = 0, h = 6, k = 0)

9 54  12  78 3  45  34   (l = 0, h = 6, k = 6)

9  34  12  78 3  45 54   (l = 1, h = 6, k = 1)

9  3  12  78  34  45 54   (l = 1, h = 4, k = 4)

9  3  12 34  78  45 54  (l = 3, h = 4, k = 3)

一趟快排得到结果: 9  3  12 34  78  45 54 

3. 代码实现

/*
 * 快速排序
 */
- (void)quickSort:(NSMutableArray *)sortArray
            start:(NSInteger)start
              end:(NSInteger)end {
    if (start >= end) {
        return;
    }
    
    NSInteger low = start;
    NSInteger high = end;
    NSInteger keyIndex = start;
    self.count1 ++;
    while (low < high) {
        while ([sortArray[high] integerValue]>= [sortArray[keyIndex] integerValue] && high > keyIndex) {
            high --;
            self.count2 ++;
        }
        
        if ([sortArray[high] integerValue] < [sortArray[keyIndex] integerValue]) {
            [sortArray exchangeObjectAtIndex:high withObjectAtIndex:keyIndex];
            keyIndex = high;
        }
        
        while ([sortArray[low] integerValue] <= [sortArray[keyIndex] integerValue] && low < keyIndex) {
            low ++;
            self.count2 ++;
        }
        
        if ([sortArray[low] integerValue] > [sortArray[keyIndex] integerValue]) {
            [sortArray exchangeObjectAtIndex:low withObjectAtIndex:keyIndex];
            keyIndex = low;
        }
    }
    
    if (low == high) {
        [self quickSort:sortArray start:start end:keyIndex -1];
        [self quickSort:sortArray start:keyIndex + 1 end:end];
    }
}

4. 验证

 NSArray *arr = [self pakageNumber:1000];    
 NSMutableArray *sortArray = [NSMutableArray arrayWithArray:arr];
 [self quickSort:sortArray start:0 end:sortArray.count -1];
count1  :688                        // 外层循环
count2 :10982                      // 内层循环

一万条数据所用时间
time:0.019154s;