如何选择合适的排序算法

1.线性排序的时间复杂度比较低，但是使用场景比较特殊，所以要选通用的排序算法时候不能选线性排序。

2.如果是小规模排序，可以采用O(n2) 的算法，用时间换取空间；如果是大规模的算法，通常采用O(nlogn)的算法高效，用空间换取时间。所以一般为了兼顾数据规模的排序，一般采用时间复杂度是o(nlogn)的排序算法进行排序。

3.O(nlogn)的排序算法通常是有快速排序、归并排序、以及堆排序。一般归并排序使用情况不多，即使是最坏情况下快排时间复杂度是o(n2),而归并只需o(nlogn)，但是快排的使用情况还是最多的。这是因为归并排序不是原地排序，空间复杂度是O（n），归并排序计算100M的数据，往往还需要100M的空间来供给排序算法使用，空间翻倍。在数据规模很大的时候，这个是很恐怖的。

优化快排

快排最坏情况是 O(n2) ，即在最坏的情况下，数据是有序的或接近有序，分区点设置在最后一个数据上，这样是最坏的。所以理想的分区点是分区点左右两边的数据量是差不多的。这样会平均点。
如何找到中间的分区点呢。

三数取中法

从区间的首、中、尾三个数中进行比较，取三个数的中间值作为分区点。
代码：

 /** 取首中尾的中间值，并将其移至数组的尾部. */
    private static void midThree(int[] a, int start, int end) {
    
        int mid = (start + end) / 2;
        int min = Math.min(Math.min(a[start], a[mid]), a[end]);
        int max = Math.max(Math.max(a[start], a[mid]), a[end]);
        if (a[start] != min && a[start] != max) {
    
            swap(a,start,end); //如果start 是中间值，移动到尾部
        }else if (a[mid] != min && a[mid] != max){
    
            swap(a,mid,end); //如果mid是中间值，移动到尾部
        }
    }
    private static void swap(int[] arr, int a, int b) {
    
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

完整代码：

    public static int quickPartition(int[] arr, int begin, int end){
    
        int   keyi = begin; // 设置数组最左边为分区点
        while (begin < end){
     // 左右指针便利
            while (arr[end] >= arr[keyi] && begin < end){
     --end;} //找出右指针比分区点小的数
            while (arr[begin] <= arr[keyi] && begin < end){
     ++begin;} //找出左指针比分区点大的数
            int tmp = arr[end]; //  交换数据
            arr[end] = arr[begin];
            arr[begin] = tmp;
        }
        int temp = arr[end];  //左右指针相遇，移动分区点到相遇点
        arr[end] = arr[keyi];
        arr[keyi] = temp;
        keyi = end; //找出最新的分区点
        return keyi;
    }
    public static void quickfindLarge1(int[] arr, int begin, int end){
    
        if (begin >= end){
    
            return;
        }
        //midThree(arr,begin,end);
        int q = quickPartition(arr,begin,end);
        quickfindLarge1(arr,begin,q-1);
        quickfindLarge1(arr,q+1,end);
    }

    public static void quickfindLarge2(int[] arr, int begin, int end){
    
        if (begin >= end){
    
            return;
        }
        midThree(arr,begin,end);
        int q = quickPartition(arr,begin,end);
        quickfindLarge2(arr,begin,q-1);
        quickfindLarge2(arr,q+1,end);
    }
    /** 取首中尾的中间值，并将其移至数组的尾部. */
    private static void midThree(int[] a, int start, int end) {
    
        int mid = (start + end) / 2;
        int min = Math.min(Math.min(a[start], a[mid]), a[end]);
        int max = Math.max(Math.max(a[start], a[mid]), a[end]);
        if (a[start] != min && a[start] != max) {
    
            swap(a,start,end); //如果start 是中间值，移动到尾部
        }else if (a[mid] != min && a[mid] != max){
    
            swap(a,mid,end); //如果mid是中间值，移动到尾部
        }
    }
    private static void swap(int[] arr, int a, int b) {
    
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

结果比较：

随机数法

取随机数作为分区点，不能保证每次分区点选的都是最好，但也不是最坏的。这里不写代码；

总结，通用排序实现技巧

1.数据量不大的时候，采取时间换空间策略，即冒泡、插入、选择
2.数据量大的时候，采用空间换时间，例如快排、基数等。
3.手动模拟栈（防止递归引起的堆栈溢出）
4.使用哨兵优化代码，每一次排序减少判断
5.Arrays.sort():
1.若数组元素个数总数小于47，使用插入排序
2.若数据元素个数总数在47~286之间，使用快速排序。应该是使用的优化版本的三值取中的优化版本。
3.若大于286的个数，使用归并排序。