题目描述：

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。　　

示例:

  1. 输入: [2,0,2,1,1,0]
  2. 输出: [0,0,1,1,2,2]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-colors
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
实现如下：
  1.   1 def sortColors(nums):
  2.   2     '''
  3.   3 　　 使用计数排序思想
  4.   4     :param nums:
  5.   5     :return:
  6.   6     '''
  7.   7     colors = [0] * 3
  8.   8 
  9.   9     for i in nums:
  10.  10         colors[i] += 1
  11.  11 
  12.  12     j = 0
  13.  13     for m in range(3):
  14.  14         for n in range(colors[m]):  # 控制次数
  15.  15             nums[j] = m
  16.  16             j += 1
  17.  17 
  18.  18     return nums
  19.  19 
  20.  20 
  21.  21 print('==============测试colorsort()============')
  22.  22 nums = [2, 1, 1, 0, 2, 1]
  23.  23 result = sortColors(nums)
  24.  24 print("result=", result)
  25.  25 
  26.  26 
  27.  27 def bubbleSort(nums):
  28.  28     '''
  29.  29     实现冒泡排序
  30.  30     :param nums:
  31.  31     :return:
  32.  32     '''
  33.  33 
  34.  34     for i in range(len(nums) - 1):  # 控制循环次数
  35.  35         for j in range(len(nums) - i - 1):  # 控制每次循环时在指定数组长度内进行
  36.  36             if nums[j] > nums[j + 1]:
  37.  37                 nums[j], nums[j + 1] = nums[j + 1], nums[j]
  38.  38             else:
  39.  39                 continue
  40.  40 
  41.  41     return nums
  42.  42 
  43.  43 
  44.  44 print("----------------测试Bubblesort()-------------")
  45.  45 nums = [2, 1, 3, 5, 6, 2, 0, 2, 0, 2]
  46.  46 result = bubbleSort(nums)
  47.  47 print("result=", result)
  48.  48 
  49.  49 
  50.  50 def colorsort1(nums):
  51.  51     '''
  52.  52     使用桶排序思想
  53.  53     :param nums:
  54.  54     :return:
  55.  55     '''
  56.  56     color = [[] for i in range(3)]
  57.  57     for i in nums:
  58.  58         color[i].append(i)
  59.  59 
  60.  60     nums[:] = []
  61.  61 
  62.  62     for i in color:
  63.  63         nums.extend(i)
  64.  64 
  65.  65     return nums
  66.  66 
  67.  67 
  68.  68 print("-----------测试colorsort1()------------")
  69.  69 nums = [2, 1, 2, 1, 0, 1, 0, 0, 2]
  70.  70 result = colorsort1(nums)
  71.  71 print("result=", result)
  72.  72 
  73.  73 
  74.  74 def colorsort2(nums):
  75.  75     '''
  76.  76     荷兰三色旗问题
  77.  77     :param nums:
  78.  78     :return:
  79.  79     '''
  80.  80     p0 = curr = 0
  81.  81     p2 = len(nums) - 1
  82.  82 
  83.  83     while curr <= p2:
  84.  84         if nums[curr] == 0:
  85.  85             nums[p0], nums[curr] = nums[curr], nums[p0]
  86.  86             p0 += 1
  87.  87             curr += 1
  88.  88         elif nums[curr] == 2:
  89.  89             nums[curr], nums[p2] = nums[p2], nums[curr]
  90.  90             p2 -= 1
  91.  91         else:
  92.  92             curr += 1
  93.  93 
  94.  94     return nums
  95.  95 
  96.  96 
  97.  97 print("------------测试colorsort2()--------------")
  98.  98 nums = [2, 0, 2, 0, 0, 1, 1, 1]
  99.  99 result = colorsort2(nums)
  100. 100 print("result=", result)

输出：

  1. ==============测试colorsort()============
  2. result= [0, 1, 1, 1, 2, 2]
  3. ----------------测试Bubblesort()-------------
  4. result= [0, 0, 1, 2, 2, 2, 2, 3, 5, 6]
  5. -----------测试colorsort1()------------
  6. result= [0, 0, 0, 1, 1, 1, 2, 2, 2]
  7. ------------测试colorsort2()--------------
  8. result= [0, 0, 0, 1, 1, 1, 2, 2]

总结：上述一共采用四种方法解决该问题。四种方法使用不同的思想方法。这里需要说明一下最后一种荷兰三色旗采用的三指针方法。初始化三个指针分别为p0,curr和p2,p0初始化为指向第一个元素，p2指向最后一个元素，curr指针用来遍历整个数组，指向当前元素，所以初始化也为0。当指向元素为0时，交换当前元素和p0,当指向元素为2时，交换当前元素和p2,再紧接着判断当前元素的值，代码中表现为curr不增加。

版权声明：本文为rounie原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/rounie/p/13084228.html