快排

快速排序

基本思想:
1、先从数列中取出一个数作为基数。
2、分区,将比此基数大的数放到它右边,小的数放到它左边。
3、再对左右两块区间进行第二步,直到各中间只有一个数。(分治策略)

    public void quick_sort1(int s[],int l,int r){
        if (l < r)  
        {  
            int i = AdjustArray(s, l, r);//对基数排序,返回排序后的基数位置
            quick_sort1(s, l, i - 1);    //划分基数两边区域继续排序,分治
            quick_sort1(s, i + 1, r);  
        } 
    }
    
    public int  AdjustArray(int a[],int i,int j){//取a[i]做为基数排序,返回排好序之后基数的位置
        int k=a[i];
        while(i<j){
            while(i<j){//右向左寻找比基数小的数,进行交换
                if(k<a[j]){
                    j--;
                }else{
                    a[i++]=a[j];
                    a[j]=k;
                    break;
                }
            }
            while(i<j){ //左向右寻找比基数大的数,进行交换
                if(k>a[i]){
                    i++;
                }else{
                    a[j--]=a[i];
                    a[i]=k;
                    break;
                }
            }
        }
        return i;       
    }

上述代码将基数排序和分治 分为两个函数,较为繁琐,简化后如下:

    public void quick_sort(int a[],int l,int r){
        if (l < r) {  
            int i=l,j=r,k=a[i];
            while(i<j){      //对区域内基数进行排序,选区域内第一个数为基数
                while(i<j){
                    if(k<a[j]){
                        j--;
                    }else{
                        a[i++]=a[j];
                        a[j]=k;
                        break;
                    }
                }
                while(i<j){
                    if(k>a[i]){
                        i++;
                    }else{
                        a[j--]=a[i];
                        a[i]=k;
                        break;
                    }
                }
            }
            quick_sort(a, l, i - 1);    //分治,对基数两边区域继续排序
            quick_sort(a, i + 1, r);  
        } 
    }



//上述代码对基数排序的部分,即指定区域内比基数小的放在左边,比基数大的放在右边,此部分较为繁琐,简化如下:
        int i = l, j = r, x = s[l]; 
        while (i < j)  {  
            while(i < j && s[j] >= x) // 从右向左找第一个小于x的数  
                j--;    
            if(i < j)   
                s[i++] = s[j];  
              
            while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数  
                i++;    
            if(i < j)   
                s[j--] = s[i];  
        }  
       s[i] = x;
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容