partition一般用于快速排序中，也可用于求无序数组的第k大(中位数)等问题。partition的思想是根据一个哨兵(pivot)将数组分为大于(等于)或小于(等于)pivotde的两部分。
在partition的过程中我遇到了两个比较困惑的问题：
- 如何选择pivot？
- 如何划分数组
pivot与时间复杂度
快排的时间复杂度与pivot的选取有很大的关系。
最坏时间复杂度为$O(n^2)$ ,当待排序的序列为正序或逆序排列时，且每次划分只得到一个比上一次划分少一个记录的子序列,需要执行n‐1次递归调用，且第i次划分需要经过n‐i次关键字的比较才能找到第i个记录，也就是枢轴的位置，因此比较次数为$\sum_{i=1}^{n-1}(n-i)=(n-1)n/2$,即$O(n^2)$
最好的时间复杂度，当哨兵将数组均分为两部分时：
$$ T(n) = 2T(n/2)+n $$
$$ T(n) = 2(2T(n/4)+n/2)+n = 4T(n/4) +2n $$
$$ T(n) = 4(2T(n/8)+n/4)+2n = 8T(n/8) +3n $$
$$ 且T(1)=0 $$
$$ T(n) = nT(1) + (logn)n = nlogn $$
平均时间复杂度(不会证，参考算法导论)：
选择开头(结尾)的元素作为pivot
public int partition1(int[] nums,int l,int r){
int pivot = nums[l];
while(l<r){
while(l<r&&nums[r]>=pivot) r--; //必须先从r开始比较
nums[l] = nums[r];
while(l<r&&nums[l]<pivot) l++;
nums[r] = nums[l];
}
nums[l] = pivot; // 赋值
return l;
}
//稍微换一种写法，赋值->交换，则每次都是和哨兵交换。
public int partition2(int[] nums,int l,int r){
int pivot = nums[l];
while(l<r){
while(l<r&&nums[r]>=pivot) r--; //必须先从r开始比较
swap(nums,l,r);
while(l<r&&nums[l]<pivot) l++;
swap(nums,l,r);
}
//此处相比于partition1少了赋值 nums[l] = pivot;
return l;
}
//leetcode讨论区中看到的一种写法
public int partition3(int[] nums,int l,int r){
int pivot = nums[r];
int L = l;
for(int i=l;i<r;i++){ //注意是r不用比较
if(nums[i]<pivot){
swap(nums,L++,i);
}
}
swap(nums,L,r);
return l;
}
//排序：
int p = partition(nums,l,r);
sort(l,p-1);
sort(p+1,r);
partition1选择开头作为哨兵，则开头的位置空出来了（所以开头可以本身的数不会丢失的情况下放置小于哨兵的数，因为pivot记录了开头的数）,把从r开始的第一个小于pivot的数放在开头的位置，则该位置又空出来了，如此反复，最后会空出来一个位置，用来放置哨兵。
partition2把赋值改为交换操作，哨兵的值在交换中不会被覆盖，所以最后不用再赋值了（表达能力堪忧，具体参考这篇博文中的图https://www.cnblogs.com/fly-code-jia/articles/7702983.html）
随机选择pivot
每次选择开头(结尾)作为哨兵，可能会出现最坏的时间复杂度的情况，所以一般会随机选择一个哨兵：
//加上随机操作
public int partition(int[] nums,int l,int r){
//随机选择一个元素与开头交换
int index = rand.nextInt(r - l + 1) + l;
swap(nums,l,index);
//或打乱数组：shuffle(nums);再选择开头
int pivot = nums[l];
while(l<r){
while(l<r&&nums[r]>=pivot) r--; //必须先从r开始比较
nums[l] = nums[r];
while(l<r&&nums[l]<pivot) l++;
nums[r] = nums[l];
}
nums[l] = pivot; // 赋值
return l;
}
以上的几种partition写法相当于每次都是移动哨兵，最后将数组划分为：
[[小于pivot] ,pivot, [大于等于pivot]] 三部分
另外还有一类常见的partition写法，每次将数组划分为:
[[小于等于pivot]， [大于等于pivot]] 两部分
public void partition(int[] nums,int l,int r){
int index = rand.nextInt(end - start + 1) + start;
int pivot = nums[index];
int L = l, R = r;
while(L < R){
while(L < R && nums[L] < pivot){//此处不能为<=的原因是：为了避免当哨兵为最大(小)时，所有元素都分到一个数组的情况
L++;
}
while(L < R && nums[R] > pivot){
R--;
}
if(L < R){
int temp = nums[L];
nums[L] = nums[R];
nums[R] = temp;
L++;
R--;
}
}
/*
C只是分为两个部分，再对两个部分递归，不会把某个数去掉，区间可能不会减小。标准快排递归是p+1,p-1，区间一定会减小。此处while循环其实就是保证区间减小。
*/
while(L >= start && nums[L] >= pivot){
L--;
}
while(R <= end && nums[R] <= pivot){
R++;
}
quickSort(nums, start, L);
quickSort(nums, R, end);
}