快速排序 (不稳定)

• 时间复杂度：平均$O(nlogn)$，最坏$O(n^2)$
• 空间复杂度：$O(1)$

private void quick_sort(int[] nums, int l, int r) {
    if (l >= r) return;
    int i = l - 1, j = r + 1, mid = nums[l + r >> 1];
    while (i < j) {
        do ++i; while (nums[i] < mid);
        do --j; while (nums[j] > mid);
        if (i < j) {
            nums[i] = nums[i] ^ nums[j];
            nums[j] = nums[i] ^ nums[j];
            nums[i] = nums[i] ^ nums[j];
        }
    }
    quick_sort(nums, l, j);
    quick_sort(nums, j + 1, r);
}

归并排序 (稳定)

• 时间复杂度：平均$O(nlogn)$，最坏$O(nlogn)$
• 空间复杂度：$O(n)$

private void merge_sort(int[] nums, int l, int r) {
    if (l >= r) return;
    int mid = l + r >> 1;
    merge_sort(nums, l, mid);
    merge_sort(nums, mid + 1, r);
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
        if (nums[i] <= nums[j]) temp[k++] = nums[i++];
        else temp[k++] = nums[j++];
    }
    while (i <= mid) temp[k++] = nums[i++];
    while (j <= r) temp[k++] = nums[j++];

    for (int s = l, t = 0; s <= r; s++, t++) nums[s] = temp[t]; 
}

基数排序 (稳定)

• 时间复杂度：平均$O(d(n+k))$，最坏$O(d(n+k))$
• 空间复杂度：$O(n+k)$

int maxNum = Arrays.stream(nums).max().getAsInt();
for (int exp = 1; maxNum / exp > 0; exp *= 10) {
    // 按位排序
    sort(nums, exp);
}

private void sort(int[] nums, int exp) {
    int n = nums.length;
    int[] res = new int[n];
    int[] cnt = new int[10];

    for (int x : nums) cnt[(x / exp) % 10]++;
    for (int i = 1; i < 10; i++) cnt[i] += cnt[i - 1];
    for (int i = n - 1; i >= 0; i--) {
        int dig = (nums[i] / exp) % 10;
        res[cnt[dig] - 1] = nums[i];
        cnt[dig]--;
    }

    System.arraycopy(res, 0, nums, 0, n);
}