排序数组

难度: Medium

给你一个整数数组 nums，请你将该数组升序排列。

示例 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⁴
-5 * 10⁴ <= nums[i] <= 5 * 10⁴

Submission

运行时间: 62 ms

内存: 22.2 MB

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        if not nums:
            return []
        pivot = random.choice(nums)
        left, middle, right = [],[],[]
        for num in nums:
            if num < pivot:
                left.append(num)
            elif num > pivot:
                right.append(num)
            else:
                middle.append(num)
        return self.sortArray(left) + middle + self.sortArray(right)

Explain

该题解采用快速排序的方法对数组进行排序。首先，如果输入数组为空，则直接返回空数组。接下来，从数组中随机选择一个元素作为基准点（pivot）。然后，遍历整个数组，根据每个元素与基准点的大小关系，将其分配到三个不同的列表：left（小于基准的元素），middle（等于基准的元素），right（大于基准的元素）。最后，对left和right列表递归进行相同的排序过程，并将排序后的结果与middle列表连接起来，形成最终的排序数组。通过随机选择基准点，该算法试图避免最坏情况的发生，即每次划分都非常不平衡。

时间复杂度: 平均O(n log n)，最坏O(n^2)

空间复杂度: O(n)

# 快速排序实现
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        if not nums:
            return []
        # 随机选择一个元素作为基准点
        pivot = random.choice(nums)
        left, middle, right = [], [], []
        for num in nums:
            if num < pivot:
                left.append(num)  # 小于基准的元素
            elif num > pivot:
                right.append(num)  # 大于基准的元素
            else:
                middle.append(num)  # 等于基准的元素
        # 递归排序左右两部分，然后与中间部分连接
        return self.sortArray(left) + middle + self.sortArray(right)

Explore

随机选择基准点的主要目的是为了减少快速排序在最坏情况下的时间复杂度。在标准的快速排序中，如果每次都选择第一个或最后一个元素作为基准，那么在数组已经有序或接近有序的情况下，每次分区只能将一个元素与其他元素分开，导致递归深度接近数组长度，使得时间复杂度退化到O(n^2)。通过随机选择基准，可以大概率避免这种极端的不平衡划分，使得分区更加均匀，从而保持算法的平均时间复杂度为O(n log n)。

快速排序的最坏情况发生在每次递归调用时，基准点使得一侧的元素数量极少（例如只有一个元素或没有元素），而另一侧包含了其余所有元素。这种情况下，排序的时间复杂度会上升到O(n^2)。通过随机选择基准点，可以显著降低选择到极端基准点的概率，使得每次分区更加均衡，分区的大小接近于总元素数的一半，从而保持整个排序过程的效率。

在快速排序的实际实现中，通常会有几种优化方法来处理小数组的情况。例如，当子数组的大小下降到一个较小的阈值时，可以转而使用插入排序，因为插入排序在小数组上表现得更好。此外，递归的基本情况是当子数组长度为0或1时，此时数组已是有序的。然而，在提供的解法中，没有明确实现这些优化。每次递归调用都会执行，即使是只有一个元素的子数组也会进行递归调用，这可能不是最优的处理方式。