三色排序：荷兰国旗最优解，sql题目基础50题。
问题描述
LeetCode 75题“颜色分类”要求将一个包含红色（0）、白色（1）和蓝色（2）的数组原地排序，使得相同颜色的元素相邻且按红、白、蓝的顺序排列。这个问题也被称为“荷兰国旗问题”，由计算机科学家Edsger Dijkstra提出，用于解决三色分类问题。
荷兰国旗问题解法
荷兰国旗问题的核心思想是通过分区将数组划分为三个部分：红色区、白色区和蓝色区。使用三个指针（low、mid、high）来实现分区：
low指向红色区的末尾。mid用于遍历当前元素。high指向蓝色区的起始位置。
初始化时，low和mid指向数组起始位置，high指向数组末尾。遍历过程中：
- 如果
nums[mid] == 0，交换nums[low]和nums[mid]，并将low和mid右移。 - 如果
nums[mid] == 1，mid右移。 - 如果
nums[mid] == 2，交换nums[mid]和nums[high]，并将high左移。
def sortColors(nums): low, mid, high = 0, 0, len(nums) - 1 while mid <= high: if nums[mid] == 0: nums[low], nums[mid] = nums[mid], nums[low] low += 1 mid += 1 elif nums[mid] == 1: mid += 1 else: nums[mid], nums[high] = nums[high], nums[mid] high -= 1插入排序解法
插入排序是一种简单的排序算法，适用于小规模数据或部分有序数据。对于颜色分类问题，可以通过插入排序逐步将元素插入到正确的位置：
- 从第二个元素开始遍历数组。
- 将当前元素与前面的元素比较，如果前面的元素更大，则交换位置。
- 重复直到当前元素到达正确位置。
def sortColors(nums): for i in range(1, len(nums)): key = nums[i] j = i - 1 while j >= 0 and nums[j] > key: nums[j + 1] = nums[j] j -= 1 nums[j + 1] = key分区解法
分区是快速排序的核心步骤，也可以用于颜色分类问题。通过两次分区将数组分为三部分：
- 第一次分区将红色（0）移到左侧。
- 第二次分区将白色（1）移到中间，蓝色（2）自然位于右侧。
def sortColors(nums): # 第一次分区：将0移到左侧 boundary = 0 for i in range(len(nums)): if nums[i] == 0: nums[i], nums[boundary] = nums[boundary], nums[i] boundary += 1 # 第二次分区：将1移到中间 boundary = boundary for i in range(boundary, len(nums)): if nums[i] == 1: nums[i], nums[boundary] = nums[boundary], nums[i] boundary += 1性能分析
- 荷兰国旗解法：时间复杂度为O(n)，仅需一次遍历，空间复杂度为O(1)，是最优解法。
- 插入排序解法：时间复杂度为O(n^2)，空间复杂度为O(1)，适用于小规模数据。
- 分区解法：时间复杂度为O(n)，但需要两次遍历，空间复杂度为O(1)。
应用场景
荷兰国旗问题不仅适用于颜色分类，还可以扩展到多分区排序问题。插入排序和分区解法虽然简单，但在特定场景下仍有应用价值。