DDR爱好者之家 Design By 杰米

快速排序算法
快速排序是一个递归的思想,首先选择一个数作为基数,把数组中小于它的数放在它的左边,把大于它的数放在它的右边,然后对左右两边的数递归进行排序。

算法的关键部分是实现数组的划分,即怎么把数组的元素划分成两部分,使得左边的数比基数小,右边的数比基数大。划分有许多不同的实现方法,这里主要使用单向扫描的方法,后面再稍微介绍双向扫描的方法。

选择最右边的数字作为基数。使用一个变量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 ;
}


执行输出如下:

[yu@argcandargv-com quicksort]$ go build quicksort.go 
[yu@argcandargv-com quicksort]$ ls

quicksort quicksort.go
[yu@argcandargv-com quicksort]$ time ./quicksort
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 

 

real  1m55.564s
user  1m55.215s
sys 0m0.052s

PS:其实应用中有一个优化,因为快速排序在数组本来有序的情况下复杂度会退化为O(n^2)。为了避免这点,在选取基数的时候可以随机地进行选择。具体做法是把最右边的数字跟一个随机的数字交换位置。另外还有一种三数取中的方法,即选择首尾跟中间某个数共三个数的中值作为基数。

DDR爱好者之家 Design By 杰米
广告合作:本站广告合作请联系QQ:858582 申请时备注:广告合作(否则不回)
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
DDR爱好者之家 Design By 杰米

P70系列延期,华为新旗舰将在下月发布

3月20日消息,近期博主@数码闲聊站 透露,原定三月份发布的华为新旗舰P70系列延期发布,预计4月份上市。

而博主@定焦数码 爆料,华为的P70系列在定位上已经超过了Mate60,成为了重要的旗舰系列之一。它肩负着重返影像领域顶尖的使命。那么这次P70会带来哪些令人惊艳的创新呢?

根据目前爆料的消息来看,华为P70系列将推出三个版本,其中P70和P70 Pro采用了三角形的摄像头模组设计,而P70 Art则采用了与上一代P60 Art相似的不规则形状设计。这样的外观是否好看见仁见智,但辨识度绝对拉满。