划分是求Kth、快速排序等的基础。

目标：一个数组array，给定一个pivotIndex，要求将array[pivotIndex]的对象至于storeIndex位置，使得[left,storeIndex)的元素都小于array[pivotIndex]，而使得大于[storeIndex,right]的元素都大于等于array[pivotIndex]。

算法步骤：
1、交换array[pivotIndex]和array[right]，记前者为pivot
2、用store表示pivotIndex“潜在”可能的存储位置，初始为left。
3、i从left到right依次扫描，每当遇到比pivot小的元素，则放入store,并store++。
4、重复上述2-3直到i扫描完最右侧
5、交换array[store]和array[right]（切忌忘记right里存得可是pivot）。

#include <stdio.h>

typedef int TYPE;

//Compare function
int cmp(TYPE a, TYPE b)
{
	return a - b;
}

//Partion, devide the arr into 2 parts
//arr[pivotIndex] store in arr[store]
//And:
//(1)All elems in [left,store) < arr[store]
//(2)All elems in [store,right] > arr[store]
int partition(TYPE* arr, int left, int right, int pivotIndex, int (*cmp)(TYPE, TYPE))
{
	TYPE pivot, tmp;
	int i, store;

	//First, swap the arr[pivotIndex] and arr[right]
	pivot = arr[pivotIndex];
	arr[pivotIndex] = arr[right];
	arr[right] = pivot;

	//Scan from left to right
	i = store = left;
	while(i<right)
	{
		if(cmp(arr[i],pivot)<=0)
		{
			tmp = arr[store];
			arr[store] = arr[i];
			arr[i] = tmp;
			store++;
		}
		i++;
	}

	//Final, swap the arr[right] and arr[store]
	arr[right] = arr[store];
	arr[store] = pivot;
	return store;
}

int main()
{
	int arr[16] = {15, 9, 8, 1, 4, 11, 7, 12, 13, 6, 5, 3, 16, 2, 10, 14};
	int len = sizeof(arr)/sizeof(TYPE);
	int storeIndex;

	//partition
	storeIndex = partition(arr, 0, len - 1, 9, cmp );
	printf("storeIndex\t%d\n", storeIndex);

	//print
	int i;
	for(i=0; i<len; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}