快速排序

快速排序

快速排序也是分治思想下的排序方法。时间复杂度O(n*log2n)，是不稳定的。比如前两个数字是一样的，明显就不稳定了。

1.首先理解如何分为两组：

假设有array[10]

a，选定一个用来比较的基数，就选第一个吧;（这里的算法就先不理了）

b.a中选定了一个基数，用另外一个空间去储存，那么位置array[0]就空缺出来了，来选择一个数字去填充它，如何选择呢，从后边开始与基数比，比他小的满足条件

c.然后从后边选出了一个数，把它放进array[0],那么现在后边又空出了一个数可以填了

d.现在，从array[1]开始比较，比基数大的数字放到刚刚的数组尾部那个空缺的可填入的地方

代码如下：

private static int adjustArray(int[] array , int start,int end){
        //记录左边的那个可比较的元素位置
        int i = start;
        //记录右边的那个可比较的元素位置
        int j = end;
        //记录用来比较的基数
        int tem = array[start];
        
        //如果i<j，循环继续
        while(i < j){
            //从右边找满足条件的数（小于基数）放进左边可以填的那个地方，这里与下边的那个while循环都没有出现=号，但是并不会出现遗漏元素，因为与基数相等的元素待在原来的地方并不会影响排序的结果
            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--;
            }
        }
        //跳出循环时，必然有i = j,这个位置就是基数的位置，然后就会发现基数左边的全是小于基数的数字，基数右边的全是大于基数的数字。
        array[i] = tem;
        //另外需要返回基准值放的位置
        return i;
    }

2.递归调用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("");
    }

}