算法篇:Java实现九种排序算法7:交换排序之快速排序

基本思想：选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。

java实现

public class Quick {
    public static  void quick(int[] a) {
        if(a.length>0) {
            quickSort(a,0,a.length-1);
        }

    }
    private static void quickSort(int[] a, int low, int high) {
        if(low<high) {
            //选择基准元素
             int middle = getMiddle(a,low,high);
             quickSort(a, 0, middle-1);
             quickSort(a, middle+1, high);
        }

    }
    private static int getMiddle(int[] a, int low, int high) {
        //假设第一个是基准元素
        int temp = a[low];
        while(low<high) {
            //找到比基准元素小的位置
            while(low<high&&a[high]>=temp) {
                high--;
            }
             a[low] = a[high];
             //当队首元素小于等于tmp时,向前挪动low指针
             while(low<high && a[low]<=temp){
                   low++;
             }
             a[high] = a[low];
        }
        a[low] = temp;
        return low;
    }
    public static void main(String[] args) {
        int[] a = {49,38,65,97,76,13,27,49,78,34,12,64,1};
        quick(a);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
    }

}

注：用随机化选择基准元素的方法可能把最坏时间复杂度到O(nlogn)