Chapter3: 更好的查找与排序算法
6. 最快效率求出乱序数组中第k小的数
题目
以尽量高的效率求一个乱序数组中第k小的元素
算法
算法1
用快排先将数组排序，然后直接找第k个元素，时间复杂度为O(nlgn)
算法2
思路
用分区查找的思想，同样有点排序的感觉，毕竟分区就是将小于主元的元素放左边，大于主元的元素放右边。
与排序完再查找不同的是：
- 这个思路不用将所有元素排序完毕,找到指定元素就停止。
- 排序的分区每次递归将数组分为两部分，两部分都需要分别递归进行分区；而这个思路每次确定元素在左数组还是右数组后，只需要继续对其中一个进行分区，另一个不用
对于一次递归调用来说：
首先只用快排的分区函数：选取一个主元，将比主元小的元素放在左边，比主元大的元素放在右边
-
比较输入k和主元的位置(注意和下标的转换，
nowQ=q-begin+1即为主元在当前划分数组中是第几个元素)- 如果输入k在主元之前，即在数组的左部分，则下一次递归调用时，k的相对位置不变，传参到直接传k即可
- 如果输入k在主元之后，即在数组的右部分，则下一次递归调用时，k的相对位置发现变化，
k = k-nowQ即k在当前划分数组中的位置
比如原来数组10个元素，假设主元为第4个元素，如果位置(不是下标)k为3，则下次划分为前5个元素，它的位置还是3；
如果k为6，则下次划分为的数组为第5-10个元素，它的位置为6-4=2,即第2个位置
时间复杂度分析
最好情况
每次主元的选取都选中整个数组的中值，由于每次分区后只在原来的一半进行查找，所以如果找到最后才找到的话(即待查位置的元素每次都不是主元)，那时间复杂度为O(lgn)
最差情况
如果每次主元都选中边界前一个的话(左边n-1个元素，右边1个),如果找到最后才找到的话(即待查位置的元素每次都不是主元)，那要进行n(1+n)/2 次运算，时间复杂度为O(n^2)
平均情况
三点分区法选取的中值比较合理，如果找到最后才找到的话(即待查位置的元素每次都不是主元)，时间复杂度也是O(lgn)
代码
int selectK(int* arr,int begin, int end,int k){
int q = partition2(arr,begin,end);//主元的下标
int nowQ=q-begin+1;//nowK:主元在当前的数组划分中是第几个元素(注意不是下标)
if(nowQ<k)//当前主元位置小于k,即k在主元右侧
return selectK(arr,q+1,end,k-nowQ);//在右数组中k新的相对位置下标(代入nowQ的值发现等价与k+begin-(q+1))//即新的k的下标
else if(nowQ>k)
return selectK(arr,begin,q-1,k);//k在当前数组划分的左半部分，位置还是ke
else
return arr[q];//索引元素值的时候又得用回下标q了
}
其中的分区函数要用到之前快排的分区函数，这里用双向扫描分区法，主元的选取采用3点中值法
/*快速排序-双向扫描分区分区法
功能：选取一个主元，将小于主元的数放数组左边，大于主元的数放右边
//三点中值法确定主元
*/
int partition2(int* arr,int begin,int end){
//int pivot=arr[begin];
int pivot;//三点中值法确定主元
int mid = begin+((end-begin)>>1);
/*判断这3个数哪个是中位数，并将中位数与第一个数交换*/
if(arr[begin]>=arr[end]&&arr[begin]<=arr[mid]){
pivot=arr[begin];
}
else if(arr[begin]<=arr[end]&&arr[begin>=arr[mid]]){
pivot=arr[begin];
}
else if(arr[begin]<=arr[end]&&arr[begin]<=arr[mid]){
if(arr[end]<=arr[mid]){
pivot=arr[end];
int tmp=arr[begin];//交换值
arr[begin]=arr[end];
arr[end]=tmp;
}
else{
pivot=arr[mid];
int tmp=arr[begin];
arr[begin]=arr[mid];
arr[mid]=tmp;
}
}
else if(arr[begin]>=arr[end]&&arr[begin]>=arr[mid]){
if(arr[end]<=arr[mid]){
pivot=arr[mid];
int tmp=arr[begin];
arr[begin]=arr[mid];
arr[mid]=tmp;
}
else{
pivot=arr[end];
int tmp=arr[begin];
arr[begin]=arr[end];
arr[end]=tmp;
}
}
int left=begin+1;
int right=end;
while(left<=right){
while(left<=right&&arr[left]<=pivot)//因为left在变化所以这里也要有left<=right的判断条件
left++;
while(left<=right&&arr[right]>pivot)
right--;
if(left<right){//如果left==right就没有交换的必要了
int tmp=arr[left];
arr[left]=arr[right];
arr[right]=tmp;
}
}
int tmp=arr[begin];//交换主元到右指针的位置
arr[begin]=arr[right];
arr[right]=tmp;
return right;
}
