912. 排序数组

题目描述

输入整数数组 nums，其中可能有重复值。

把它按从小到大的顺序排好并返回。

不能调用任何内置的排序函数，时间复杂度要达到 O(n log(n))，额外空间越少越好。

示例 1

输入：nums = [5,2,3,1]
输出：[1,2,3,5]

示例 2

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

解释：重复的值也要保留。

数据范围

1 <= nums.length <= 5 * 10^4
-5 * 10^4 <= nums[i] <= 5 * 10^4

解题思路：堆排序

堆排序：把数组本身看成一棵完全二叉树，下标 i 的孩子是 2i+1 和 2i+2。第一步建最大堆：从最后一个非叶子结点向前，对每个结点做“下沉”（和较大的孩子交换，直到不小于孩子）。第二步反复把堆顶（当前最大值）与堆末尾交换，堆缩小一格，再让新堆顶下沉。数组末尾就从大到小依次排好。

为什么正确

nums[0:end] 是最大堆，nums[end:] 已排好且每个元素都不小于堆中任何元素。

复杂度分析

时间 O(n log n)，建堆 O(n)；空间 O(1)，原地排序。

易错点

下沉时要和“较大的孩子”交换，否则堆性质会被破坏。第二阶段下沉的范围是 [0, end)，不能碰已排好的尾部。快速排序如果不随机选枢轴，在有序或大量重复的数据上会退化到 O(n²)。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        def sift(i, size):
            while 2 * i + 1 < size:
                c = 2 * i + 1
                if c + 1 < size and nums[c + 1] > nums[c]:
                    c += 1
                if nums[i] >= nums[c]:
                    break
                nums[i], nums[c] = nums[c], nums[i]
                i = c
        for i in range(n // 2 - 1, -1, -1):
            sift(i, n)
        for end in range(n - 1, 0, -1):
            nums[0], nums[end] = nums[end], nums[0]
            sift(0, end)
        return nums

class Solution {
    void sift(int[] nums, int i, int size) {
        while (2 * i + 1 < size) {
            int c = 2 * i + 1;
            if (c + 1 < size && nums[c + 1] > nums[c]) {
                c++;
            }
            if (nums[i] >= nums[c]) {
                break;
            }
            int tmp = nums[i]; nums[i] = nums[c]; nums[c] = tmp;
            i = c;
        }
    }

    public int[] sortArray(int[] nums) {
        int n = nums.length;
        for (int i = n / 2 - 1; i >= 0; i--) {
            sift(nums, i, n);
        }
        for (int end = n - 1; end > 0; end--) {
            int tmp = nums[0]; nums[0] = nums[end]; nums[end] = tmp;
            sift(nums, 0, end);
        }
        return nums;
    }
}

class Solution {
public:
    void sift(vector<int>& nums, int i, int size) {
        while (2 * i + 1 < size) {
            int c = 2 * i + 1;
            if (c + 1 < size && nums[c + 1] > nums[c]) {
                c++;
            }
            if (nums[i] >= nums[c]) {
                break;
            }
            swap(nums[i], nums[c]);
            i = c;
        }
    }

    vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();
        for (int i = n / 2 - 1; i >= 0; i--) {
            sift(nums, i, n);
        }
        for (int end = n - 1; end > 0; end--) {
            swap(nums[0], nums[end]);
            sift(nums, 0, end);
        }
        return nums;
    }
};

func sift(nums []int, i, size int) {
	for 2*i+1 < size {
		c := 2*i + 1
		if c+1 < size && nums[c+1] > nums[c] {
			c++
		}
		if nums[i] >= nums[c] {
			break
		}
		nums[i], nums[c] = nums[c], nums[i]
		i = c
	}
}

func sortArray(nums []int) []int {
	n := len(nums)
	for i := n/2 - 1; i >= 0; i-- {
		sift(nums, i, n)
	}
	for end := n - 1; end > 0; end-- {
		nums[0], nums[end] = nums[end], nums[0]
		sift(nums, 0, end)
	}
	return nums
}

