一、序言

　　在使用partition-exchange排序算法時，如快速排序算法(即使選擇了一個好的關鍵元素pivot values)，我們往往面臨一個很尷尬的境地--當排序對象中有很多重復的元素，partition-exchange排序算法表現很不盡如人意。當所有元素都相等時，這就特別容易理解了。在每次遞歸中，左邊部分是空的(沒有元素比關鍵元素小)，而右邊部分只能一個一個遞減移動。結果導致耗費了二次方時間來排序相等元素。為了解決這個問題(有時叫做荷蘭國旗問題)，我們詳細介紹下解決這個問題的方法。

二、”荷蘭國旗難題“問題描述

　　”荷蘭國旗難題“是計算機科學中的一個程序難題，它是由Edsger Dijkstra提出的。荷蘭國旗是由紅、白、藍三色組成的。

　　現在有若干個紅、白、藍三種顏色的球隨機排列成一條直線。現在我們的任務是把這些球按照紅、白、藍排序。

三、問題分析

這個問題我們可以將這個問題視為一個數組排序問題，這個數組分為前部，中部和后部三個部分，每一個元素（紅白藍分別對應0、1、2）必屬于其中之一。由于紅、白、藍三色小球數量并不一定相同，所以這個三個區域不一定是等分的，也就是說如果我們將整個區域放在[0,1]的區域里，由于三色小球之間數量的比不同（此處假設1:2:2），可能前部為[0,0.2)，中部為[0.2,0.6)，后部為[0.6,1]。我們的思路如下：將前部和后部各排在數組的前邊和后邊，中部自然就排好了。具體的：設置兩個標志位begin和end分別指向這個數組的開始和末尾，然后用一個標志位current從頭開始進行遍歷：1）若遍歷到的位置為0，則說明它一定屬于前部，于是就和begin位置進行交換，然后current向前進，begin也向前進（表示前邊的已經都排好了）。2）若遍歷到的位置為1，則說明它一定屬于中部，根據總思路，中部的我們都不動，然后current向前進。3）若遍歷到的位置為2，則說明它一定屬于后部，于是就和end位置進行交換，由于交換完畢后current指向的可能是屬于前部的，若此時current前進則會導致該位置不能被交換到前部，所以此時current不前進。而同1），end向后退1。

四、實現代碼

　　1、偽代碼：

　　　　偽代碼使用A代表元素數組

PRocedure three-way-partition(A : array of value, mid : value):    i ← 0    j ← 0    n ← size of A - 1    while j ≤ n:        if A[j] < mid:            swap A[i] and A[j]            i ← i + 1            j ← j + 1        else if A[j] > mid:            swap A[j] and A[n]            n ← n - 1        else:            j ← j + 1

　　2、java代碼實現：

public void sort(List<Integer> list){        int size = list.size();        int topEnd = 0;        int bottomStart = size - 1;        int current = 0;        while(current <= bottomStart){            int currentVal = list.get(current);            if(currentVal < 1){                swap(list, current, topEnd);                topEnd++;                current++;            }else if(currentVal > 1){                swap(list, current, bottomStart);                bottomStart--;            }else{                current++;            }        }    }

五、參考文獻：

　　http://en.wikipedia.org/wiki/Dutch_national_flag_problem

　　http://en.wikipedia.org/wiki/Quicksort

　　算法習作--荷蘭國旗問題