快速排序（Quicksort）是对冒泡排序的一种改进。
快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
先来感受一下快速排序动态过程
快速排序实现方案
设要排序的数组是mutableArray对象，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一次快速排序。
步骤讲解
1 ）.设置两个变量i，j ，排序开始时i = 0，就j = mutableArray.count - 1；
2 ）.设置数组的第一个值为比较基准数key，key = mutableArray.count[0]；
3 ）.因为设置key为数组的第一个值，所以先从数组最右边开始往前查找比key小的值。如果没有找到，j--继续往前搜索；如果找到则将mutableArray[i]和mutableArray[j]互换，并且停止往前搜索，进入第4步；
4 ）.从i位置开始往后搜索比可以大的值，如果没有找到，i++继续往后搜索；如果找到则将mutableArray[i]和mutableArray[j]互换，并且停止往后搜索；
5 ）.重复第3、4步，直到i == j（此时刚好执行完第三步或第四部），停止排序；
排序演示
假设mutableArray = [@(6),@(3),@(7),@(1),@(5),@(8)]
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 数据 | 4 | 3 | 7 | 1 | 5 | 8 |
第一步：i = 0; j = 5; key = 4;
第二步：要找比key小的指，从右往前找，j不断递减，直到找到第一个比key小的，然后将mutableArray[i]和mutableArray[j]互换
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 数据 | 1 | 3 | 7 | 4 | 5 | 8 |
i = 0; j = 3; key = 4;
第三步：要找比key大的指，从左往后找，i不断递增，直到找到第一个比key大的，然后将mutableArray[i]和mutableArray[j]互换
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 数据 | 1 | 3 | 4 | 7 | 5 | 8 |
i = 2; j = 3; key = 4;
接着j--，则i==j；这样就称为一次循环
然后将key左边，右边的值分别当做一个数组重复上面步骤
OC代码实现
- (void)viewDidLoad {
[super viewDidLoad];
NSMutableArray *arr = [[NSMutableArray alloc] initWithObjects:@(6), @(1),@(2),@(5),@(9),@(4),@(3),@(7),nil];
[self quickSortArray:arr withLeftIndex:0 andRightIndex:arr.count - 1];
NSLog(@"%@",arr);
}
- (void)quickSortArray:(NSMutableArray *)array withLeftIndex:(NSInteger)leftIndex andRightIndex:(NSInteger)rightIndex
{
if (leftIndex >= rightIndex) {//如果数组长度为0或1时返回
return ;
}
NSInteger i = leftIndex;
NSInteger j = rightIndex;
//记录比较基准数
NSInteger key = [array[i] integerValue];
while (i < j) {
/**** 首先从右边j开始查找比基准数小的值 ***/
while (i < j && [array[j] integerValue] >= key) {//如果比基准数大，继续查找
j--;
}
//如果比基准数小，则将查找到的小值调换到i的位置
array[i] = array[j];
/**** 当在右边查找到一个比基准数小的值时，就从i开始往后找比基准数大的值 ***/
while (i < j && [array[i] integerValue] <= key) {//如果比基准数小，继续查找
i++;
}
//如果比基准数大，则将查找到的大值调换到j的位置
array[j] = array[i];
}
//将基准数放到正确位置
array[i] = @(key);
/**** 递归排序 ***/
//排序基准数左边的
[self quickSortArray:array withLeftIndex:leftIndex andRightIndex:i - 1];
//排序基准数右边的
[self quickSortArray:array withLeftIndex:i + 1 andRightIndex:rightIndex];
}
