leet_75_sort_color（荷兰国旗问题）

• leet_code地址：点我

• 问题描述：

  • 一个由0，1，2乱序组成的数组，使用o(1)的空间复杂度，且时间复杂度在0（n）范围内（只遍历一遍数组），将数组进行排序。
  • 因为该排序问题属于有序的三分类问题，类似于荷兰国旗（红白蓝）撕成很多条进行排序问题，所以也称为荷兰国旗问题，该题也可拓展为该类型：一直欲排序数组元素值（相同元素值有很多）的排序问题。

• 方法一分析：

  • 一般对时间复杂度和空间复杂度要求较高的（如排序）相关问题都要考虑使用双指针，甚至三指针。
  • 该问题确定使用三个指针（low, mid, high）来实现后，就要确定问题的“主要矛盾”,抓住主要矛盾就容易解题了。三个指针中mid指针作为主要矛盾。其次，三个指针所充当的角色要定位好，如low和mid指针分别指向的是0和1元素的下一个位置，而high指针指向的是2元素的上一个位置。

• 方法一c++代码实现：

class Solution 
{
private:
	int* data;
	int length;
public:
	Solution(int *value, int len) :data(value),length(len){};
	void sort_color_1()
	{
		int low = 0, mid = 0, high = length - 1;
		while(mid <= high)
		{
			if (data[mid] == 0)
			{
				int temp = data[mid];
				data[mid] = data[low];
				data[low] = temp;
				low++;
				mid++;
			}
			else if (data[mid] == 1)
				mid++;
			else if(data[mid] == 2)//mid == 2
			{
				int temp = data[mid];
				data[mid] = data[high];
				data[high] = temp;
				high--;
			}
		}
	}
	void get_vales()
	{
		for (int i = 0; i < length; i++)
			cout << data[i];
		cout << endl;
	}
};

主调函数：

int main(int argc, char* argv[])
{
	int data[] = { 2, 0, 2, 1, 1, 0};
	Solution solution = Solution(data, 6);
	solution.get_vales();
	clock_t start_time, end_time;
	start_time = clock();
	solution.sort_color_1();
	end_time = clock();
	solution.get_vales();
	cout << "time:" << end_time - start_time <<"ms"<<endl;
	system("pause");
	return 0;
}

• 方法二分析：
  • 该方法不用指针、不用交换元素即可实现，的确是绝！
  • 因为是已知数组内所有元素的排序问题，那么同样定义三个指针low, mid,high分别指向0，1，2元素的元素尾部的下一个位置，遇到0三个指针都向后移，遇到1向后移动mid和high指针，遇到2向后移动high指针。
  • 具体思路：
    
• 方法二C++代码：

	void sort_color_2()
	{
		int low = 0, mid = 0, high = 0;
		for (int i = 0; i < length; i++)
		{
			if (data[i] == 0)
			{
				data[high++] = 2;
				data[mid++] = 1;
				data[low++] = 0;
			}
			else if (data[i] == 1)
			{
				data[high++] = 2;
				data[mid++] = 1;
			}
			else if (data[i] == 2)
			{
				data[high++] = 2;
			}
		}
	}

注：以上的for循环可以使用c++11的新特性–区间迭代，这样更加优雅：

for(int val:data)  //data 为int类型的数组（或容器变量），不能是指针类型