重组数组问题可以表述为
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
核心代码如下
void reorder(int *arr, int len) { if (arr == nullptr || len <= 0) return; int *bgn = arr; int *end = arr + len - 1; while (bgn < end) { //while (*bgn % 2 == 1) while (*bgn & 0x1) bgn ++; //while (*end % 2 == 0) while (!(*end & 0x1)) end --; if (bgn < end){ int tmp = *bgn; *bgn = *end; *end = tmp; bgn ++; end --; } } }
在编写代码的时候，会发现与快排的代码比较相似：同样是两个指针，同样是while循环里有while循环。而快排的核心代码可能更复杂一些，因为还涉及到递归。于是将快排的核心部分找出来研究：
int sort(int *data, int left, int right){ if(left >= right) return 0; int i = left; int j = right; int key = data[i]; while(i < j){ //每次大循环内可能同时有i++和j--，如果二层循环不加i < j，可能会导致i > j?(猜想)，经测试，不加i < j，结果一样 //while(i < j && key < data[j]){ while(key < data[j]){//后面的值比基准值大就正常移动，一旦碰到比基准值小的就停下 j--;//从后往前移动 } data[i] = data[j];//将小于基准的值放到前面 //while(i < j && key >= data[i]){ while(key >= data[i]){//基准值比前面的值小就正常移动，一旦碰到比基准值大的就停下 i++;//从前往后移动 } data[j] = data[i];//将大于基准的值放在后面，j的位置是刚才从后往前移动时小于基准值的位置，已经被挪到前面 } data[j] = key;//当i==j时，循环结束，此时的位置i==j即为基准值应该放置的位置。 sort(data, left, i-1);//排列基准位置左边的序列 sort(data, i+1, right);//排列基准位置右边的序列 }
其实重组数组问题，也是一种排序。可以归为特殊的排序问题，所以在实现上跟快排有相似的代码组织结构。
由此我们可以抽象出一个模型，使用以下逻辑：
排序函数funtion()
- 准备工作：将两个指针或索引分别对应数组的头尾。
- 循环1，前面的指针不超过后面的指针。
a. 循环2a，以某种条件移动头指针。
b. 循环2b，以某种条件移动尾指针。
c. 移动后的指针满足排序条件，交换两个指针对应的数值。- 结束，或递归调用此过程。
还有一个比较两个压缩字符串有多少相同字符的问题，结构类似，一并贴上。
#include <stdio.h> // str1 = 2a3b5c2d // str2 = 3c2b4d3c int compare(char* str1, char* str2){ int n1 = 0, n2 = 0, n, count = 0; int c1 = 0, c2 = 0; char *p1 = str1, *p2 = str2; while (*p1 != '\0' || *p2 != '\0'){ if (n1 == 0){ while (*p1 >= '0' && *p1 <= '9'){ n1 = n1*10 + (*p1 - '0'); p1++; } c1 = *p++; } if (n2 == 0){ while (*p2 >= '0' && *p2 <= '9'){ n2 = n2*10 + (*p2 - '0'); p2++; } c2 = *p2++; } n = n1 < n2 ? n1 : n2; if (c1 == c2) { count += n; } n1 -= n; n2 -= n; } return count; } int main() { printf("%d\n",compare("2a3b5c2d","3c2b4d3c")); printf("%d\n",compare("5a","1c1b1d1c1a")); }
将以上三个问题研究完，相信你应该会对这一类排序问题有比较深入的了解，并能够熟练使用双重while循环结构。
