棋牌類游戲算法–牌分類

毫無(wú)疑問(wèn)，Quicksort被認(rèn)為是本世紀(jì)最重要的算法之一，并且它是許多語(yǔ)言的事實(shí)上的系統(tǒng)排序，包括Java中的Arrays.sort 。

那么，quicksort有何新功能？

好吧，除了我剛剛（在Java 7發(fā)行了2年之久）之后才想到， Arrays.sort的Quicksort實(shí)現(xiàn)已被稱為Dual-Pivot QuickSort的變體替代。 出于這個(gè)原因，這個(gè)線程很棒，而且喬恩·本特利和約書(shū)亞·布洛赫真的很謙虛。

接下來(lái)我要做什么？

就像其他所有人一樣，我也想實(shí)現(xiàn)它并針對(duì)約1000萬(wàn)個(gè)整數(shù)（隨機(jī)和重復(fù)）進(jìn)行一些基準(zhǔn)測(cè)試。

奇怪的是，我發(fā)現(xiàn)以下結(jié)果：

隨機(jī)數(shù)據(jù)：

• 快速排序基本：1222毫秒
• 快速排序3種方式：1295毫秒（嚴(yán)重！）
• 雙軸快速排序：1066毫秒

重復(fù)數(shù)據(jù)：

• 快速排序基礎(chǔ)：378毫秒
• 快速排序3種方式：15毫秒
• 快速分類雙樞軸：6毫秒

愚蠢的問(wèn)題1：

恐怕在三向分區(qū)的實(shí)現(xiàn)中缺少一些東西。 在針對(duì)隨機(jī)輸入（1000萬(wàn)個(gè)）的數(shù)字進(jìn)行的多次運(yùn)行中，我可以看到單個(gè)樞軸始終表現(xiàn)更好（盡管對(duì)于1000萬(wàn)個(gè)數(shù)字，其差異小于100毫秒）。

我知道直到現(xiàn)在，將三路Quicksort設(shè)置為默認(rèn)Quicksort的全部目的是它不會(huì)在重復(fù)鍵上提供0（n ^2）性能-當(dāng)我對(duì)重復(fù)輸入運(yùn)行它時(shí)，這是非常明顯的。 但是，為了處理重復(fù)的數(shù)據(jù)，三路方式會(huì)付出一點(diǎn)代價(jià)嗎？ 還是我的實(shí)現(xiàn)不好？

愚蠢的問(wèn)題2

我的Dual Pivot實(shí)現(xiàn)（下面的鏈接）不能很好地處理重復(fù)項(xiàng)。 它需要永遠(yuǎn)的甜蜜（0（n ^2））才能執(zhí)行。 有避免這種情況的好方法嗎？ 談到Arrays.sort實(shí)現(xiàn)，我發(fā)現(xiàn)在完成實(shí)際排序之前，就消除了升序和重復(fù)項(xiàng)。 因此，作為一個(gè)骯臟的解決方法，如果樞軸相等，則我快進(jìn)lowerIndex，直到它與pivot2不同。 這是公平的實(shí)施嗎？

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

而已。 那就是我所做的一切？

我總是發(fā)現(xiàn)算法的跟蹤很有趣，但是由于Dual Pivot quicksort中的變量數(shù)量眾多，我的眼睛在調(diào)試時(shí)發(fā)現(xiàn)它不知所措。 因此，我還繼續(xù)創(chuàng)建了啟用跟蹤的實(shí)現(xiàn)（針對(duì)所有3種實(shí)現(xiàn)），以便可以看到變量指針當(dāng)前所在的位置。

這些啟用了跟蹤的類僅覆蓋指針在數(shù)組值下方的位置。 我希望您發(fā)現(xiàn)這些課程有用。

例如。 用于Dual Pivot迭代

整個(gè)項(xiàng)目（以及DSA的一些la腳實(shí)現(xiàn)）可在github 此處獲得 。 僅在這里可以找到 quicksort類。

這是我對(duì)SinglePivot（Hoare），3way（Sedgewick）和新Dual-Pivot（Yaroslavskiy）的實(shí)現(xiàn)

單樞軸

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;}}

3路

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=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);}}

雙樞軸

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);}}

參考： Resort.me博客上的快速排序–我們JCG合作伙伴 Arun Manivannan的3向和雙向旋轉(zhuǎn) 。

翻譯自: https://www.javacodegeeks.com/2013/06/quicksorting-3-way-and-dual-pivot.html

棋牌類游戲算法–牌分類

總結(jié)

以上是生活随笔為你收集整理的棋牌类游戏算法–牌分类_快速分类–三向和双枢轴的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。