快速排序

快速排序也是分治思想下的排序方法。時間復(fù)雜度O(n*log2n)，是不穩(wěn)定的。比如前兩個數(shù)字是一樣的，明顯就不穩(wěn)定了。

1.首先理解如何分為兩組：

假設(shè)有array[10]

a，選定一個用來比較的基數(shù)，就選第一個吧;（這里的算法就先不理了）

b.a中選定了一個基數(shù)，用另外一個空間去儲存，那么位置array[0]就空缺出來了，來選擇一個數(shù)字去填充它，如何選擇呢，從后邊開始與基數(shù)比，比他小的滿足條件

c.然后從后邊選出了一個數(shù)，把它放進array[0],那么現(xiàn)在后邊又空出了一個數(shù)可以填了

d.現(xiàn)在，從array[1]開始比較，比基數(shù)大的數(shù)字放到剛剛的數(shù)組尾部那個空缺的可填入的地方

代碼如下：

private static int adjustArray(int[] array , int start,int end){
        //記錄左邊的那個可比較的元素位置
        int i = start;
        //記錄右邊的那個可比較的元素位置
        int j = end;
        //記錄用來比較的基數(shù)
        int tem = array[start];
        
        //如果i<j，循環(huán)繼續(xù)
        while(i < j){
            //從右邊找滿足條件的數(shù)（小于基數(shù)）放進左邊可以填的那個地方，這里與下邊的那個while循環(huán)都沒有出現(xiàn)=號，但是并不會出現(xiàn)遺漏元素，因為與基數(shù)相等的元素待在原來的地方并不會影響排序的結(jié)果
            while(i < j && tem < array[j])
                j--;
            if(i < j){
                array[i] = array[j];
                //下次左邊比較的數(shù)字
                i++;
            }
            
            //從左邊找滿足條件的數(shù)（大于基數(shù)）放進右邊可以填的那個地方          
            while(i < j && tem > array[i])
                i++;
            if(i < j){
                array[j] = array[i];
                //下次右邊比較的數(shù)字
                j--;
            }
        }
        //跳出循環(huán)時，必然有i = j,這個位置就是基數(shù)的位置，然后就會發(fā)現(xiàn)基數(shù)左邊的全是小于基數(shù)的數(shù)字，基數(shù)右邊的全是大于基數(shù)的數(shù)字。
        array[i] = tem;
        //另外需要返回基準值放的位置
        return i;
    }

2.遞歸調(diào)用1的方法

    public static void quickSort(int[] array,int start,int end){
        if(start < end){
            int i = adjustArray(array, start, end);
            quickSort(array,start,i - 1);
            quickSort(array,i + 1,end);
        }
    }

完整代碼：

public class QuickSort {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int size = 200000;
        int[] array = new int[size];
        Random r = new Random();
        long start;
        
        for(int i = 0; i < array.length ;i ++){
            array[i] = r.nextInt(size);
        }
        
        start = System.currentTimeMillis();
        quickSort(array, 0, array.length - 1);
        System.out.println("quick:" + (System.currentTimeMillis() - start));
    

    }
    
    public static void quickSort(int[] array,int start,int end){
        if(start < end){
            int i = adjustArray(array, start, end);
            quickSort(array,start,i - 1);
            quickSort(array,i + 1,end);
        }
    }
    
    private static int adjustArray(int[] array , int start,int end){
        //use to record elements from left
        int i = start;
        //use to record elements from left
        int j = end;
        //save the elements that used to be compared(the first elements)
        int tem = array[start];
        
        while(i < j){
            while(i < j && tem < array[j])
                j--;
            if(i < j){
                array[i] = array[j];
                i++;
            }
            
            while(i < j && tem > array[i])
                i++;
            if(i < j){
                array[j] = array[i];
                j--;
            }
        }
        array[i] = tem;
        return i;
    }
    
    private static void print(int[] array){
        for(int i : array){
            System.out.print(i + " ");
        }
        System.out.println("");
    }

}