Java 分治算法实战：快速与归并排序

• 时间复杂度：O(n)
• 空间复杂度：O(1)

排序数组（快速排序）

给一个数组进行排序，核心在于利用基准值（Key）将数组划分为小于 Key、等于 Key、大于 Key 三个模块。然后递归地对左右两个模块重复此过程。

为了避免在有序或近乎有序数组上退化为 O(n^2)，我们采用随机选取基准值的策略。随机下标范围是 [left, right]。

class Solution {
    public int[] sortArray(int[] nums) {
        qsort(nums, 0, nums.length - 1);
        return nums;
    }

    private void qsort(int[] nums, int l, int r) {
        if (l >= r) {
            return;
        }
        // 随机获取 key，下标范围 [l, r]
        int key = nums[new Random().nextInt(r - l + 1) + l];
        
        int left = l - 1;
        int right = r + 1;
        int i = l;
        
        while (i < right) {
            if (nums[i] < key) {
                swap(nums, ++left, i++);
            } else if (nums[i] == key) {
                i++;
            } else {
                swap(nums, --right, i);
            }
        }
        
        qsort(nums, l, left);
        qsort(nums, right, r);
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

数组中第 K 个最大元素

基于快速排序的思想，我们可以优化为快速选择算法。快排会将数组分为三个模块，我们只需判断第 K 大的元素落在哪个模块中，然后只对该模块继续递归，无需处理其他模块。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        return qsort(nums, 0, nums.length - 1, k);
    }

