快捷導(dǎo)航

Java排序?qū)崿F(xiàn)的心得分享

更新時(shí)間：2014年01月10日 15:40:40 作者：

這篇文章主要介紹了Java排序?qū)崿F(xiàn)的心得，有需要的朋友可以參考一下

1.概述
排序和查找是程序設(shè)計(jì)里的兩類非?；镜膯?wèn)題，而現(xiàn)在也存在很多經(jīng)典的算法用于解決這兩類問(wèn)題，本文主要對(duì)java中排序算法實(shí)現(xiàn)進(jìn)行一個(gè)基本的探討，希望能夠起到拋磚引玉的作用。在此之前，首先問(wèn)各位幾個(gè)問(wèn)題：你能寫出一個(gè)正確的快排嗎？快排在什么情況下真正的快？你的快排足夠快嗎？還可以進(jìn)一步優(yōu)化嗎？帶著這些問(wèn)題，我們來(lái)看看jre7中快排是如何實(shí)現(xiàn)的吧。

Jre7中排序的實(shí)現(xiàn)類是DualPivotQuickSort.java，相比jre6有一些改變，主要發(fā)生在兩個(gè)地方，一個(gè)是insertion sort的實(shí)現(xiàn)上，另一個(gè)是QuickSort實(shí)現(xiàn)中pivot從一個(gè)變成了兩個(gè)。我們以int型的數(shù)組為例，該類中有個(gè)排序?qū)崿F(xiàn)的核心方法，該方法的原型為

復(fù)制代碼代碼如下:

void sort(int[] a, int left, int right, boolean leftmost)

參數(shù)a為需要排序的數(shù)組，left代表需要排序的數(shù)組區(qū)間中最左邊元素的索引，right代表區(qū)間中最右邊元素的索引，leftmost代表該區(qū)間是否是數(shù)組中最左邊的區(qū)間。舉個(gè)例子：
數(shù)組：[2, 4, 8, 5, 6, 3, 0, -3, 9]可以分成三個(gè)區(qū)間(2, 4, 8){5, 6}<3, 0, -3, 9>
對(duì)于()區(qū)間，left=0, right=2, leftmost=true
對(duì)于 {}區(qū)間, left=3, right=4, leftmost=false，同理可得<>區(qū)間的相應(yīng)參數(shù)

當(dāng)區(qū)間長(zhǎng)度小于47時(shí)，該方法會(huì)采用插入排序；否則采用快速排序。

2. 插入排序?qū)崿F(xiàn)
當(dāng)leftmost為true時(shí)，它會(huì)采用傳統(tǒng)的插入排序(traditional insertion sort)，代碼也較簡(jiǎn)單，其過(guò)程類似打牌時(shí)抓牌插牌：

復(fù)制代碼代碼如下:

for (int i = left, j = i; i < right; j = ++i) {
                    int ai = a[i + 1];
                    while (ai < a[j]) {
                        a[j + 1] = a[j];
                        if (j-- == left) {
                            break;
                        }
                    }
                    a[j + 1] = ai;
                } 

傳統(tǒng)插入排序代碼
當(dāng)leftmost為false時(shí)，它采用一種新型的插入排序（pair insertion sort），改進(jìn)之處在于每次遍歷前面已排好序的數(shù)組需要插入兩個(gè)元素，而傳統(tǒng)插入排序在遍歷過(guò)程中只需要為一個(gè)元素找到合適的位置插入。對(duì)于插入排序來(lái)講，其關(guān)鍵在于為待插入元素找到合適的插入位置，為了找到這個(gè)位置，需要遍歷之前已經(jīng)排好序的子數(shù)組，所以對(duì)于插入排序來(lái)講，整個(gè)排序過(guò)程中其遍歷的元素個(gè)數(shù)決定了它的性能。很顯然，每次遍歷插入兩個(gè)元素可以減少排序過(guò)程中遍歷的元素個(gè)數(shù)，其實(shí)現(xiàn)代碼如下：

復(fù)制代碼代碼如下:

for (int k = left; ++left <= right; k = ++left) {
                    int a1 = a[k], a2 = a[left];

                    if (a1 < a2) {
                        a2 = a1; a1 = a[left];
                    }
                    while (a1 < a[--k]) {
                        a[k + 2] = a[k];
                    }
                    a[++k + 1] = a1;

                    while (a2 < a[--k]) {
                        a[k + 1] = a[k];
                    }
                    a[k + 1] = a2;
                }

