十大排序算法——快排

思想：

选定一个枢纽元素，对待排序序列进行分割，分割之后的序列一个部分小于枢纽元素，一个部分大于枢纽元素，再对这两个分割好的子序列进行上述的过程

Java

public class Quick {
    public static void main(String[] args) {
        int[] array = new int[]{2, 3, 5, 8, 9, 0, 7, 5, 1, 6, 8, 7};
        sort(array);
        System.out.println(Arrays.toString(array));
    }

    private static void sort(int[] array) {
        shuffle(array);
        sort(array, 0, array.length - 1);
    }
    private static void sort(int[] array, int lo, int hi) {
        if (hi<=lo) return;
        int j = partition(array, lo, hi);
        sort(array, lo, j - 1);
        sort(array, j+1, hi);
    }

    private static int partition(int[] array, int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        int v = array[lo];
        while (true) {
            while (array[++i] < v) if (i == hi) break;
            while (v < array[--j]) if (j == lo) break;
            if (i>=j) break;

            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
        int temp = array[lo];
        array[lo] = array[j];
        array[j] = temp;
        return j;
    }
    /**
     *打乱数组
     */
    private static void shuffle(int[] array) {
        Random random = new Random(System.currentTimeMillis());
        if (array == null) throw new NullPointerException("argument array is null");
        int n = array.length;
        for (int i = 0; i < n; i++) {
            int r = i + random.nextInt(n-i);     // between i and n-1
            int temp = array[i];
            array[i] = array[r];
            array[r] = temp;
        }
    }
}

C

void swap(int a,int b){int t;t =a ;a =b ;b =t ;} 
        int Partition(int [] arr,int low,int high) 
        { 
            int pivot=arr[low];//采用子序列的第一个元素作为枢纽元素 
            while (low < high) 
            { 
                //从后往前栽后半部分中寻找第一个小于枢纽元素的元素 
                while (low < high && arr[high] >= pivot) 
                { 
                    --high; 
                } 
                //将这个比枢纽元素小的元素交换到前半部分 
                swap(arr[low], arr[high]); 
                //从前往后在前半部分中寻找第一个大于枢纽元素的元素 
                while (low <high &&arr [low ]<=pivot ) 
                { 
                    ++low ; 
                } 
                swap (arr [low ],arr [high ]);//将这个枢纽元素大的元素交换到后半部分 
            } 
            return low ;//返回枢纽元素所在的位置 
        } 
        void QuickSort(int [] a,int low,int high) 
        { 
            if (low <high ) 
            { 
                int n=Partition (a ,low ,high ); 
                QuickSort (a ,low ,n ); 
                QuickSort (a ,n +1,high ); 
            } 
        } 

平均效率O（nlogn），适用于排序大列表。
此算法的总时间取决于枢纽值的位置；选择第一个元素作为枢纽，可能导致O（n²）的最糟用例效率。若数基本有序，效率反而最差。选项中间值作为枢纽，效率是O（nlogn）。
基于分治法。