var sortArray = function(nums) {
    const n = nums.length;
    const sift = (i, size) => {
        while (2 * i + 1 < size) {
            let c = 2 * i + 1;
            if (c + 1 < size && nums[c + 1] > nums[c]) {
                c++;
            }
            if (nums[i] >= nums[c]) {
                break;
            }
            [nums[i], nums[c]] = [nums[c], nums[i]];
            i = c;
        }
    };
    for (let i = (n >> 1) - 1; i >= 0; i--) {
        sift(i, n);
    }
    for (let end = n - 1; end > 0; end--) {
        [nums[0], nums[end]] = [nums[end], nums[0]];
        sift(0, end);
    }
    return nums;
};

function sortArray(nums: number[]): number[] {
    const n = nums.length;
    const sift = (i: number, size: number): void => {
        while (2 * i + 1 < size) {
            let c = 2 * i + 1;
            if (c + 1 < size && nums[c + 1] > nums[c]) {
                c++;
            }
            if (nums[i] >= nums[c]) {
                break;
            }
            [nums[i], nums[c]] = [nums[c], nums[i]];
            i = c;
        }
    };
    for (let i = (n >> 1) - 1; i >= 0; i--) {
        sift(i, n);
    }
    for (let end = n - 1; end > 0; end--) {
        [nums[0], nums[end]] = [nums[end], nums[0]];
        sift(0, end);
    }
    return nums;
}

载入编辑器，自己跑一遍 →

其他解法

堆排序最坏 O(n log n) 且原地，但不稳定、访存跳跃；快速排序平均最快但只有期望保证；归并排序最坏 O(n log n) 且稳定，但要 O(n) 额外空间。

解法 2：随机快速排序（三路划分）时间期望 O(n log n)，最坏 O(n²)，空间期望 O(log n)（递归栈）

随机选一个基准值 pivot，用三个指针一遍扫描把区间分成“小于 pivot、等于 pivot、大于 pivot”三段（荷兰国旗划分），再对左右两段递归。随机选基准避免有序输入退化，三路划分避免大量重复元素时退化。

常数小、缓存友好，实际通常是最快的比较排序；但只有期望复杂度保证，并且不稳定。如果不做随机化或不处理重复元素，在本题的卡数据下会超时。

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def quick(lo, hi):
            if lo >= hi:
                return
            pivot = nums[random.randint(lo, hi)]
            lt, i, gt = lo, lo, hi
            while i <= gt:
                if nums[i] < pivot:
                    nums[lt], nums[i] = nums[i], nums[lt]
                    lt += 1
                    i += 1
                elif nums[i] > pivot:
                    nums[i], nums[gt] = nums[gt], nums[i]
                    gt -= 1
                else:
                    i += 1
            quick(lo, lt - 1)
            quick(gt + 1, hi)

        quick(0, len(nums) - 1)
        return nums

class Solution {
    Random rand = new Random();

    void quick(int[] nums, int lo, int hi) {
        if (lo >= hi) return;
        int pivot = nums[lo + rand.nextInt(hi - lo + 1)];
        int lt = lo, i = lo, gt = hi;
        while (i <= gt) {
            if (nums[i] < pivot) {
                int t = nums[lt]; nums[lt] = nums[i]; nums[i] = t;
                lt++;
                i++;
            } else if (nums[i] > pivot) {
                int t = nums[gt]; nums[gt] = nums[i]; nums[i] = t;
                gt--;
            } else {
                i++;
            }
        }
        quick(nums, lo, lt - 1);
        quick(nums, gt + 1, hi);
    }

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

class Solution {
public:
    void quick(vector<int>& nums, int lo, int hi) {
        if (lo >= hi) return;
        int pivot = nums[lo + rand() % (hi - lo + 1)];
        int lt = lo, i = lo, gt = hi;
        while (i <= gt) {
            if (nums[i] < pivot) swap(nums[lt++], nums[i++]);
            else if (nums[i] > pivot) swap(nums[i], nums[gt--]);
            else i++;
        }
        quick(nums, lo, lt - 1);
        quick(nums, gt + 1, hi);
    }

