排序（2）

计数排序

题目

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

• 注意:
  不能使用代码库中的排序函数来解决这道题。

• 示例:

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

• 进阶：

一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-colors
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解答

我的垃圾答案(本质只能应付这一题)：

`

def sortColors(self, nums: List[int]) -> None:
    """
    Do not return anything, modify nums in-place instead.
    """
    """使用计数排序"""
    maxnum=max(nums)
    minnum=min(nums)
    listcount=[0 for i in range(maxnum+1)]
    for i in range(len(nums)):
        listcount[nums[i]]=listcount[nums[i]]+1
    for i in range(1,len(listcount)):
        listcount[i]=listcount[i]+listcount[i-1]
    for i in range(len(listcount)-1,0,-1):
        for j in range(listcount[i-1],listcount[i]):
            nums[j]=i
    for i in range(0,listcount[0]):
        nums[i]=0

`

其他答案（模仿指针）

`

def sortColors(self, nums: List[int]) -> None:
    # 对于所有 idx < p0 : nums[idx < p0] = 0
    # curr是当前考虑元素的下标
    p0 = curr = 0
    # 对于所有 idx > p2 : nums[idx > p2] = 2
    p2 = len(nums) - 1
    while curr <= p2:
        if nums[curr] == 0:
            nums[p0], nums[curr] = nums[curr], nums[p0]
            p0 += 1
            curr += 1
        elif nums[curr] == 2:
            nums[curr], nums[p2] = nums[p2], nums[curr]
            p2 -= 1
        else:
            curr += 1

`

反思

躺平，学不来，想不到。哭泣。