iOS/OC:快速排序的理解与实现(包含单路/双路)
快速排序(Quicksort)作为二十世纪最伟大的算法之一。快速排序的是一个时间复杂度平均为O(nlog2n)的不稳定算法。
快速排序的思想是从数组中任意选取一个元素v。然后将v放到它排序好后应该所在的正确位置，此时，元素v会将数组分割成两部分，
v左边一部分都比v要小，v右边的都比v要大，之后对分割出的两个子数组递归进行此分割操作，递归完成时，整个数组就排好序了。
比如，我们任意选择此数组第一个元素4。
1.png
然后将4放到他排序好后的应该所在的位置，并使4前面的都小于四，后边的都大于4。
2.png
之后对前后两部分继续进行此操作，即可完成整个的排序。
所以对于快速排序算法来说，最重要的就是，如何把一个选定的元素挪到正确的位置上，并且使前后两部分的都满足要求。这也是快速排序算法的核心。
在这个过程中，我们通常都选择第一个元素来作为我们分界的标识。我们给它起名叫v，同时用索引L记录他的位置。
3.png
之后我们在对v后面的元素一个一个的遍历过程中，我们将逐渐的整理出一部分是小于v的，一部分是大于v的。两部分的分界点我们用J来标识。
4.png
而当前访问的元素e我们用索引i来标识。
5.png
此时数组[L+1，J]这个区间都是小于v的，[J+1，i-1]这个区间都是大于v的,
之后我们看i这个位置的元素e，他怎么放到两个区间的某一个里去。
我们将e与v进行比较，如果比v大，说明它属于图中紫色的大于v的区间内，此时我们直接i自增1，直接指向下一个需要与v比较的元素，而e就已经是属于紫色的大于v的区间内了。
6.png
如果e比v小呢，我们就将元素e与J索引的下一个位置也就是J+1位置的元素交换。
7.png
8.png
此时e就属于蓝色小于v的区间内了，然后将J索引自增1，指向新的边界，i索引自增1，进行下一个元素的判断。
9.png
当所有的元素遍历完时，大于v和小于v的两部分就分完了。
10.png
最后，我们要将元素v挪到正确的位置上，只需将索引L位置的v与索引J位置的元素进行交换。
11.png
12.png
整个操作就完成了。之后对蓝色的小于v部分和紫色大于v部分的子数组重复以上操作，整个快速排序就完成了。
接下来，我们用代码实现一下快速排序。
NSMutableArray * array = [NSMutableArray arrayWithObjects:@8,@7,@6,@5,@4,@3,@2,@1, nil];
//调用排序
[self quickSortArray:array];
- (void)quickSortArray:(NSMutableArray *)array {
[self quickSort:array low:0 high:array.count - 1];
}
- (void)quickSort:(NSMutableArray *)array low:(int)low high:(int)high {
//递归退出条件判断
if (low>=high) {
return;
}
//对数组进行分割操作，返回分界处索引index
int index = [self quick:array low:low high:high];
//对从最低位索引low到分界处索引index前一位的元素递归进行分割操作
[self quickSort:array low:low high:index-1];
//对分界处索引index的后一位到末尾索引high进行递归分割操作
[self quickSort:array low:index + 1 high:high];
}
- (int)quick:(NSMutableArray *)array low:(int)low high:(int)high {
//分界处索引j的初始值为数组第一个元素的索引---low
int j = low;
//记录第一个元素的大小，方便与之后遍历的元素比较
NSInteger key = [array[low] integerValue];
for (int i = low + 1; i <= high; i++) {
//如果当前元素小于开始选取的第一个元素，则交换索引j+1和i的元素，同时j自增1.
if ([array[i] integerValue] < key) {
[array exchangeObjectAtIndex:j+1 withObjectAtIndex:i];
j++;
}
}
//全部遍历完成后，交换索引low与j的元素，将第一个元素放到正确的位置
[array exchangeObjectAtIndex:low withObjectAtIndex:j];
//返回分界点索引
return j;
}
双路快速排序
当数组中很多重复的元素时,上文的那种做法会将数组中与选定元素v相等的元素极不平衡的分配到前后两个部分中,这种情况我们之前快速排序算法就会退化成趋近于O(n2)级别的算法。
13.png
解决方式就是，之前我们是单一的从左侧开始遍历元素，分出两个部分，现在我们从数组左右两侧分别开始遍历。
我们将小于等于v和大于等于v的分别放在数组的两端，用i代表从左向右遍历的位置，J代表从右向左遍历的位置。
14.png
i向后遍历时，如果当前元素小于v则继续向后遍历，如果大于等于v则停止。
J向前遍历如果当前元素大于v则继续向前遍历，如果小于等于v则停止。
15.png
此时我们将索引i的元素e和索引J处的元素o交换下位置，就好了。
16.png
17.png
之后i继续向后遍历，J继续向前遍历。
18.png
直到i和J重合，就结束了。
数组中即使有大量相等的元素，也会平均分到两端。
代码实现一下双路快速排序。
NSMutableArray * array = [NSMutableArray arrayWithObjects:@8,@7,@6,@5,@4,@3,@2,@1, nil];
//调用排序
[self quickSortArray:array];
- (void)quickSortArray:(NSMutableArray *)array {
[self quickSort:array low:0 high:array.count - 1];
}
- (void)quickSort:(NSMutableArray *)array low:(int)low high: (int)high {
if (low>=high) {
return;
}
int index = [self quick:array low:low high:high];
[self quickSort:array low:low high:index-1];
[self quickSort:array low:index + 1 high:high];
}
- (int)quick:(NSMutableArray *)array low:(int)low high:(int)high {
int j = high;
int i = low + 1;
NSInteger key = [array[low] integerValue];
while (true) {
while (i <= high && [array[i] integerValue] < key) {
i++;
}
while (j>=low + 1 && [array[j] integerValue] > key) {
j--;
}
if(i > j) {
break;
}
[array exchangeObjectAtIndex:i withObjectAtIndex:j];
i++;
j--;
}
[array exchangeObjectAtIndex:low withObjectAtIndex:j];
return j;
}
如果觉得作者对哪里的理解有偏差或者其他的优化，希望不吝赐教，留言指正。谢谢支持~
