分享：快速排序实例

快速排序实例

代码如下：
import org.rut.util.algorithm.SortUtil;
public class QuickSort implements SortUtil.Sort{
    public void sort(int[] data) {
        quickSort(data,0,data.length-1);       
    }
    private void quickSort(int[] data,int i,int j){
        int pivotIndex=(i+j)/2;
        //swap
        SortUtil.swap(data,pivotIndex,j);
        int k=partition(data,i-1,j,data[j]);
        SortUtil.swap(data,k,j);
        if((k-i)>1) quickSort(data,i,k-1);
        if((j-k)>1) quickSort(data,k+1,j);
       
    }
   private int partition(int[] data, int l, int r,int pivot) {
        do{
           while(data[++l]<pivot);
           while((r!=0)&&data[--r]>pivot);
           SortUtil.swap(data,l,r);
        }
        while(l<r);
        SortUtil.swap(data,l,r);       
        return l;
    }
}


改进后的快速排序：



import org.rut.util.algorithm.SortUtil;
public class ImprovedQuickSort implements SortUtil.Sort {
    private static int MAX_STACK_SIZE=4096;
    private static int THRESHOLD=10;
    public void sort(int[] data) {
        int[] stack=new int[MAX_STACK_SIZE];
        int top=-1;
        int pivot;
        int pivotIndex,l,r;
        stack[++top]=0;
        stack[++top]=data.length-1;
        while(top>0){
            int j=stack[top--];
            int i=stack[top--];
            pivotIndex=(i+j)/2;
            pivot=data[pivotIndex];
            SortUtil.swap(data,pivotIndex,j);
            l=i-1;
            r=j;
            do{
                while(data[++l]<pivot);
                while((r!=0)&&(data[--r]>pivot));
                SortUtil.swap(data,l,r);
            }
            while(l<r);
            SortUtil.swap(data,l,r);
            SortUtil.swap(data,l,j);
            if((l-i)>THRESHOLD){
                stack[++top]=i;
                stack[++top]=l-1;
            }
            if((j-l)>THRESHOLD){
                stack[++top]=l+1;
                stack[++top]=j;
            }
           
        }
        insertSort(data);
    }
    private void insertSort(int[] data) {
        int temp;
        for(int i=1;i<data.length;i++){
            for(int j=i;(j>0)&&(data[j]<data[j-1]);j--){
                SortUtil.swap(data,j,j-1);
            }
        }      
    }
}

评论

2 楼 祖祖cool 2011-12-06  

的确，可以把效率提高很多

1 楼 ankyhe 2011-12-05  

一般建议，在quick sort之前随即排序一下，这样可以避免最差的时间复杂度。
另外，Python和Java 7的sort都改成timsort了，你可以看看，实现有些困难，不过效率更好。