首页 > 代码库 > 快速排序—三路快排 vs 双基准
快速排序—三路快排 vs 双基准
快速排序被公认为是本世纪最重要的算法之一,这已经不是什么新闻了。对很多语言来说是实际系统排序,包括在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不相等为止。这种实现会没有问题吗?
1 2 3 4 5 6 | else if (pivot1==pivot2){ while (pivot1==pivot2 && lowIndex<highIndex){ lowIndex++; pivot1=input[lowIndex]; } } |
这就是所有内容吗?我究竟做了哪些?
我一直觉得算法跟踪很有趣,但是双基准快速排序中出现的变量个数让我眼花缭乱。所以,接下来我在(三种)实现中都加入了调试信息,这样就可以看出实际运行中不同。
这些可跟踪的类只负责追踪数组下方的指针。希望你能发现这些类是很有用的。
例如一个双基准迭代器:
你可以从哪里下载代码?
整个项目(连同一些蹩脚的DSA实现)的实现可以在GitHub上找到。快速排序类就可以在这里找到。
这是我的实现单基准(Hoare),三路快排(Sedgewick)和新双基准(Yaroslavskiy)。
单基准:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | 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; } } |
三基准
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | 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 QuickSort3Way { public void sort ( int [] input){ //input=shuffle(input); sort (input, 0 , input.length- 1 ); } public void sort( int [] input, int lowIndex, int highIndex) { if (highIndex<=lowIndex) return ; int lt=lowIndex; int gt=highIndex; int i=lowIndex+ 1 ; int pivotIndex=lowIndex; int pivotValue=http://www.mamicode.com/input[pivotIndex]; while (i<=gt){ if (less(input[i],pivotValue)){ exchange(input, i++, lt++); } else if (less (pivotValue, input[i])){ exchange(input, i, gt--); } else { i++; } } sort (input, lowIndex, lt- 1 ); sort (input, gt+ 1 , highIndex); } } |
双基准
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 | 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