快速排序：

基本思想：
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;