    private int qsort(int[] nums, int l, int r, int k) {
        if (l == r) {
            return nums[l];
        }
        int key = nums[new Random().nextInt(r - l + 1) + l];
        int left = l - 1;
        int right = r + 1;
        int i = l;
        
        while (i < right) {
            if (nums[i] < key) {
                swap(nums, ++left, i++);
            } else if (nums[i] == key) {
                i++;
            } else {
                swap(nums, --right, i);
            }
        }
        
        // 划分为 [l, left], [left+1, right-1], [right, r]
        int b = right - left - 1; // 等于 key 的数量
        int c = r - right + 1;    // 大于 key 的数量
        
        if (c >= k) {
            // 只在右边找
            return qsort(nums, right, r, k);
        } else if ((b + c) >= k) {
            return key;
        } else {
            // 在左边找，注意 k 需要减去已排除的元素数
            return qsort(nums, l, left, k - b - c);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

最小的 K 个数

返回数组中最小的 k 个数。这与上一题类似，使用快速选择算法配合随机基准值。不同之处在于，找到前 k 小元素后，它们的顺序可以是随机的，不需要完全有序。

class Solution {
    public int[] smallestK(int[] arr, int k) {
        qsort(arr, 0, arr.length - 1, k);
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = arr[i];
        }
        return ret;
    }

    private void qsort(int[] arr, int l, int r, int k) {
        if (l >= r) {
            return;
        }
        int key = arr[new Random().nextInt(r - l + 1) + l];
        int left = l - 1;
        int right = r + 1;
        int i = l;
        
        while (i < right) {
            if (arr[i] < key) {
                swap(arr, ++left, i++);
            } else if (arr[i] == key) {
                i++;
            } else {
                swap(arr, --right, i);
            }
        }
        
        // [l, left], [left+1, right-1], [right, r]
        int a = left - l + 1;
        int b = right - left - 1;
        
        if (a > k) {
            qsort(arr, l, left, k);
        } else if (a + b >= k) {
            return;
        } else {
            qsort(arr, right, r, k - a - b);
        }
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

• 时间复杂度：O(n)，随机取 key 使得渐进复杂度更优
• 空间复杂度：O(k)

排序数组（归并排序）

归并排序同样遵循分治思想。根据中间点将数组分为左右两部分，分别递归排序，最后合并两个有序子数组。

class Solution {
    int[] tem;

    public int[] sortArray(int[] nums) {
        tem = new int[nums.length];
        mergeSort(nums, 0, nums.length - 1);
        return nums;
    }

    private void mergeSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);

        // 合并两个有序数组
        int cur1 = left;
        int cur2 = mid + 1;
        int i = 0;
        
        while (cur1 <= mid && cur2 <= right) {
            tem[i++] = nums[cur1] >= nums[cur2] ? nums[cur2++] : nums[cur1++];
        }
        
        while (cur1 <= mid) {
            tem[i++] = nums[cur1++];
        }
        while (cur2 <= right) {
            tem[i++] = nums[cur2++];
        }
        
        for (int j = left; j <= right; j++) {
            nums[j] = tem[j - left];
        }
    }
}

交易逆序对的总数

相对顺序不变，找出满足 ai > aj 且 i < j 的逆序对总个数。这可以通过归并排序的过程来统计。

在合并两个有序数组时，如果左边的元素大于右边的元素，说明左边剩余的所有元素都与右边当前元素构成逆序对。

class Solution {
    int[] tem;

    public int reversePairs(int[] record) {
        tem = new int[record.length];
        return mergeSort(record, 0, record.length - 1);
    }

    private int mergeSort(int[] record, int left, int right) {
        if (left >= right) {
            return 0;
        }
        int mid = (left + right) / 2;
        int ret = mergeSort(record, left, mid) + mergeSort(record, mid + 1, right);

        int cur1 = left;
        int cur2 = mid + 1;
        int i = 0;
        
        while (cur1 <= mid && cur2 <= right) {
            if (record[cur1] <= record[cur2]) {
                tem[i++] = record[cur1++];
            } else {
                ret += mid - cur1 + 1;
                tem[i++] = record[cur2++];
            }
        }
        
        while (cur1 <= mid) {
            tem[i++] = record[cur1++];
        }
        while (cur2 <= right) {
            tem[i++] = record[cur2++];
        }
        
        for (int j = left; j <= right; j++) {
            record[j] = tem[j - left];
        }
        return ret;
    }
}

翻转对

找出前面一个元素大于后面元素 2 倍的总个数。思路与逆序对类似，但在条件判断上有所不同。由于涉及乘法可能溢出，建议改为除法比较 nums[cur1] / 2.0 <= nums[cur2]。

class Solution {
    int[] tem;

    public int reversePairs(int[] nums) {
        int n = nums.length;
        tem = new int[n];
        return mergeSort(nums, 0, n - 1);
    }

    private int mergeSort(int[] nums, int left, int right) {
        if (left >= right) {
            return 0;
        }
        int ret = 0;
        int mid = (left + right) / 2;
        ret += mergeSort(nums, left, mid);
        ret += mergeSort(nums, mid + 1, right);

        // 先计算翻转对的个数
        int cur1 = left;
        int cur2 = mid + 1;
        
        while (cur1 <= mid) {
            while (cur2 <= right && nums[cur1] / 2.0 <= nums[cur2]) {
                cur2++;
            }
            if (cur2 > right) {
                break;
            }
            ret += right - cur2 + 1;
            cur1++;
        }

        // 合并两个有序数组
        cur1 = left;
        cur2 = mid + 1;
        int i = left;
        
        while (cur1 <= mid && cur2 <= right) {
            tem[i++] = nums[cur1] >= nums[cur2] ? nums[cur1++] : nums[cur2++];
        }
        
        while (cur1 <= mid) {
            tem[i++] = nums[cur1++];
        }
        while (cur2 <= right) {
            tem[i++] = nums[cur2++];
        }
        
        for (int j = left; j <= right; j++) {
            nums[j] = tem[j];
        }
        return ret;
    }
}

计算右侧小于当前元素的个数

返回一个新数组，对应下标的值是后面元素比当前下标元素小的个数。难点在于排序过程中会打乱原始索引，因此需要额外维护一个索引数组 index 来记录每个元素原本的相对位置。

class Solution {
    int[] ret;
    int[] index;
    int[] temIndex;
    int[] temNums;

    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        ret = new int[n];
        index = new int[n];
        temIndex = new int[n];
        temNums = new int[n];
        
        // 初始化对应下标
        for (int i = 0; i < n; i++) {
            index[i] = i;
        }
        
        mergeSort(nums, 0, n - 1);
        
        List<Integer> l = new ArrayList<>();
        for (int x : ret) {
            l.add(x);
        }
        return l;
    }

    private void mergeSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        
        int cur1 = left;
        int cur2 = mid + 1;
        int i = 0;
        
        // 进行排序
        while (cur1 <= mid && cur2 <= right) {
            if (nums[cur1] <= nums[cur2]) {
                temNums[i] = nums[cur2];
                temIndex[i++] = index[cur2++];
            } else {
                // 更新结果，此时找到 cur1 对应的下标进行赋值
                ret[index[cur1]] += right - cur2 + 1;
                temNums[i] = nums[cur1];
                temIndex[i++] = index[cur1++];
            }
        }
        
        while (cur1 <= mid) {
            temNums[i] = nums[cur1];
            temIndex[i++] = index[cur1++];
        }
        while (cur2 <= right) {
            temNums[i] = nums[cur2];
            temIndex[i++] = index[cur2++];
        }
        
        // 合并
        for (int j = left; j <= right; j++) {
            nums[j] = temNums[j - left];
            index[j] = temIndex[j - left];
        }
    }
}