荷兰国旗问题

题目描述：　　

　　给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)

解题思路：

　　使用两个指针：p1,p2

　　p1 = -1;  //左指针，在p1左边并含p1的所有数都<num

　　p2 = N ； //右指针，p2=N在p2的右边含p2的所有数都大于num

　　然后比较arr与num的值，并与相应的p1,p2的位置交换

代码实现：

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 
 6 void swap(int& a, int &b)
 7 {
 8     int temp;
 9     temp = a;
10     a = b;
11     b = temp;
12 }
13 
14 //记住，单次遍历n次数组的时间复杂度 = n*O(N) == O(N)
15 
16 template<class T>
17 void Test(T& array , const int num)
18 {
19     int  p1, p2;//两个指针
20     p1 = -1;//左指针，在p1左边并含p1的所有数都<num
21     p2 = sizeof(array) / sizeof(array[0]);//右指针，p2=N在p2的右边含p2的所有数都大于num
22     for (int i = 0; i != p2; )
23     {
24         if (array[i] < num)
25             swap(array[++p1], array[i++]);
26         else if (array[i] > num)
27             swap(array[--p2], array[i]);
28         else
29             ++i;
30 
31     }
32 
33 }
34 
35 void Heland()
36 {
37     int arr[] = { 1, 5,7,4,6,4,2,9 };    
38     Test(arr, 4);
39     for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i)
40         cout << arr[i] << \"  \";
41     cout << endl << \"**************************\" << endl;
42 }