快速排序QuickSort

通过递归算法对比基准值而进行快速的排序

快速排序利用分而治之的思想，它的最好和平均实际复杂度为O(nlogn)，但是，如果选取基准的规则正好与实际数值分布相反，例如我们选取第一个数为基准，而原始序列是倒序的，那么每一轮循环，快排都只能把基准放到最右侧，故快排的最差时间复杂度为O(n²)。快排算法本身没有用到额外的空间，可以说需要的空间为O(1)；对于递归实现，也可以说需要的空间是O(n)，因为在递归调用时有栈的开销，当然最坏情况是O(n)，平均情况是O(logn)。快速排序是不稳定的。

实现一

以左边第一个数为基准

public class QuickSort {
    public static void main(String[] args) {
		int[] arr={54,12,42,21,67,34,21};
        quickSort(arr,0,arr.length-1);
    }
    //这个方法就是取找基准数的
    private static void quickSort(int[] arr, int left, int right) {
         // 递归需要出口
        if(left > right){
                return;
        }
        int i = left;
        int j = right;
        int baseNum = arr[left];
        while( i != j){
             while(arr[j] >= baseNum && j > i ){
                j--;
             }
             while(arr[i] <= baseNum && i <j){
                i++;
             }
             int temp = arr[i];
             arr[i] = arr[j];
             arr[j] = temp;
        }
        // 相遇的基准数归位
        arr[left] = arr[j];
        arr[j] = baseNum;

        quickSort(arr,left,i-1);
        quickSort(arr,j+1,right );

    }
}

实现二

取中间一个数为基准分界值

public class quickSort {
    public static void main(String[] args) {
        int[] arr={54,12,42,21,67,34,21};
        System.out.println("排序前："+ Arrays.toString(arr));
        quickSort(arr,0,arr.length-1);
        System.out.println("排序后："+ Arrays.toString(arr));
    }

    public static void quickSort(int[] arr,int left,int right){
        int ltemp=left,rtemp=right;
        int temp,mid;
        mid=arr[(left+right)/2];                         //分界值
        while(ltemp<rtemp){
            while (arr[ltemp]<mid){
                ltemp++;
            }
            while (arr[rtemp]>mid){
                rtemp--;
            }
            if(ltemp<=rtemp){
                temp=arr[ltemp];
                arr[ltemp]=arr[rtemp];
                arr[rtemp]=temp;
                --rtemp;
                ++ltemp;
            }
        }
        if(ltemp==rtemp){
            ltemp++;
        }
        if(left<rtemp){
            quickSort(arr,left,ltemp-1);               //递归调用
        }
        if(ltemp<right){
            quickSort(arr,rtemp+1,right);               //递归调用
        }
    }
}