划分对于分治的算法设计很重要，下面就专门说一个划分的算法设计，然后再举例子说一些具体的应用。
int Partition(int data[], int start, int end){ if(data == NULL) return -1; int index = RandomInRange(start, end); int small = start - 1; swap(data[index], data[end]); for(index = start; index < end; index++) { if(data[index] < data[end]) { ++small; if(small != index) { swap(data[small], data[index]); }//if }//if }//for ++small; swap(data[small], data[end]); return small;}//Partition() 下面看一下划分的应用。
快速排序中的划分
void QuickSort(int data[], int start, int end){ if(start == end) return; int index = Partition(data, start, end); if(index > start) QuickSort(data, start, index - 1); if(index < end) QuickSort(data, index + 1, end);} 递归的程序一定要有递归出口。
查找第K大的数字
int findKth(int *data, int start, int end, int k){ int pos = partition(data, start, end); if(pos + 1 == k) return data[pos]; else if(pos + 1 > k) return findKth(data,start, pos -1, k); else return findKth(data, pos + 1, end, k);}int findKthLargest(int *nums, int numsSize, int k) { //转换成求第k小元素 int m = numsSize - k + 1; int result = findKth(nums, 0, numsSize - 1, m); return result;}
数组中出现次数超过一半的数字
这个问题貌似很难，但是设想如果这个数组已经排序好了，那么这个出现次数超过一半的数字肯定会出现在中位数的地方。所以可以利用上面的算法，找数组中的中位数小的元素。
但是测试用例一定要首先写好，要防止空的数组、数组中根本不存在超过一半多这样的数字，这次用循环来实现找第k小的元素，不用递归了。
int MoreThanHalfNum_Solution(vector numbers) { if(numbers.size() == 0) return 0; int start = 0; int end = numbers.size() - 1; int middle = numbers.size() >> 1; int index = partition(numbers, start, end); while(index != middle) { if(index > middle) { end = index - 1; index = partition(numbers, start, end); } else { start = index + 1; index = partition(numbers, start, end); } }//while int result = numbers[middle]; if(!checkMoreThanHalf(numbers,result)) { return 0; } return result;} 注意上面的循环的方式，感觉比递归的方式更好。但是通过中位数找到的数字可能不是正确的答案，最后要验证一下，这个数字是不是出现的次数多于数组大小的一半。
bool checkMoreThanHalf(vector &numbers, int result){ int times = 0; for(int i = 0; i < numbers.size(); i++) { if(numbers[i] == result) { times++; } }//for if(times * 2 > numbers.size()) { return true; } return false;} 注意上面的函数的返回值：正确的情况下，返回查找到的数据，错误的时候，返回错误码0。
不管怎么弄，上面的算法的实现都是基于划分算法来实现的，其实除了这种方法，还可以有其他的解决方案：
设置两个变量，一个变量用于保存目前出现次数最多的那个数字，另一变量用来记录出现的次数。随着不断的遍历，每遍历一个数，如果和前面保存的数字相同，计数器就+1，不相同就-1。如果计数器减到0，就代表之前存的数已经被淹没掉了，这是要重新记录新的数字，同时置计数变量为1。既然结果数字多于数组个数的一半，那么最后记录中留下的肯定是这个结果数字。但是要注意，原数组中可能本来就没有多于一半的这样的数字，但是最后还是会有一个结果的，所以要最后校验一次。如果发现错误的话，及时的返回错误码0。
int MoreThanHalfNum(vector numbers){ int times = 1; int result = numbers[0]; for(int i = 1; i < numbers.size(); i++) { if(numbers[i] == result) { times++; } else { times--; if(times == 0) { result = numbers[i]; times = 1; } }//else }//for if(!checkMoreThanHalf(numbers, result)) { return 0; } return result;} 对于查找数组中出现次数多于一半的数字，有这两种方法，他们的时间复杂度都是O(n)，但是注意第一种改变了原来的数组，但是第二种没有改变原数组，是一种很好的方法。
获取数组中的最小的K个数
这个题目第一次看到可能会想到先排序，然后就可以很简单的获得最小的k个数了，但是排序的时间复杂度是O(nlogn)，这可能达不到算法时间复杂度的要求，所以又想到了划分。类似前面那个出现次数大于数组个数一半的题目，只要划分能够定位到k-1那个元素。那么[0...k-1]的这些数字就是最小的k个数字。
vector GetKLeastNumbers(vector input, int k){ vector result; if(input.size() == 0 || k <= 0 || k > input.size()) return result; int start = 0; int end = input.size() - 1; int index = partition(input, start, end); while(index != k - 1) { if(index > k -1) { end = index - 1; index = partition(input, start, end); } else { start = index + 1; index = partition(input, start, end); } }//while for(int i = 0; i < k; i++) { result.push_back(input[i]); } return result;} 但是这个算法会改变原来的数组，所以如果要求不改变原来的数组，得想另外的办法。
最小K个数的另一种解决的办法
我们可以另外建立一个容器，在这个容器中存储最小的K个数字。一次遍历原始的数字，如果这时K的容器数组没有满，直接把这个原始数据放到容器中，如果容器已经满了，则比较原始数组的值和容器中最大值，如果原始的数字小，则替换容器中的最大值。否则忽略这个原始的数据，继续向后遍历。
因此在容器满了之后要做下面3件事：
在K的容器中，找到最大值；可能会删除这个最大值；可能会插入一个新的值。
如果用一个二叉树完成上面的3个操作，时间复杂度就能够控制在O(logk)，这样的话整个算法的时间复杂度控制在O(nlogk)。由于每次都是从容器中找到最大值，所以很容易考虑到最大堆，这样的话就可以在O(1)的时间找到容器的最大值，但是删除和插入的时间复杂度是O(logk)。
对于二叉树，可以选用set或者multiset来代替，因为这两个东西都是基于红黑树实现的，红黑树的查找、删除、插入的时间复杂度都是O(logk)。
typedef multiset