    vector<int> sortArray(vector<int>& nums) {
        quick(nums, 0, (int)nums.size() - 1);
        return nums;
    }
};

func sortArray(nums []int) []int {
	var quick func(lo, hi int)
	quick = func(lo, hi int) {
		if lo >= hi {
			return
		}
		pivot := nums[lo+rand.Intn(hi-lo+1)]
		lt, i, gt := lo, lo, hi
		for i <= gt {
			if nums[i] < pivot {
				nums[lt], nums[i] = nums[i], nums[lt]
				lt++
				i++
			} else if nums[i] > pivot {
				nums[i], nums[gt] = nums[gt], nums[i]
				gt--
			} else {
				i++
			}
		}
		quick(lo, lt-1)
		quick(gt+1, hi)
	}
	quick(0, len(nums)-1)
	return nums
}

var sortArray = function(nums) {
    const quick = (lo, hi) => {
        if (lo >= hi) return;
        const pivot = nums[lo + Math.floor(Math.random() * (hi - lo + 1))];
        let lt = lo, i = lo, gt = hi;
        while (i <= gt) {
            if (nums[i] < pivot) {
                [nums[lt], nums[i]] = [nums[i], nums[lt]];
                lt++;
                i++;
            } else if (nums[i] > pivot) {
                [nums[i], nums[gt]] = [nums[gt], nums[i]];
                gt--;
            } else {
                i++;
            }
        }
        quick(lo, lt - 1);
        quick(gt + 1, hi);
    };
    quick(0, nums.length - 1);
    return nums;
};

function sortArray(nums: number[]): number[] {
    const quick = (lo: number, hi: number): void => {
        if (lo >= hi) return;
        const pivot = nums[lo + Math.floor(Math.random() * (hi - lo + 1))];
        let lt = lo, i = lo, gt = hi;
        while (i <= gt) {
            if (nums[i] < pivot) {
                [nums[lt], nums[i]] = [nums[i], nums[lt]];
                lt++;
                i++;
            } else if (nums[i] > pivot) {
                [nums[i], nums[gt]] = [nums[gt], nums[i]];
                gt--;
            } else {
                i++;
            }
        }
        quick(lo, lt - 1);
        quick(gt + 1, hi);
    };
    quick(0, nums.length - 1);
    return nums;
}

解法 3：归并排序时间 O(n log n)，空间 O(n)

把数组从中间分成两半，分别递归排好，再用双指针把两个有序段合并到辅助数组，最后拷回原数组。合并时相等元素先取左半部分的，所以排序是稳定的。

最坏情况也是 O(n log n) 且稳定，还能顺便统计逆序对，也适合链表和外部排序。代价是需要 O(n) 辅助空间。

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        tmp = [0] * len(nums)

        def merge_sort(lo, hi):
            if lo >= hi:
                return
            mid = (lo + hi) // 2
            merge_sort(lo, mid)
            merge_sort(mid + 1, hi)
            i, j, k = lo, mid + 1, lo
            while i <= mid and j <= hi:
                if nums[i] <= nums[j]:
                    tmp[k] = nums[i]
                    i += 1
                else:
                    tmp[k] = nums[j]
                    j += 1
                k += 1
            while i <= mid:
                tmp[k] = nums[i]
                i += 1
                k += 1
            while j <= hi:
                tmp[k] = nums[j]
                j += 1
                k += 1
            nums[lo:hi + 1] = tmp[lo:hi + 1]

        merge_sort(0, len(nums) - 1)
        return nums

class Solution {
    int[] tmp;

