快速排序算法
快速排序是一个递归的思想，首先选择一个数作为基数，把数组中小于它的数放在它的左边，把大于它的数放在它的右边，然后对左右两边的数递归进行排序。
算法的关键部分是实现数组的划分，即怎么把数组的元素划分成两部分，使得左边的数比基数小，右边的数比基数大。划分有许多不同的实现方法，这里主要使用单向扫描的方法，后面再稍微介绍双向扫描的方法。
选择最右边的数字作为基数。使用一个变量j记录当前左边数字（比基数小的数）的最右的下标值。然后使用变量i从左到右遍历数组，如果a[i]比基数小，说明a[i]属于左边的数，就把j自增，然后交换a[j]和当前的a[i]。因为自增前的j是左边数字最右的下标，自增后的a[j]肯定不属于左边了，把其跟a[i]交换后，新的a[j]是属于左边的，而且此时j也重新变为左边数字最右的下标了。
扫描结束后，把j自增（因为a[j]将会被交换到最右边，因此要选属于右边的数字）后与最右边的基数交换，此时的j即为划分的结果。
Golang版的实现例子：
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 ;
}
执行输出如下:
