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

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

    禁止套娃?

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

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

挖坑法提供的解决思路

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

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

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

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

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

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

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

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

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

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

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

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

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

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

我们此时可以发现,原先的数组已经被分为了三部分:比 temp 小的数, temp ,比 temp 大(或等)的数组。

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

只需要再对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

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » 挖坑法实现快速排序(Java,Scala)

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址