题目描述：　　

　　给定一个数组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 
     
       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 << N）次数组的时间复杂度 = n*O(N) == O(N)15 template
      
       //目前我只想到了使用模板来实现引用数组，其他的引用方法都报错了。16 void Test(T& array , const int num)17 {18     int N, p1, p2;//两个指针19     p1 = -1;//左指针，在p1左边并含p1的所有数都
       
         num)26             swap(array[--p2], array[i]);27         else28             ++i;29 30     }31 32 }33 34 void Heland()35 {36     int arr[] = { 1, 5,7,4,6,4,2,9 };    37     Test(arr, 4);38     for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i)39         cout << arr[i] << "  ";40     cout << endl << "**************************" << endl;41 }