目录
荷兰国旗问题
快排改进（随机快排）
描述
荷兰国旗有三种条纹构成，自上到下条纹的颜色依次为红、白、蓝。现有若干红、白、蓝三种颜色的条纹序列，要将它们重新排列使所有相同颜色的条纹在一起。本问题要求将所有红色的条纹放最上边、所有白色的条块放中间、所有蓝色的条纹放最下边。（如下所示）
实际上可以把题目简化为编程题目：
给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)。
题目思路：实际上类似于快排的思想，设3个移动变量，假设
int arr[10] = {2,5,1,3,4,9,5,8,5,7}; num = 5; //中间数假设三个指针，分别指向数组的最左侧减一，最右侧加1，以及数组最左端。
开始排序：
1.当 i 指向 第0位 时，发现 arr[0] 小于 num(也就是5)， 那么便 （L-1）+1 = L 位与 第 i 位进行交换，并且各向前移动一位，变成如下：（由于L位和 i 位恰好都为 0 ，所以发生自身与自身交换）
2.当 i 指向 第1位 时，发现 arr[1] 等于 num， 那么 i 向前移动一位，由于左边不交换，L的位置不动，变成如下：
3.当 i = 2 时，发现 arr[2] 小于 num， 那么便 L+1 位与 第 i 位进行交换，并且各向前移动一位，变成如下：
4. i = 3, i = 4 都是小于 num，所以操作跟步骤3 一样，得到如下。此时 i = 5 ，arr[5] = 9 > num，所以arr[i] 与 arr[(R+1)-1]进行交换，这里注意，由于交换以后原来的arr[(R+1)-1]的值并不一定小于等于num，所以我们不能让 i 前进一步，必须继续判断 arr[i] 与 arr[R - 1] 的值，进行交换，以此类推，直到不交换为止，图示如下：
5.这里到最后一步，i = 7，arr[7] = 8 > num ，那么便使得 arr[7] 与 arr[R - 1]交换，这里可以看出 R - 1 = 7，所以需要停止搜索了，终止的条件就是 i 与右边指针所指相等。
代码很简单如下：
void mySwap(int * a, int *b){ if(a != b){ (*a) ^= (*b); (*b) ^= (*a); (*a) ^= (*b); } } void mySort(int *arr, int L,int R, int num){ int i = 0; while(i < R){ if(arr[i] < num) mySwap(&arr[++L],&arr[i]); else if(arr[i] > num){ mySwap(&arr[--R], &arr[i]); continue; } i++; } } int main() { int arr[10] = {2,5,1,3,4,9,5,8,5,7}; mySort(arr,-1,10,5); for(int i =0; i<10; i++){ cout<<arr[i]<<" "; } return 0; }
通过上面的思想实际上我们可以对快排进行改进，快排的思想是拿取一个数字然后把其定位到正确的位置；但是实际上数组中不一定只有一个大小为拿取数大小的数字，可能有一批数字均相等，此时我们便可以利用上述问题的解决方法进改进。
把数组分成三块小于num，等于num，大于num；之后进行递归时只要对小于和大于两边的数组进行排序即可，这样效率也会提升。其次，由于在快排中，我们通常拿取的比较数字一般是首个或者末尾，但是这样如果遇到 顺序数列 {5，4，3，2，1}或者{1，2，3，4，5}，效率会大大降低，使得时间复杂度可能降为O(N^2)；为了提高效率，我们可以采取随机拿取某个数来进行比较，这个方法数学推导也证明了期望时间复杂度为 O(NlogN)。
代码如下：
void mySwap(int * a, int *b){ if(a != b){ (*a) ^= (*b); (*b) ^= (*a); (*a) ^= (*b); } } void quickSort2(int *arr, int left, int right){ if(left < right){ mySwap(&arr[left + rand()%(right-left+1)],&arr[right]); //随机拿取 int i = left, L = left - 1, R = right; while(i < R){ if(arr[i] < arr[right]) mySwap(&arr[++L],&arr[i++]); else if(arr[i] > arr[right]) mySwap(&arr[--R],&arr[i]); else i++; } mySwap(&arr[R],&arr[right]);//arr[right]最后进行交换，前面不变 quickSort2(arr,left,L); quickSort2(arr,R+1,right); } }