現(xiàn)在有個(gè)問(wèn)題：為什么最左邊的區(qū)間采用傳統(tǒng)插入排序，其他的采用成對(duì)插入排序呢？加入用上述成對(duì)插入排序代碼替換傳統(tǒng)插入排序代碼，會(huì)出現(xiàn)什么問(wèn)題呢？期待大家自己來(lái)回答。。。
3. 快速排序?qū)崿F(xiàn)
Jre7中對(duì)快速排序也做了改進(jìn)，傳統(tǒng)的快速排序是選取一個(gè)pivot（jre6種選取pivot的方法是挑選出數(shù)組最左邊，中間和最右邊位置的元素，將其中數(shù)值大小排在中間的元素作為pivot），然后分別從兩端向中間遍歷，把左邊遍歷過(guò)程中遇到的大于pivot的值和右邊遍歷中遇到的小于等于pivot的值進(jìn)行交換，當(dāng)遍歷相遇后，插入pivot的值；這樣就使得pivot左邊的值均小于或等于pivot，pivot右邊的值大于pivot；接下來(lái)再采用遞歸的方式對(duì)左邊和右邊分別進(jìn)行排序。

通過(guò)上述分析，我們可以看到：插入排序的每一步是使數(shù)組的一個(gè)子區(qū)間絕對(duì)有序，而每一次循環(huán)的本質(zhì)是使這個(gè)子區(qū)間不斷擴(kuò)大，所以我們可以看到其優(yōu)化的方向是使每次循環(huán)遍歷盡可能的使子區(qū)間擴(kuò)大的速度變快，所以上面把每次遍歷插入一個(gè)元素優(yōu)化成每次插入兩個(gè)元素。當(dāng)然肯定有人會(huì)問(wèn)，那為什么不把這個(gè)數(shù)字變得更大一點(diǎn)呢？比如每次遍歷插入5個(gè)，10個(gè)。。。很顯然，這樣是不行，它的一個(gè)極端情況就是每次遍歷插入n個(gè)（n為數(shù)組長(zhǎng)度）。。。至于為什么，大家自己回答吧。

對(duì)于快速排序來(lái)講，其每一次遞歸所做的是使需要排序的子區(qū)間變得更加有序，而不是絕對(duì)有序；所以對(duì)于快速排序來(lái)說(shuō)，其性能決定于每次遞歸操作使待排序子區(qū)間變得有序的程度，另一個(gè)決定因素當(dāng)然就是遞歸次數(shù)?？焖倥判蚴棺訁^(qū)間變得相對(duì)有序的關(guān)鍵是pivot，所以我們優(yōu)化的方向也應(yīng)該在于pivot，那就增加pivot的個(gè)數(shù)吧，而且我們可以發(fā)現(xiàn)，增加pivot的個(gè)數(shù)，對(duì)遞歸次數(shù)并不會(huì)有太大影響，有時(shí)甚至可以使遞歸次數(shù)減少。和insert sort類似的問(wèn)題就是，pivot增加為幾個(gè)呢？很顯然，pivot的值也不能太大；記住，任何優(yōu)化都是有代價(jià)的，而增加pivot的代價(jià)就隱藏在每次交換元素的位置過(guò)程中。關(guān)子貌似賣的有點(diǎn)大了。。。下面我們就來(lái)看看pivot的值為2時(shí)，快速排序是如何實(shí)現(xiàn)的吧。其實(shí)現(xiàn)過(guò)程其實(shí)也不難理解：
1. 首先選取兩個(gè)pivot，pivot的選取方式是將數(shù)組分成近視等長(zhǎng)的六段，而這六段其實(shí)是被5個(gè)元素分開的，將這5個(gè)元素從小到大排序，取出第2個(gè)和第4個(gè)，分別作為pivot1和pivot2；
2. Pivot選取完之后，分別從左右兩端向中間遍歷，左邊遍歷停止的條件是遇到一個(gè)大于等于pivot1的值，并把那個(gè)位置標(biāo)記為less；右邊遍歷的停止條件是遇到一個(gè)小于等于pivot2的值，并把那個(gè)位置標(biāo)記為great
3. 然后從less位置向后遍歷，遍歷的位置用k表示，會(huì)遇到以下幾種情況:
a. k位置的值比pivot1小，那就交換k位置和less位置的值，并是less的值加1；這樣就使得less位置左邊的值都小于pivot1，而less位置和k位置之間的值大于等于pivot1
b. k位置的值大于pivot2，那就從great位置向左遍歷，遍歷停止條件是遇到一個(gè)小于等于pivot2的值，假如這個(gè)值小于pivot1，就把這個(gè)值寫到less位置，把less位置的值寫道k位置，把k位置的值寫道great位置，最后less++，great--；加入這個(gè)值大于等于pivot1，就交換k位置和great位置，之后great—
4. 完成上述過(guò)程之后，帶排序的子區(qū)間就被分成了三段（<pivot1, pivot1<=&&<=pivot2,>pivot2），最后分別對(duì)這三段采用遞歸就行了。

復(fù)制代碼代碼如下:

/*
             * Partitioning:
             *
             *   left part           center part                   right part
             * +--------------------------------------------------------------+
             * |  < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2  |
             * +--------------------------------------------------------------+
             *               ^                          ^       ^
             *               |                          |       |
             *              less                        k     great
             *
             * Invariants:
             *
             *              all in (left, less)   < pivot1
             *    pivot1 <= all in [less, k)     <= pivot2
             *              all in (great, right) > pivot2
             *
             * Pointer k is the first index of ?-part.
             */