快排思想
如下的三步用于描述快排的流程：
- 在数组中随机取一个值作为标兵
- 对标兵左、右的区间进行划分(将比标兵大的数放在标兵的右面，比标兵小的数放在标兵的左面，如果倒序就反过来)
- 重复如上两个过程，直到选取了所有的标兵并划分(此时每个标兵决定的区间中只有一个值，故有序)
- (void)quickSortArray:(NSMutableArray *)array leftIndex:(NSInteger)leftIndex rightIndex:(NSInteger)rightIndex {
if (leftIndex >= rightIndex) {
return;
}
NSInteger i = leftIndex;
NSInteger j = rightIndex;
NSInteger key = [array[i] integerValue];
while (i < j) {
while (i < j && [array[j] integerValue] >= key) {
j--;
}
array[i] = array[j];
while (i < j && [array[i] integerValue] <= key) {
i++;
}
array[j] = array[i];
}
array[i] = @(key);
[self quickSortArray:array leftIndex:leftIndex rightIndex:i - 1];
[self quickSortArray:array leftIndex:i + 1 rightIndex:rightIndex];
}
在最好的情况下，每次 partition 都会把数组一分为二，所以时间复杂度 T(n) = 2T(n/2) + O(n)
解为 T(n) = O(nlog(n))
在最坏的情况下，数组刚好和想要的结果顺序相同，每次 partition 到的都是当前无序区中最小(或最大)的记录，因此只得到一个比上一次划分少一个记录的子序列。T(n) = O(n) + T(n-1)
解为 T(n) = O(n²)
在平均的情况下，快排的时间复杂度是 O(nlog(n))
