LeetCode 分类颜色
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。示例:
输入: [2,0,2,1,1,0]输出: [0,0,1,1,2,2]
进阶：
-
- 一个直观的解决方案是使用计数排序的两趟扫描算法。首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
- 你能想出一个仅使用常数空间的一趟扫描算法吗？
1. 使用基数排序：
1 class Solution: 2 def sortColors(self, nums): 3 """ 4 :type nums: List[int] 5 :rtype: void Do not return anything, modify nums in-place instead. 6 """ 7 #桶排序 8 count = [] 9 for i in [0,1,2]:10 count.append(nums.count(i))11 j=012 for i in [0,1,2]:13 while count[i]>0:14 nums[j] = i15 j += 116 count[i] -= 117 print(nums)
2. 使用快排：
两路快排的Partition的实现（c++）：
1 // v为pivot，初始存储在arr[l]的位置 2 int j = l; // 循环过程保持 arr[l+1...j] < v ; arr[j+1...i) > v 3 for( int i = l + 1 ; i <= r ; i ++ )4 if( arr[i] < v ) 5 swap( arr[++j] , arr[i] );6 swap( arr[l] , arr[j]); // 此时，j指向pivot的正确位置
1 class Solution: 2 def _sortColors(self, nums, l, r): 3 if l >= r: 4 return 5 # pratition 6 j = l+1 7 pivot = nums[l] 8 for i in range(l+1, r+1): 9 if nums[i] < pivot:10 nums[i], nums[j] = nums[j], nums[i]11 j += 112 j -= 113 nums[l], nums[j] = nums[j], nums[l]14 15 #devide16 self._sortColors(nums, l, j-1)17 self._sortColors(nums, j+1, r)18 def sortColors(self, nums):19 """20 :type nums: List[int]21 :rtype: void Do not return anything, modify nums in-place instead.22 """23 self._sortColors(nums, 0, len(nums)-1)
这样的一个快排，在面临有序或者近乎有序的数组时，会退化成为一个O(n^2)的算法。于是我们使用了一个很简单的随机选取pivot的方式来处理这个问题。这步随机化让快速排序的时间期望成为了O(nlogn)，并且只有极低的概率退化为O(n^2)。
面对有大量重复元素的数据时，还是有可能退化成O(n^2)级别的。通过这个思路，我们可以进一步优化，提出三路快排的思想。3. 三路快排
三路快排的Partition代码是这样的。
1 // v为pivot，初始存储在arr[l]的位置 2 int lt = l; // 循环过程中保持 arr[l+1...lt] < v 3 int gt = r + 1; // 循环过程中保持 arr[gt...r] > v 4 int i = l+1; // 循环过程中保持 arr[lt+1...i) == v 5 while( i < gt ){ 6 if( arr[i] < v ){ 7 swap( arr[i++], arr[lt+1]); lt ++; } 8 else if( arr[i] > v ){ 9 swap( arr[i], arr[gt-1]); gt --; } 10 else // arr[i] == v 11 i ++; 12 } 13 swap( arr[l] , arr[lt] ); 14 // 此时 arr[lt...gt-1]部分为数组中元素等于v的部分 15 // 之后只需要递归地对arr[l...lt-1]和arr[gt...r]两部分进行三路快排即可 1 class Solution: 2 def _sortColors(self, nums, l, r): 3 if l >= r: 4 return 5 # pratition 6 pivot = nums[l] 7 j = l+1 #循环过程中保持 arr[lt+1...j) == v 8 lt = l #循环过程中保持 arr[l+1...lt] < v 9 gt = r # 循环过程中保持 arr[gt...r] > v10 while j <= gt:11 if nums[j] < pivot:12 nums[lt], nums[j] = nums[j], nums[lt]13 j += 114 lt += 115 elif nums[j] > pivot:16 nums[gt], nums[j] = nums[j], nums[gt]17 gt -= 118 else:19 j += 120 21 #devide22 self._sortColors(nums, l, lt-1)23 self._sortColors(nums, gt+1, r)24 def sortColors(self, nums):25 """26 :type nums: List[int]27 :rtype: void Do not return anything, modify nums in-place instead.28 """29 self._sortColors(nums, 0, len(nums)-1)