算法的關(guān)鍵部分是實(shí)現(xiàn)數(shù)組的劃分，即怎么把數(shù)組的元素劃分成兩部分，使得左邊的數(shù)比基數(shù)小，右邊的數(shù)比基數(shù)大。劃分有許多不同的實(shí)現(xiàn)方法，這里主要使用單向掃描的方法，后面再稍微介紹雙向掃描的方法。
選擇最右邊的數(shù)字作為基數(shù)。使用一個(gè)變量j記錄當(dāng)前左邊數(shù)字（比基數(shù)小的數(shù)）的最右的下標(biāo)值。然后使用變量i從左到右遍歷數(shù)組，如果a[i]比基數(shù)小，說明a[i]屬于左邊的數(shù)，就把j自增，然后交換a[j]和當(dāng)前的a[i]。因?yàn)樽栽銮暗膉是左邊數(shù)字最右的下標(biāo)，自增后的a[j]肯定不屬于左邊了，把其跟a[i]交換后，新的a[j]是屬于左邊的，而且此時(shí)j也重新變?yōu)樽筮厰?shù)字最右的下標(biāo)了。
掃描結(jié)束后，把j自增（因?yàn)閍[j]將會被交換到最右邊，因此要選屬于右邊的數(shù)字）后與最右邊的基數(shù)交換，此時(shí)的j即為劃分的結(jié)果。
package main
import "fmt"
type ElemType int;
func main() {
data := make([]ElemType, 600000) // ALL ZERO
var i int = 0;
var dlen int = len(data);
for i = 0 ; i dlen ; i++{
data[i] = (ElemType)(dlen - i -1);
}
fmt.Println("Start ...",len(data));
for i = 0 ; i 100 ; i++{
fmt.Printf("%d ", data[i]);
}
fmt.Println();
QuickSort(data,0,dlen-1);
fmt.Println("End ...");
for i = 0 ; i 100 ; i++{
fmt.Printf("%d ", data[i]);
}
fmt.Println();
}
func QuickSort(A []ElemType,low, high int){
if low high {
// Partition() is the operation of divide A[low ... high]
// one to two arrays which can be used as QuickSort Again
pivotpos := Partition(A,low,high);
QuickSort(A,low,pivotpos-1);
QuickSort(A,pivotpos+1,high);
}
}
func Partition(A []ElemType,low ,high int) int {
var pivot ElemType = A[low];
var tmp ElemType;
//Method I:
//for low high {
// for low high A[high] >= pivot { high-- ; }
// A[low] = A[high];
// for low high A[low] pivot { low++; }
// A[high] = A[low];
//}
//end of MI
//Method II:
for (low high) (A[high] > pivot) { high --; }
for (low high) (A[low] pivot) {low++; }
for low high {
// swap A[low] A[high]
tmp = A[low];
A[low] = A[high];
A[high] = tmp;
low ++;
high --;
}
//end of MII
A[low] = pivot ;
return low ;
}
real 1m55.564s
user 1m55.215s
sys 0m0.052s
PS：其實(shí)應(yīng)用中有一個(gè)優(yōu)化，因?yàn)榭焖倥判蛟跀?shù)組本來有序的情況下復(fù)雜度會退化為O(n^2)。為了避免這點(diǎn)，在選取基數(shù)的時(shí)候可以隨機(jī)地進(jìn)行選擇。具體做法是把最右邊的數(shù)字跟一個(gè)隨機(jī)的數(shù)字交換位置。另外還有一種三數(shù)取中的方法，即選擇首尾跟中間某個(gè)數(shù)共三個(gè)數(shù)的中值作為基數(shù)。
