快速排序算法
快速排序是一个递归的思想，首先选择一个数作为基数，把数组中小于它的数放在它的左边，把大于它的数放在它的右边，然后对左右两边的数递归进行排序。
算法的关键部分是实现数组的划分，即怎么把数组的元素划分成两部分，使得左边的数比基数小，右边的数比基数大。划分有许多不同的实现方法，这里主要使用单向扫描的方法，后面再稍微介绍双向扫描的方法。
选择最右边的数字作为基数。使用一个变量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 ;
}
执行输出如下:
|
1
2
|
[yu@argcandargv-com quicksort]$ go build quicksort.go
[yu@argcandargv-com quicksort]$ ls
|
|
1
|
quicksort quicksort.go
|
|
1
|
[yu@argcandargv-com quicksort]$ time ./quicksort
|
|
1
2
3
4
|
Start ... 600000
599999 599998 599997 599996 599995 599994 599993 599992 599991 599990 599989 599988 599987 599986 599985 599984 599983 599982 599981 599980 599979 599978 599977 599976 599975 599974 599973 599972 599971 599970 599969 599968 599967 599966 599965 599964 599963 599962 599961 599960 599959 599958 599957 599956 599955 599954 599953 599952 599951 599950 599949 599948 599947 599946 599945 599944 599943 599942 599941 599940 599939 599938 599937 599936 599935 599934 599933 599932 599931 599930 599929 599928 599927 599926 599925 599924 599923 599922 599921 599920 599919 599918 599917 599916 599915 599914 599913 599912 599911 599910 599909 599908 599907 599906 599905 599904 599903 599902 599901 599900
End ...
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
|
|
1
2
3
|
real 1m55.564s
user 1m55.215s
sys 0m0.052s
|
PS：其实应用中有一个优化，因为快速排序在数组本来有序的情况下复杂度会退化为O(n^2)。为了避免这点，在选取基数的时候可以随机地进行选择。具体做法是把最右边的数字跟一个随机的数字交换位置。另外还有一种三数取中的方法，即选择首尾跟中间某个数共三个数的中值作为基数。