算法分析[排序]

1. 快速排序

快排最优复杂度是 O(n*log(n))，但是要使用辅助栈，总共要排序n次，每次查找中间值复杂度是O(logn)

75 快速排序, 此题用快排会超时，经典3种颜色，需要特殊处理

// 快排
void quick_sort(int[]arr, int low, inthigh){
         if (low>=high) return;
         // for找出中间值，O(logn)
         int i = partition(arr, low, high);
         // f(n/2) - 分治左
         quick_sort(arr, low, i-1);
         // f(n/2) - 分治右
         quick_sort(arr, i+1, high);
}
private int partition(int[] nums, int lo, int hi) {
        // 每次交换后， 都还是以p为中心点
        int p=nums[lo];
        while(lo<hi) {
            while(lo<hi && p<=nums[hi]) hi--;
            nums[lo]=nums[hi];
            // lo++; // 这里会导致数组为2时错误交换
            while(lo<hi && p>=nums[lo]) lo++;
            nums[hi]=nums[lo];
        }
        nums[lo]=p;
        return lo;
    }
// 空间换时间
private static void sortA(int[] nums) {
        Map<Integer, Integer> cs = new HashMap<>();
        for (int i : nums) {
            cs.put(i, cs.getOrDefault(i, 0) + 1);
        }
        int p = 0;
        for (Map.Entry<Integer, Integer> entry : cs.entrySet()) {
            Integer k = entry.getKey();
            Integer v = entry.getValue();
            for (int i = 0; i < v; i++) {
                nums[p++] = k;
            }
        }
    }
// 三色排序的特色，只需要2个标识能代表三色
// 中等值排在最前方，最小值每次出现都和中等值交换位置
// 最大值每次出现，都和最后k位交换位置
    private void quickB(int []nums) {
        // j 代表 1 开始的位置
        // k 代表 2 开始的位置
        int j=0, k=nums.length;
        for(int i=0; i<k; i++) {
            if(nums[i]==0) {
                swap(nums, i, j++);
            } else if(nums[i] == 2) {
                swap(nums, i--, --k);
            }
        }
    }