荷兰国旗问题

第一次见到这个问题的时候，脑子里面第一反应居然是荷兰豆。。。

好了，言归正传，荷兰国旗就是比较分明的三条颜色，映射到程序员身上就是给定一个数组，以及一个target目标，让你给这个数组排个序，要求分成三段，第一段都小于target，第二段都等于target，第三段都大于target。

第二反应这东西就是快速排序的第一部分，只不过中间有序，这样的话，由于是分了三段，就需要两个指针i, j来记录，在实际遍历数组的时候，是需要另外的一个表示当前遍历结尾的k变量，i，j，和k将整个数组分成四个部分[0,i)已经排序，小于target部分，[i,j)已经排序，等于target部分，[j,k],未排序部分，(k,~)已经排序，大于target部分。这样的话，遍历的起始和终止条件就出现了，i,j起始都为0，k=n-1,终止条件就是j>k，所以代码如下：

点击(此处)折叠或打开

1. void flag_of_netherland(int *arr, int n, int target){
   
2.     int i=0,j=0, k=n-1;
   
3.     int temp;
   
4.     while(j<=k){
   
5.         if(arr[j]<target){
   
6.             temp=arr[i];
   
7.             arr[i]=arr[j];
   
8.             arr[j]=temp;
   
9.             i++,j++;
   
10.         }else if(arr[j]>target){
    
11.             temp=arr[k];
    
12.             arr[k]=arr[j];
    
13.             arr[j]=temp;
    
14.             k--;// 这会不能j++,因为你不知道换过来的是个啥东西
    
15.         }else{
    
16.             j++;
    
17.         }
    
18.     }
    
19. }