文档章节

双基准快速排序

kxf327
 kxf327
发布于 2014/01/09 20:41
字数 1053
阅读 49
收藏 0

快速排序被公认为是本世纪最重要的算法之一,这已经不是什么新闻了。对很多语言来说是实际系统排序,包括在Java中的Arrays.sort

那么快速排序有什么新进展呢?

好吧,就像我刚才提到的那样(Java 7发布两年后)快速排序实现的Arrays.sort双基准(dual-pivot)排序的一种变体取代了。这篇文章不仅展示了为什么这个变化如此优秀,而且让我们看到Jon Bentley和Joshua Bloch的谦逊。

我当时做了什么?

与所有人一样,我想实现这个算法并且对一千万个数值排序(随机数据和重复数据)。奇怪的是,我得到了下面的结果:

随机数据:

  • 基本排序:1222ms。

  • 三路(Three-way)快速排序:1295ms(我是认真的!)。

  • 双基准快速排序:1066ms。

重复数据:

  • 基本排序:378ms。

  • 三路快速排序:15ms。

  • 双基准快速排序:6ms。

愚蠢的问题1

我担心自己在实现三路快速排序的时候遗漏了什么。在多次执行随机输入一千万个数值后,可以看到单点排序始终运行更良好。尽管在执行一千万个数值的时候差距小于100ms。

我现在明白了,用三路快速排序作为默认排序工具的目的。因为在重复数值时,它的时间复杂度没有0(n2)。当我在输入重复值数据时,结果非常明显。但是真的为了处理重复数据的缘故,三路快速排序会受到性能损失吗?或者是我实现方式有问题?

愚蠢的问题2

我的双基准快速排序在实现重复数据的时候并没有处理好,它执行时耗费了0(n2)的时间复杂度。有什么好的办法可以避免吗?实现数组排序时我发现,在实际排序前升序序列和重复就已经能得到很好地消除。所以,作为一种应急的办法,如果定位的数字与比较的数字相等,则增长lowerIndex 去比较下一位数直到与pivot2不相等为止。这种实现会没有问题吗?

else if (pivot1==pivot2){
       while (pivot1==pivot2 && lowIndex<highIndex){
           lowIndex++;
           pivot1=input[lowIndex];
       }
   }

这就是所有内容吗?我究竟做了哪些?

我一直觉得算法跟踪很有趣,但是双基准快速排序中出现的变量个数让我眼花缭乱。所以,接下来我在(三种)实现中都加入了调试信息,这样就可以看出实际运行中不同。

这些可跟踪的类只负责追踪数组下方的指针。希望你能发现这些类是很有用的。

你可以从哪里下载代码?

整个项目(连同一些蹩脚的DSA实现)的实现可以在GitHub上找到。快速排序类就可以在这里找到。

这是我的实现单基准(Hoare),三路快排(Sedgewick)和新双基准(Yaroslavskiy)。

单基准:

package basics.sorting.quick;
 
import static basics.sorting.utils.SortUtils.exchange;
import static basics.sorting.utils.SortUtils.less;
import basics.shuffle.KnuthShuffle;
 
public class QuickSortBasic {
 
  public void sort (int[] input){
 
      //KnuthShuffle.shuffle(input);
      sort (input, 0, input.length-1);
  }
 
  private void sort(int[] input, int lowIndex, int highIndex) {
 
      if (highIndex<=lowIndex){
          return;
      }
 
      int partIndex=partition (input, lowIndex, highIndex);
 
      sort (input, lowIndex, partIndex-1);
      sort (input, partIndex+1, highIndex);
  }
 
  private int partition(int[] input, int lowIndex, int highIndex) {
 
      int i=lowIndex;
      int pivotIndex=lowIndex;
      int j=highIndex+1;
 
      while (true){
 
          while (less(input[++i], input[pivotIndex])){
              if (i==highIndex) break;
          }
 
          while (less (input[pivotIndex], input[--j])){
              if (j==lowIndex) break;
          }
 
          if (i>=j) break;
 
          exchange(input, i, j);
 
      }
 
      exchange(input, pivotIndex, j);
 
      return j;
  }
 
}

三基准

package basics.sorting.quick;
 
import static basics.shuffle.KnuthShuffle.shuffle;
import static basics.sorting.utils.SortUtils.exchange;
import static basics.sorting.utils.SortUtils.less;
 
public class QuickSortDualPivot {
 
  public void sort (int[] input){
      //input=shuffle(input);
      sort (input, 0, input.length-1);
  }
 
