1 快速排序的基本代码实现

1.1 partition()

  • 对 arr[l, r] 部分进行操作：

    • 使用第一个元素作为切分元素，即v = arr[l]；
    • 使用j指向列表的切分点，初始化j=l代表当前没有元素；
    • 使用i指向当前遍历的元素；
    • 遍历结束后没交换l与j的值，并返回j，即p。

    • 返回p，使得 arr[l, p - 1] < arr[p]; arr[p + 1, r] > arr[p]

      1. private int partition(int[] arr, int l, int r) {
      2. int v = arr[l];
      3. int j = l;
      4. for (int i = l + 1; i <= r; i++) {
      5.    if (arr[i] < v) {
      6.        swap(arr, i, j + 1);
      7.        j++;
      8.    }
      9. }
      10. swap(arr, l, j);
      11. return j;
      12. }

      1.2 quickSort

      1. public class QuickSort implements Sort {
      3. @Override
      4. public void sort(int[] arr) {
      5.    quickSort(arr, 0, arr.length - 1);
      6. }
      8. private void quickSort(int[] arr, int l, int r) {
      9.    if (l >= r)
      10.        return;
      12.    int p = partition(arr, l, r);
      13.    quickSort(arr, l, p - 1);
      14.    quickSort(arr, p + 1, r);
      15. }
      16. }

      2 快速排序的优化

      2.1 随机优化

  • 当数组长度小于某一个值的时候，使用插入排序来优化

  • 当数组有序的时候，快排会退化成O(n)的复杂度：
    • 解决办法：随机选择切分元素，可用数学方法证明，此时，复杂度的期望是O(nlogn)的。
    • 在每次排序的时候随机选择在 [l, r]之间的元素，与l交换，再进行partition操作。

  • 优化后的代码：

    1. private int partition(int[] arr, int l, int r) {
    3.   // 随机选择切分元素
    4.   ArrayUtil.swap(arr, l, random.nextInt(r - l + 1) + l);
    6.   int v = arr[l];
    7.   int j = l;
    8.   for (int i = l + 1; i <= r; i++) {
    9.       if (arr[i] < v) {
    10.           ArrayUtil.swap(arr, i, j + 1);
    11.           j++;
    12.       }
    13.   }
    14.   ArrayUtil.swap(arr, l, j);
    15.   return j;
    16. }

    2.2 partition()优化

  • 当数组中有大量重复元素的时候，还是有问题，所以此时我们需要优化partition；

  • 从数组的两端往中间进行扫描，然后交换元素

    1. private int partition2(int[] arr, int l, int r) {
    2.   ArrayUtil.swap(arr, l, random.nextInt(r - l + 1) + l);
    3.   int v = arr[l];
    5.   int i = l + 1;
    6.   int j = r;
    8.   while (true) {
    9.       while (i <= r && arr[i] < v) i++;
    10.       while (j >= l + 1 && arr[j] > v) j--;
    12.       if (i > j)
    13.           break;
    15.       ArrayUtil.swap(arr, i, j);
    16.       i++;
    17.       j--;
    18.   }
    19.   ArrayUtil.swap(arr, l, j);
    20.   return j;
    21. }

    3 三路快排

  • 一种处理包含有大量重复元素的更优的解法