iOS/OC:快速排序的理解与实现(包含单路/双路)

快速排序(Quicksort)作为二十世纪最伟大的算法之一。快速排序的是一个时间复杂度平均为O(nlog₂n)的不稳定算法。

快速排序的思想是从数组中任意选取一个元素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(n²)级别的算法。

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;
}

如果觉得作者对哪里的理解有偏差或者其他的优化，希望不吝赐教，留言指正。谢谢支持~