工程上对排序的改进

1、稳定性的考虑

给定一个事实，如Java 中的 Arrays.sort(arr)方法，底层实现中，如果数组 arr 是基础类型，就会使用快速排序；如果 arr 是非基础类型，就会使用归并排序，为什么？

答：因为系统知道基础类型对稳定性没有什么要求，所以会使用较快的快速排序；而如果 arr 是非基础类型，不知道你是否需要稳定性，但是系统要给你保证稳定性，所以会使用归并排序。

如果给定其他事实，分析排序方法，也往稳定性上靠。

2、充分利用 O ( N × l o g N ) O(N times logN) O(N×logN) 和 O ( N 2 ) O(N^2) O(N2) 排序各自的优势

举例说明：

public class Test {
    //经典快排
    public static void quickSort(int[] arr, int L, int R) {
        if (L == R) return ;
        
        int[] p = partition(arr, L, R);
        quickSort(arr, L, p[0] - 1);
        quickSort(arr, p[1] + 1, R);
    }
    
    public static int[] partition(int[] arr, int L, int R) {
        
    }
}

但是有些语言可能会进行如下更改：

public class Test {
    //插入排序 O(N^2)，但是常数项小
    //快速排序：O(NlogN), 但是常数项大
    //所以N很大的时候，使用快排，快排调度优势明显
    //N不大的时候，插入排序的时间可能会优于快速排序
    public static void quickSort(int[] arr, int L, int R) {
        if (L + 60 > R) { //不足60个数的时候直接插入排序
            执行插入排序 arr[L ... R]
            return ;
        }
        
        int[] p = partition(arr, L, R);
        quickSort(arr, L, p[0] - 1);
        quickSort(arr, p[1] + 1, R);
    }
    
    public static int[] partition(int[] arr, int L, int R) {
        
    }
}

总结来说，如果要讨论排序算法的改进，就考虑稳定性和各自不同时间复杂度的算法的优势。