算法的关键部分是实现数组的划分，即怎么把数组的元素划分成两部分，使得左边的数比基数小，右边的数比基数大。划分有许多不同的实现方法，这里主要使用单向扫描的方法，后面再稍微介绍双向扫描的方法。
选择最右边的数字作为基数。使用一个变量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)。为了避免这点，在选取基数的时候可以随机地进行选择。具体做法是把最右边的数字跟一个随机的数字交换位置。另外还有一种三数取中的方法，即选择首尾跟中间某个数共三个数的中值作为基数。
咨 询 客 服