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;
}