leetcode75之颜色分类

题目描述：

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

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

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

示例:

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

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

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

实现如下：

 def sortColors(nums):

     '''

 　　 使用计数排序思想

     :param nums:

     :return:

     '''

     colors = [0] * 3

     for i in nums:

         colors[i] += 1

     j = 0

     for m in range(3):

         for n in range(colors[m]):  # 控制次数

             nums[j] = m

             j += 1

     return nums

 print('==============测试colorsort()============')

 nums = [2, 1, 1, 0, 2, 1]

 result = sortColors(nums)

 print("result=", result)

 def bubbleSort(nums):

     '''

     实现冒泡排序

     :param nums:

     :return:

     '''

     for i in range(len(nums) - 1):  # 控制循环次数

         for j in range(len(nums) - i - 1):  # 控制每次循环时在指定数组长度内进行

             if nums[j] > nums[j + 1]:

                 nums[j], nums[j + 1] = nums[j + 1], nums[j]

             else:

                 continue

     return nums

 print("----------------测试Bubblesort()-------------")

 nums = [2, 1, 3, 5, 6, 2, 0, 2, 0, 2]

 result = bubbleSort(nums)

 print("result=", result)

 def colorsort1(nums):

     '''

     使用桶排序思想

     :param nums:

     :return:

     '''

     color = [[] for i in range(3)]

     for i in nums:

         color[i].append(i)

     nums[:] = []

     for i in color:

         nums.extend(i)

     return nums

 print("-----------测试colorsort1()------------")

 nums = [2, 1, 2, 1, 0, 1, 0, 0, 2]

 result = colorsort1(nums)

 print("result=", result)

 def colorsort2(nums):

     '''

     荷兰三色旗问题

     :param nums:

     :return:

     '''

     p0 = curr = 0

     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

     return nums

 print("------------测试colorsort2()--------------")

 nums = [2, 0, 2, 0, 0, 1, 1, 1]

 result = colorsort2(nums)

 print("result=", result)

输出：

==============测试colorsort()============

result= [0, 1, 1, 1, 2, 2]

----------------测试Bubblesort()-------------

result= [0, 0, 1, 2, 2, 2, 2, 3, 5, 6]

-----------测试colorsort1()------------

result= [0, 0, 0, 1, 1, 1, 2, 2, 2]

------------测试colorsort2()--------------

result= [0, 0, 0, 1, 1, 1, 2, 2]

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