三色排序：荷兰国旗最优解，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] 1mid右移。如果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)。应用场景荷兰国旗问题不仅适用于颜色分类还可以扩展到多分区排序问题。插入排序和分区解法虽然简单但在特定场景下仍有应用价值。