    void mergeSort(int[] nums, int lo, int hi) {
        if (lo >= hi) return;
        int mid = (lo + hi) / 2;
        mergeSort(nums, lo, mid);
        mergeSort(nums, mid + 1, hi);
        int i = lo, j = mid + 1, k = lo;
        while (i <= mid && j <= hi) tmp[k++] = nums[i] <= nums[j] ? nums[i++] : nums[j++];
        while (i <= mid) tmp[k++] = nums[i++];
        while (j <= hi) tmp[k++] = nums[j++];
        for (k = lo; k <= hi; k++) nums[k] = tmp[k];
    }

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

class Solution {
public:
    vector<int> tmp;

    void mergeSort(vector<int>& nums, int lo, int hi) {
        if (lo >= hi) return;
        int mid = (lo + hi) / 2;
        mergeSort(nums, lo, mid);
        mergeSort(nums, mid + 1, hi);
        int i = lo, j = mid + 1, k = lo;
        while (i <= mid && j <= hi) tmp[k++] = nums[i] <= nums[j] ? nums[i++] : nums[j++];
        while (i <= mid) tmp[k++] = nums[i++];
        while (j <= hi) tmp[k++] = nums[j++];
        for (k = lo; k <= hi; k++) nums[k] = tmp[k];
    }

    vector<int> sortArray(vector<int>& nums) {
        tmp.assign(nums.size(), 0);
        mergeSort(nums, 0, (int)nums.size() - 1);
        return nums;
    }
};

func sortArray(nums []int) []int {
	tmp := make([]int, len(nums))
	var mergeSort func(lo, hi int)
	mergeSort = func(lo, hi int) {
		if lo >= hi {
			return
		}
		mid := (lo + hi) / 2
		mergeSort(lo, mid)
		mergeSort(mid+1, hi)
		i, j, k := lo, mid+1, lo
		for i <= mid && j <= hi {
			if nums[i] <= nums[j] {
				tmp[k] = nums[i]
				i++
			} else {
				tmp[k] = nums[j]
				j++
			}
			k++
		}
		for ; i <= mid; i, k = i+1, k+1 {
			tmp[k] = nums[i]
		}
		for ; j <= hi; j, k = j+1, k+1 {
			tmp[k] = nums[j]
		}
		copy(nums[lo:hi+1], tmp[lo:hi+1])
	}
	mergeSort(0, len(nums)-1)
	return nums
}

var sortArray = function(nums) {
    const tmp = new Array(nums.length);
    const mergeSort = (lo, hi) => {
        if (lo >= hi) return;
        const mid = (lo + hi) >> 1;
        mergeSort(lo, mid);
        mergeSort(mid + 1, hi);
        let i = lo, j = mid + 1, k = lo;
        while (i <= mid && j <= hi) tmp[k++] = nums[i] <= nums[j] ? nums[i++] : nums[j++];
        while (i <= mid) tmp[k++] = nums[i++];
        while (j <= hi) tmp[k++] = nums[j++];
        for (k = lo; k <= hi; k++) nums[k] = tmp[k];
    };
    mergeSort(0, nums.length - 1);
    return nums;
};

function sortArray(nums: number[]): number[] {
    const tmp: number[] = new Array(nums.length);
    const mergeSort = (lo: number, hi: number): void => {
        if (lo >= hi) return;
        const mid = (lo + hi) >> 1;
        mergeSort(lo, mid);
        mergeSort(mid + 1, hi);
        let i = lo, j = mid + 1, k = lo;
        while (i <= mid && j <= hi) tmp[k++] = nums[i] <= nums[j] ? nums[i++] : nums[j++];
        while (i <= mid) tmp[k++] = nums[i++];
        while (j <= hi) tmp[k++] = nums[j++];
        for (k = lo; k <= hi; k++) nums[k] = tmp[k];
    };
    mergeSort(0, nums.length - 1);
    return nums;
}

栈与堆专题的其他题目

查看栈与堆全部题目 →