序言
由于快速排序有多个优化，所以我今天就就从最开始的快速排序到最终版本的三路快速排序分别给大家呈现出来，优化的过程也会逐步带领大家慢慢的分析，好了，废话不多说，我们从第一个版本的快速排序开始:
第一个版本的快速排序
讲快速排序之前，我还是老规矩先上一张图，不然我感觉自己描述不清楚（莫见怪_）
第一个版本快速排序.png
下面根据图片我们，再来总结一下它的概念和步骤：
1.从数列中挑出一个元素，称为"基准"（pivot），
2.重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3.递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。说完了概念可能你还是会很迷糊，别急，我再来上一张图：
第一个版本快排partition过程.png
大家不理解的肯定是这个partition过程，我们设定一个基准点，一般以数组的第一个元素为基准点，我们姑且称之为V，我们将数组后续的元素依次与这个基准点V进行比较，当我们发现当前考察的元素array[i] < V的时候，我们将数组交换一下位置，也就是将数组的j+1这个位置的元素与i这个位置的元素进行交换，这时候我们发现橙色部分的元素新增了一个元素，也就是小于V的部分的元素增加了一个元素，但是当我们发现array[i] > V的时候我们该怎么办呢？没错，我们压根就不用懂，只需要让i继续往后走即可，这是因为大于V的部分本身就是在V对应的索引后边的，当我们的数组元素全部比较完成后，我们发现，数组已经被分成了两个部分了，一半是小于V的 ，一半是大于V 的，至此我们的partition过程也就完成了，当然此时我们数组的首个元素还是存放的V这个基准点，我们只需要将V放到j对应的索引出即可（j是分界的索引位置），下面我们来看下代码：
#pragma mark - 第一个版本快速排序
#pragma mark -
- (void)quickSort1:(NSMutableArray *)array {
[self __quickSort1:array left:0 right:(int)array.count - 1];
}
- (void)__quickSort1:(NSMutableArray *)array left:(int)left right:(int)right {
//判断递归到底的情况
if (left >= right) {
return;
}
int p = [self patition1:array left:left right:right];
[self __quickSort1:array left:left right:p];
[self __quickSort1:array left:p +1 right:right];
}
/**
对数组[left...right]部分进行快速排序注意是前后都是闭区间
@param array 待排序数组
@param left 左区间
@param right 右区间
@return 找到的中间的位置使得左半部分小于标定点V 右半部分大于V
*/
- (int)patition1:(NSMutableArray *)array left:(int)left right:(int)right {
//标记变量 小于j的在左边 大于j的在右边 默认初始化为left
int j = left;
//初始化标定点为数组的左边第一个元素
NSNumber * V = array[left];
for (int i = left + 1; i <= right; i++) {
if (array[i] < V) {//只有当比较的当前元素小于标定点V时 交换位置，当array[i] > V时只需要让i++就可以了，这里i已经是++了，所以不用考虑 ，这样这个当前元素就是在V的右边部分
[array exchangeObjectAtIndex:i withObjectAtIndex:j + 1];
//索引j要++
j++;
}
}
//当走完上面的循环后，j就是那个使得标定点V左半部分小于V右半部分大于V的索引 此时将第一个元素也就是V与j所在的位置交换位置即可
[array exchangeObjectAtIndex:j withObjectAtIndex:left];
//返回索引J
return j;
}
我们看到，这里快速排序也是通过递归的方式来的，所以这里和我前面说的归并排序一样，存在一个优化点，那就是当元素范围比较小的时候，我们可以采用插入排序，所以在递归结束的条件就可以这么写：
//判断递归到底的情况
// if (left >= right) {
// return;
// }
//快速排序第一个优化
if (right - left <= 15) {
[self insertionSort3:array left:left right:right];
return;
}
下面就应该要测试一下了，我们通过三组测试用例来进行测试，分别是普通数组，近乎有序的数组、大量重复元素数组,这里我们用的是十万的数量级：
//生成普通的随机数组
NSMutableArray *normalArray = [self.testHelper generateRandomArray:100000 rangeLeft:1 rangeRight:10000];
//大量重复元素
NSMutableArray *repeatArray = [self.testHelper generateRandomArray:100000 rangeLeft:1 rangeRight:3];
//生成近乎有序的排序数组
NSMutableArray *nearArray = [self.testHelper generateNearlyOrderedArray:100000 swapTimes:10];
//快速排序第一个版本普通数组
NSMutableArray * quickSort1Normal = normalArray.mutableCopy;
//快速排序第一个版本近乎有序数组
NSMutableArray * quickSort1Near = nearArray.mutableCopy;
//快速排序第一个版本大量重复数组
NSMutableArray * quickSort1Repeat = repeatArray.mutableCopy;
NSLog(@"============近乎有序的归并排序耗时============");
[self.testHelper testSortWithExcuteBlock:^{
[self mergeSort:mergeSortNear];
}];
NSLog(@"============普通数组第一个版本快速排序耗时============");
[self.testHelper testSortWithExcuteBlock:^{
[self quickSort1:quickSort1Normal];
}];
NSLog(@"============近乎有序数组第一个版本快速排序耗时============");
[self.testHelper testSortWithExcuteBlock:^{
[self quickSort1:quickSort1Near];
}];
下面是测试结果
第一个版本测试用例对比.png
我们发现在对近乎有序的数组以及大量重复元素的数组进行排序时，效率相当的低，这是问什么呢？别急，我们一个一个来解决，
解决近乎有序数组的效率问题
我们先来解决第一个问题，那就是对于近乎有序的数组，采用我们第一个版本快速排序的时候效率很低问题，我们来分析一下原因，我们每次取出的基准点都是我们的第一个元素，当近乎有序的时候，也就是说，每一次右边的元素都是要比第一个元素要大的，下面可以用一张图来形容一下：
第一个版本快排退化为O(N^2).png
那我们怎么来解决这个问题呢？其实很简单，我们采用随机数的方式来解决就可以了，每次我们取的基准点不是第一个元素，而是随机在数组中去一个元素作为我们的基准点，这样就可以做到，每次都不是取到最小的那个元素了，优化代码如下：
//快速排序第二个优化 标定点取随机数
int randonNum = arc4random() % (right - left + 1) + left;
[array exchangeObjectAtIndex:left withObjectAtIndex:randonNum];
此时再来看一下我们的测试结果：
第一个版本快速排序优化近乎有序数组测试结果.png
解决大量重复元素数组的效率问题
下面，我们再来解决第二个问题，当我们发现有大量重复元素的时候，我们也发现效率很低，那我们再来分析一下我们在partition过程中的条件：
if (array[i] < V) {//只有当比较的当前元素小于标定点V时 交换位置，当array[i] > V时只需要让i++就可以了，这里i已经是++了，所以不用考虑 ，这样这个当前元素就是在V的右边部分
[array exchangeObjectAtIndex:i withObjectAtIndex:j + 1];
//索引j要++
j++;
}
我们在这里判断的是当小于V 的时候交换位置，所以我们就有大于等于V 的元素全部放到了右边，所以在递归的时候会造成递归树相当的不均衡，右边部分永远是大于左边的部分，聪明的你肯定知道这样效率是会大打折扣的，至此，我们的第二个版本的快速排序就该出生了。
第二个版本的快速排序
有了上面的分析，我们已经知道，正是由于等于V的情况没有分析，所以导致我们的第一个版本的快速排序就退化到了O (n^ 2)的时间复杂度，那么我们怎么来优化呢？这其实就是我们第二个版本的快速排序要来解决的问题，我们也称之为双路快速排序，先来看一张图:
第二个版本快排partition过程.png
既然我们的问题是等于V的部分过于集中到一边，那么我们想办法把等于V的部分分到两边不就行了吗，从图上看我们也知道了，通过均衡的将等于V的部分分别放置到左右两边，就可以达到均衡的目的，下面我们来看代码：
#pragma mark - 第二个版本快速排序
#pragma mark -
/**
第二个版本快速排序
@param array 待排序数组
*/
- (void)quickSort2:(NSMutableArray *)array {
[self __quickSort2:array left:0 right:(int)array.count - 1];
}
- (void)__quickSort2:(NSMutableArray *)array left:(int)left right:(int)right {
//判断递归到底的情况
// if (left >= right) {
// return;
// }
//快速排序第一个优化
if (right - left <= 15) {
[self insertionSort3:array left:left right:right];
return;
}
int p = [self patition2:array left:left right:right];
[self __quickSort2:array left:left right:p -1];
[self __quickSort2:array left:p +1 right:right];
}
/**
第二个版本的partition过程
@param array 原数组
@param left 左边界
@param right 右边界
@return 索引j使得左边界小于等于j对应的值右边界大于等于j对应的值
*/
- (int)patition2:(NSMutableArray *)array left:(int)left right:(int)right {
//i标识小于等于V的索引；j是表示大于等于V的索引
int i = left + 1,j = right ;
//快速排序第二个优化 标定点取随机数
int randonNum = arc4random() % (right - left + 1) + left;
[array exchangeObjectAtIndex:left withObjectAtIndex:randonNum];
//标定点
NSNumber *V = array[left];
//不停循环寻找到一个一个索引 让前半部分小于等于V后半部分大于等于J
while (1) {
//如果左半部分考察的元素现在是小于V的只需要让i继续往后走即可
while (i <= right && array[i] < V) {//注意i最多到right的位置
i++;
}
//当右半部分考察的元素是大于V的只需要让j递减即可
while (j >= left +1 && array[j] > V) {//注意j最多能到left + 1的位置
j--;
}
//当i已经大于J的时候证明所有已经元素考察完毕了
if (i > j) {
break;
}
//走到这里 证明所有元素尚未考察完毕 且左半部分有一个元素已经大于V了、右半部分也有一个元素小于V了 ，此时只需要交换一下两个位置的元素 继续循环即可
[array exchangeObjectAtIndex:i withObjectAtIndex:j];
i++;
j--;
}
//循环结束后 将标定点交换到应该存放的位置
[array exchangeObjectAtIndex:left withObjectAtIndex:j];
return j;
}
这里，我还是来讲解一下这部分代码，照顾下基础比较弱的朋友，我们这里有两个索引 i和 j,i初始化为l + 1的位置，j初始化为数组最后一个位置通过不断的比较array[i]与V,当发现比V小时继续往前走，当发现等于V或者是大于V就停下来，而j从右边开始一直往前走，通过比较array[j]和V，如果发现比V大，就继续往前走，直到等于V或者是小于V的时候，我们也停下来，这时候，i和j这个位置的元素只需要交换一下位置就可以让数组维持左边小于等于V，右边的大于等于V的性质，然后继续比较下面的元素。看完后，我们再来测试一下：
第一个版本和第二个版本快速排序对比.png
我们发现，就算是大量的重复元素，我们的第二个版本的快速排序也能保持不错的性能，怎么样，是不是很佩服前人的智慧，
第三个版本的快速排序
如果你以为这样就完了，那你就打错特错了，前人的智慧那么无穷，当然是不断在优化这些算法的，先说一下，我们的第三个版本的快速排序依然是为了解决大量重复元素数组的问题的，下面我们来看一张图：
第三个版本快速排序partition过程.png
我们可以看到，和第二个版本相比，我们多了一个部分，那就是 ==V的部分，第二个版本是将等于V的部分分摊到两边，而我们现在谈的三路快速排序则是干脆将等于V的单独拿出来放置到一个区域，下面我们来看下代码实现吧：
#pragma mark - 第三个版本快速排序
#pragma mark -
- (void)quickSort3:(NSMutableArray *)array {
[self __quickSort3:array left:0 right:(int)array.count -1];
}
- (void)__quickSort3:(NSMutableArray *)array left:(int)left right:(int)right{
//元素比较少时采用插入排序
if (right - left <= 15) {
[self insertionSort3:array left:left right:right];
return;
}
//lt是小于V的最后一个元素索引，gt是大于V的第一个索引也就是说lt和gt是分水岭
int lt = left,gt = right + 1,i = left + 1;
//快速排序第二个优化 标定点取随机数
int randonNum = arc4random() % (right - left + 1) + left;
[array exchangeObjectAtIndex:left withObjectAtIndex:randonNum];
//定义标定点
NSNumber *V = array[left];
//当i小于gt时 就一直循环，当i >= gt证明所有元素考察结束了
while (i < gt) {
if (array[i] < V) {//小于V时将考察的元素放到lt的下一个位置
[array exchangeObjectAtIndex:lt + 1 withObjectAtIndex:i];
//继续往后走
i++;
//维护lt索引
lt++;
}else if (array[i] > V){//当大于V时就要元素放置到大于V的部分
[array exchangeObjectAtIndex:gt - 1 withObjectAtIndex:i];
//维护gt索引
gt--;
}else {//这里就是等于V的部分 ，只需要让i继续往后走即可
i++;
}
}
//将基准点防止到它合适的位置
[array exchangeObjectAtIndex:left withObjectAtIndex:lt];
//继续将小于V的
[self __quickSort3:array left:left right:lt];
//继续大于V的部分
[self __quickSort3:array left:gt right:right];
}
代码都有详细的注释，我就不再详细介绍了，下面我们老规矩还是放上测试结果吧，测试用例的代码我就不放出来了，不然文章篇幅是在太长了，下面看下三个版本快速排序的对比：
多种排序耗时对比.png
这里大家可以观察到，我将归并排序和插入排序也测试了一番，当然你这里可以不用太关注，你可以观察到三路快速排序对于有大量重复元素的数组进行排序时异常的快，怎么样，是不是成就感爆棚。
网友评论