思想：
快速排序的思想从划分，治理，组合来解释：
-
划分：将最后一个元素作为key值，将数组划分成左边的元素<= X, 右边的元素 > X; 完成划分之后，元素X已经找到合适的位置q，所以接下来是[p, q) 和 [q+1, r)两个部分进行排序。
划分形式 治理：将左右两边分别进行排序。
组合：因为直接在数组中排序，无需进行合并。
具体实现：
对[p, r)区间中的元素进行划分，假设i, j 分别指向第一个大于X和第一个还没有进行判断的元素。当A[j] <= X时， 将A[i] 与 A[j]互换， i, j 同时向右行进，i++, j++; 当A[j] > X时，j向右行进，j++; 直到j == r - 1, 也就是指向最后一个元素时， 将A[i] 与 A[r - 1]互换，能让X值放置到正确的位置上。
- (NSInteger)partition:(NSMutableArray *)A start:(NSInteger)p end:(NSInteger)r {
// 选最后一个元素作为key值
NSInteger x = [A[r - 1] integerValue];
NSInteger i = p;
for (NSInteger j = p; j < r - 1; j++) {
// 从左到右进行判断。
if ([A[j] integerValue] <= x) {
// 交换
[A exchangeObjectAtIndex:i withObjectAtIndex:j];
i++;
}
}
// 最后将A[i]与A[r - 1]互换，就是将key值放到正确的位置上。
[A exchangeObjectAtIndex:i withObjectAtIndex:r - 1];
return i;
}
一轮过后，作为Key的X就能交换到排序后的指定位置了，也就是i最后指向的位置。我们拿具体的例子来看一遍。假设需要对[12, 8, 23, 7, 5, 4, 10] 进行排序。
然后以 i 所在的位置为分界，将数组分成左右两部分，也就是两个数组，再执行上面的步骤，最终能将所有key的正确位置都找到，这时候，数组就已经是有序的了。使用递归的方法实现：
- (void)quickSort:(NSMutableArray *)A start:(NSInteger)p end:(NSInteger)r {
// 保证数组是有元素的
if (p < r) {
// 获得分界下标
NSInteger q = [self partition:A start:p end:r];
// 左右两部分的数组递归
[self quickSort:A start:p end:q];
[self quickSort:A start:q + 1 end:r];
}
}
性能分析：
快速排序的最坏情况是𝜭(n^2)，最好的情况能达到𝜭(nlogn)。其中每次划分的时间是𝜭(n)。
- 最坏情况：每次划分都是划分都有一个空数组。公式为：T(n) = T(0) + T(n - 1) + 𝜭(n) = 𝜭(n^2) 。可以这么理解，每次划分之后，数组长度就减一，所以运行时间为:
T(n) = C * (n + n - 1 + n - 2 + ... + 2 + 1) = C * (n + 1) * n / 2 = 𝜭(n^2) -
最好情况：就是平衡划分，将数组比较平均的分成两部分，公式为：T(n) = 2T(n/2) + 𝜭(n)
计算
优化 -- 消除尾递归
当需要排序的数组很大的时候，多次的调用递归，使递归栈有可能会发生溢出。而我们在查看快速排序的划分树时发现，每次递归右边的数组的key值是一直不变的，可以利用这个特性来优化一下算法。将原来的排序方法改成：
- (void)quickSort:(NSMutableArray *)A start:(NSInteger)p end:(NSInteger)r {
// 保证数组是有元素的
while (p < r) {
// 获得分界下标
NSInteger q = [self partition:A start:p end:r];
// 左右两部分的数组递归
[self quickSort:A start:p end:q];
// [self quickSort:A start:q + 1 end:r];
p = q + 1;
}
}
将原来判断数组有元素的 if 改成 while, 而且将右边的起始位置设为q + 1; 继续能进入while循环，调用原来左边调用的排序方法。在上面的例子，对数组[12, 8, 23, 7, 5, 4, 10]进行排序，发现左右部分都用递归，调用了sort方法一共15次，而将右递归消除之后，调用sort方法一共8次。