  private void sort(int[] input, int lowIndex, int highIndex) {
 
      if (highIndex<=lowIndex) return;
 
      int pivot1=input[lowIndex];
      int pivot2=input[highIndex];
 
      if (pivot1>pivot2){
          exchange(input, lowIndex, highIndex);
          pivot1=input[lowIndex];
          pivot2=input[highIndex];
          //sort(input, lowIndex, highIndex);
      }
      else if (pivot1==pivot2){
          while (pivot1==pivot2 && lowIndex<highIndex){
              lowIndex++;
              pivot1=input[lowIndex];
          }
      }
 
      int i=lowIndex+1;
      int lt=lowIndex+1;
      int gt=highIndex-1;
 
      while (i<=gt){
 
          if (less(input[i], pivot1)){
              exchange(input, i++, lt++);
          }
          else if (less(pivot2, input[i])){
              exchange(input, i, gt--);
          }
          else{
              i++;
          }
 
      }
 
      exchange(input, lowIndex, --lt);
      exchange(input, highIndex, ++gt);
 
      sort(input, lowIndex, lt-1);
      sort (input, lt+1, gt-1);
      sort(input, gt+1, highIndex);
 
  }
 
}

本文转载自:http://www.importnew.com/8445.html

kxf327
粉丝 5
博文 5
码字总数 625
作品 0
海淀
高级程序员
私信 提问
看图轻松理解数据结构与算法系列(快速排序)

前言 推出一个新系列,《看图轻松理解数据结构和算法》,主要使用图片来描述常见的数据结构和算法,轻松阅读并理解掌握。本系列包括各种堆、各种队列、各种列表、各种树、各种图、各种排序等...

超人汪小建
2018/11/27
0
0
排序——快速排序法

一、快速排序法概念 快速排序(Quick Sort)法是对冒泡排序的一种改进,其基本思想是:通过一遍排序将需要排序的数据划分成两部分,使其中一部分数据比另一部分数据小,然后再分别对这两部分...

翼动动空
2016/06/06
1K
0
让你一看就懂的快速排序算法(Java)

快速排序 你也许会被快速排序的文章弄得迷迷糊糊,其实大体上去看,快速排序就一步:找个数做基准数,把小于它的数移到它左边,把大于它的数移到它右边。这句话是核心。然后我们只需要让基准...

巅峰小学生
2018/07/20
0
0
iOS 算法~快速排序实现

//联系人:石虎QQ:1224614774 昵称:嗡嘛呢叭咪哄 一、概念: 快速排序: 是高快省的排序算法,在快速排序算法中,使用了分治策略。首先把序列分成两个子序列,递归地对子序列进行排序,直到整个序...

石虎132
2017/12/23
0
0
快速排序——PowerShell版

继续读啊哈磊算法有感系列,继续升华。上一篇是冒泡排序,在结尾总结了一下冒泡排序的缺点——时间复杂度O(N*N)太大。这一篇来说一下快速排序,快速排序可以在多数情况下克服冒泡排序的缺点(...

天外归云
2015/10/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

cesium调用天地图服务

本文转载于:专业的前端网站➧cesium调用天地图服务 全球矢量地图服务 var viewer = new Cesium.Viewer("cesiumContainer", { animation: false, //是否显示动画控件 baseLayerPi...

前端老手
25分钟前
4
0
Docker常用命令

场景一:镜像下载、运行及删除 COMMAND DESC 查看 docker images 列出所有镜像(images) docker ps 列出正在运行的容器(containers) docker ps -a 列出所有的容器 docker pull centos 下载cen...

_Change_
25分钟前
5
0
Spark ML使用DataFrame进行K-Means

1.前言 前一篇文章使用了RDD的方式,进行了K-Means聚类. 从Spark 2.0开始,程序包中基于RDD的API spark.mllib已进入维护模式.现在,用于Spark的主要机器学习API是软件包中基于DataFrame的API...

一位不知名的帅气网友
28分钟前
4
0
当遇到美女面试官之如何理解Redis的Expire Key(过期键)

  在面试中遇到美女面试官时,我们以为面试会比较容易过,也能好好表现自己技术的时候了。然而却出现以下这一幕,当美女面试官听说你使用过Redis时,那么问题来了。 👩面试官:Q1,你知道...

ccww_
32分钟前
5
0
干货来袭!游戏背景音乐的角色创建和主界面

角色创建/选择 在一些大型的游戏中,例如多人在线的游戏玩家必须创建一个游戏的虚拟人物进行扮演游戏。初次玩这款游戏的人都会进行创建,选择职业起名字性别选择编辑人设样式等等的操作,通常...

奇亿音乐
36分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部