乐趣区

关于java:快速排序为什么这么快

疾速排序

首先选一个基准 pivot,而后过一遍数组,

  • 把小于 pivot 的都挪到 pivot 的右边,
  • 把大于 pivot 的都挪到 pivot 的左边。

这样一来,这个 pivot 的地位就确定了,也就是排好了 1 个元素。

而后对 pivot 右边 ???? 的数排序,
对 pivot 左边 ???? 的数排序,
就实现了。

那怎么排右边和左边?

答:同样的办法。

所以快排也是用的 分治法 的思维。

「分」

抉择一个 pivot,就把问题分成了

  • pivot 右边
  • pivot 左边

这两个问题。

「治」

就是最开始形容的办法,直到每个区间内 没有元素或者只剩一个元素 就能够返回了。

「合」

放在一起天然就是。

然而如何抉择这个 pivot?

取两头的?

取第一个?

取最初一个?

举个例子:{5, 2, 1, 0, 3}.

比方选最初一个,就是 3.

而后咱们就须要把除了 3 之外的数分成「比 3 大」和「比 3 小」的两局部,这个过程叫做 partition(划分)

这里咱们依然应用「挡板法」的思维,不必真的弄两个数组来存这两局部,而是用两个挡板,把区间划分好了。

咱们用「两个指针」(就是挡板)把数组分成「三个区间」,那么

  • 右边的区间用来放小于 pivot 的元素;
  • 左边的区间用来放大于 pivot 的元素;
  • 两头是未排序区间。

那么初始化时,咱们要保障「未排序区间」可能蕴含除了 3 之外的所有元素,所以

  • 未排序区间 = [i, j]

这样右边和左边的区间就成了:

  • [0, i):放比 3 小的数;
  • (j, array.length -2]:放比 3 大的数

留神 ⚠️ i, j 是不蕴含在左右区间里的呢。

那咱们的目标是 check 未排序区间里的每一个数,而后把它归到正确的区间里,以此来放大未排序区间,直到没有未排序的元素。

从左到右来 check:

Step1.

5 > 3, 所以 5 要放在右区间里,所以 5 和 j 指向的 0 替换一下:

这样 5 就排好了,指针 j –,这样咱们的未排序区间就少了一个数;

Step2.

0 < 3,所以就应该在右边的区间,间接 i++;

Step3.

2 < 3,同理,i++;

Step4.

1 < 3,同理,i++;

所以当两个指针错位的时候,咱们完结循环。

然而还差了一步,3 并不在正确的地位上呀。所以还要把它插入到两个区间两头,也就是和指针 i 替换一下。

齐姐申明:这里并不激励大家把 pivot 放最右边。

根本所有的书上都是放左边,既然放左右都是一样的,咱们就依照大家默认的、达成共识的来,没必要去“别树一帜”。

就比方围棋的四个星位,然而考究棋道的就是先落本人这边的星位,而不是伸着胳膊去够对手那边的。

那当咱们把 pivot 换回到正确的地位上来之后,整个 partition 就完结了。

之后就用递归的写法,对左右两边排序就好了。

最初还有两个问题想和大家讨论一下:

  1. 回到咱们最后 抉择 pivot的问题,每次都取最初一个,这样做好不好?

答:并不好。

因为咱们是想把数组宰割的 更平均 平均的工夫复杂度更低;然而如果这是一个有序的数组,那么总是取最初一个是最不平均的取法。

所以应该 随机 取 pivot,这样就防止了因为数组自身的特点总是取到最值的状况。

  1. pivot 放在哪

随机选取之后,咱们还是要把这个 pivot 放到整个数组的最左边,这样咱们的未排序区间才是 间断的,否则每次走到 pivot 这里还要想着跳过它,心好累哦。

class Solution {public void quickSort(int[] array) {if (array == null || array.length <= 1) {return;}
    quickSort(array, 0, array.length - 1);
  }
  private void quickSort(int[] array, int left, int right) {
    // base case
    if (left >= right) {return;}

    // partition
    Random random = new Random(); // java.util 中的随机数生成器
    int pivotIndex = left + random.nextInt(right - left + 1);
    swap(array, pivotIndex, right);

    int i = left;
    int j = right-1;
    while (i <= j) {if (array[i] <= array[right]) {i++;} else {swap(array, i, j);
        j--;
      }
    }
    swap(array, i, right);

    //「分」quickSort(array, left, i-1);
    quickSort(array, i+1, right);
  }
  private void swap(int[] array, int x, int y) {int tmp = array[x];
    array[x] = array[y];
    array[y] = tmp;
  }
}

这里的时空复杂度和分的是否平均有很大关系,所以咱们分状况来说:

1. 均分

工夫复杂度

如果每次都能差不多平均分,那么

  • 每次循环的耗时次要就在这个 while 循环里,也就是 O(right – left);
  • 均分的话那就是 logn 层;
  • 所以总的工夫是 O(nlogn).

空间复杂度

  • 递归树的高度是 logn,
  • 每层的空间复杂度是 O(1),
  • 所以总共的空间复杂度是 O(logn).

2. 最不平均

如果每次都能取到最大 / 最小值,那么递归树就变成了这个样子:

工夫复杂度

如上图所示:O(n^2)

空间复杂度

这棵递归树的高度就变成了 O(n).

3. 总结

理论呢,大多数状况都会靠近于 平均 的状况,所以平均的状况是一个 average case.

为什么看起来最好的状况实际上是一个均匀的状况呢?

因为即便如果没有取到最两头的那个点,比方分成了 10% 和 90% 两边的数,那其实每层的工夫还是 O(n),只不过 层数变成了以 9 为底的 log,那总的工夫还是 O(nlogn).

所以快排的均匀工夫复杂度是 O(nlogn)。

稳定性

那你应该能看进去了,在 swap 的时候,曾经毁坏了元素之间的绝对程序,所以快排并不具备稳定性。

这也答复了咱们结尾提出的问题,就是

  • 为什么对于 primitive type 应用快排

    • 因为它速度最快;
  • 为什么对于 object 应用归并

    • 因为它具备稳定性且快。

以上就是快排的所有内容了,也是很常考的内容哦!那下一篇文章我会讲几道从快排引申进去的题目,猜猜是什么?????

如果你喜爱这篇文章,记得给我点赞留言哦~你们的反对和认可,就是我创作的最大能源,咱们下篇文章见!

我是小齐,纽约程序媛,终生学习者,每天晚上 9 点,云自习室里不见不散!

更多干货文章见我的 Github: https://github.com/xiaoqi6666…

退出移动版