转载

挖坑法实现快速排序(Java,Scala)

取出一个数作为基准。(下文将该基准命名为 temp )
所有小数在其前，所有大数在其后，因此 temp 左右两边共产生了两个子区间。
两个子区间内部未必是有序的。因此分别在每个区间内重复1，2操作，直到各个区间只有一个数。 ~~禁止套娃？~~

由于每个区间内的处理方法是重复的，因此我们可以用递归函数来实现它(递归函数占用栈空间)，也可以采取while循环来解决。

快速排序可以轻松应付 庞大且无序的数组 ，但是若用于高度有序（甚至完全升序，降序排列好的，元素内容完全重复的）的数组，表现反而会很糟糕。

挖坑法提供的解决思路

上段中提到的操作步骤2有很多种方法实现，思路大同小异。在这里使用挖坑法来实现。我们首先准备：

两个”指针”(虽然它们实际上只是数组下标号，但为了方便理解，下文仍统称为指针) low 和 high ，分别指向数组的首和尾，且 high 只向左移动， low 只向右移动。
默认将数组首元素保存到 temp 当中。

换个说法，在程序开始前，在arr[low]的位置挖了坑，该位置上的数被移到了temp中。

有一个大前提：在调用该函数时 low < high 必须成立，否则不再继续递归。因为 low == high 意味着这个数组只有1个元素，那就没有必须再进行排序了。

程序运行， low 指针不动，而 high 指针判断它所目前指向的值是否大于 temp 。满足条件则左移，否则 high 指针会停下来，将当前指向的值覆盖到 arr[low] 位置上。（演示图里第一次判断就中了奖 =D）

或者说， high 位置上的数被挖出来填到了 low 位置上的坑。

此刻， high 指针不动， low 指针判断它所目前指向的值是否小于 temp 。满足条件则右移，否则 low 指针会停下来，将当前指向的值覆盖到 arr[high] 位置上。(这一段叙述和上一段叙述互为反过程。)

或者说， low 位置上的数又被挖出来填了上一步 high 指针位置留下来的坑。

high 指针再次开始左移，直到发现大于等于 temp 的数，则将其挖出来填到 low 指针的地方并暂停，随后 low 指针又不断右移，直到发现小于 temp 的数，再将它挖出填到 high 指针处...... high 和 low 指针一直处于 交替相向移动 的状态。

如此下去，总有一刻 high 指针和 low 指针会指向 同一位置 。此刻无需再移动 high 和 low 指针，只需要把最初挖出来的 temp 值，放到这个坑内即可。

我们此时可以发现，原先的数组已经被分为了三部分：比 temp 小的数， temp ，比 temp 大（或等）的数组。

只需要再对Smaller和Greater区间进行递归操作，重复之前所述的步骤就可以了。

基于挖坑法的Java快速排序

static void quickSortJ(Integer[] arr, int start, int end) {
        if (start < end) {
            Integer low = start;
            Integer high = end;
            Integer temp = arr[low];

            while (low < high) {

                while (high > low && arr[high] >= temp) high--;
                if (high > low) arr[low] = arr[high];
                while (high > low && arr[low] < temp) low++;
                if (high > low) arr[high] = arr[low];
                
            }
            
            arr[high] = temp;
            quickSortJ(arr, start, low - 1);
            quickSortJ(arr, high + 1, end);
        }
    }
复制代码

我只要[Smaller[], Temp, Greater[]]！

我们在进行一轮排序后（左右指针法，挖坑法，etc.）必定能将数组分割成以下形式： [Smaller[], temp, Greater[]] 。那能不能用更简单偷懒的方法来得到Smaller区间和Greater区间呢？在Scala中，可以直接利用过滤器 filter 来过滤出比 temp 小(或大)的数。如：

arr.filter(x => x > temp) //filter处理之后得到的仍是Array[]，放心食用。

而后再对过滤出来的Smaller[],和Greater[]继续进行递归即可。用Java的流处理同样可以实现类似逻辑，但是比较麻烦。

用Scala实现快速排序

def quickSortScl(arr: Array[Int]): Array[Int] = {
    if (arr.length <= 1)
       arr
    else {
      //这里的temp没有选取首元素，而是取中间元素.
      val temp =arr(arr.length/2)
      //返回一个[SmallerThanTemp[],temp,GreaterThanTemp[]].
      Array.concat(
        quickSortScl(arr.filter(x => x<temp)),
        //如果有多个相等的元素，则该数组内的元素个数大于1.
        arr.filter(x => x==temp),
        quickSortScl(arr.filter(x => x>temp))
      )
    }
  }
复制代码

原文 https://juejin.im/post/5e67594f6fb9a07cc32154da

正文到此结束