算法的關鍵部分是實現數組的劃分，即怎么把數組的元素劃分成兩部分，使得左邊的數比基數小，右邊的數比基數大。劃分有許多不同的實現方法，這里主要使用單向掃描的方法，后面再稍微介紹雙向掃描的方法。
選擇最右邊的數字作為基數。使用一個變量j記錄當前左邊數字（比基數小的數）的最右的下標值。然后使用變量i從左到右遍歷數組，如果a[i]比基數小，說明a[i]屬于左邊的數，就把j自增，然后交換a[j]和當前的a[i]。因為自增前的j是左邊數字最右的下標，自增后的a[j]肯定不屬于左邊了，把其跟a[i]交換后，新的a[j]是屬于左邊的，而且此時j也重新變為左邊數字最右的下標了。
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：其實應用中有一個優化，因為快速排序在數組本來有序的情況下復雜度會退化為O(n^2)。為了避免這點，在選取基數的時候可以隨機地進行選擇。具體做法是把最右邊的數字跟一個隨機的數字交換位置。另外還有一種三數取中的方法，即選擇首尾跟中間某個數共三個數的中值作為基數。
