利用快排查询无序数组第k位大的数

以你之姓@ 2023-10-05 13:34 44阅读 0赞

由于快速排序的partion函数返回值是基准值最终的位置，由此可以启发得出当这个位置刚好是第k位时，直接输出它下标对应的值，如果这个位置大于第k位时，则向该基准位置的左边递归；如果这个位置小于第k位时，则向该基准位置的右边递归；以上就是查找第k位的基本思想。

这个算法时间复杂度是o(n),这时候有的人会说快排的时间复杂度是o(nlogn),为什么这个是o(n)呢？因为快排分别是对基准值两边进行递归操作的，然后再合并，合并操作时间复杂度o(1),每趟进行了n次交换，整个快速排序进行了logn趟，所以快速排序的时间复杂度是o(nlogn)；而这个查找问题，它只需要每次在一边查找，确定枢纽元的相对位置（在K的左边或者右边）之后不用再对剩下的一半进行处理。也就是说第二次插入的算法复杂度不再是O(N)而是O(N/2)，它的时间复杂度求解过程是1+1/2+1/4+........ < 2\[1-（1/2）^n\]<2，换句话说就是一共是O(2N)的算法复杂度也就是O(N)的算法复杂度。

源码（python）

def partion(arr,left,right):
        front=left
        rear=right
        temp=arr[left]
        while(rear>front):
            while(rear>front) and(arr[rear]>temp):
                rear-=1
            arr[front]=arr[rear]
            while(rear>front) and(arr[front]<=temp):
                front+=1
            arr[rear]=arr[front]
        arr[front]=temp
        return front
    
    def main(arr,left,right,k):
       if(left==right):  #当只有一个数时
            return arr[left]
       if(k-left+1>right):  #当给出的k超过最大的数组时
            return -1
       t=partion(arr,left,right)  #返回的是基准值在数组的位置，需要加1才等于第几位
       if (t+1==k):  #因为数组是从0开始，所以需要t+1才能与k值判断
            return arr[t]
       elif(t+1>k):  #当t+1大于k时，说明第k位在基准值的左边
           return main(arr,left,t-1,k)
       else:        #当t+1小于k时，说明第k位在基准值的右边
            return main(arr,t+1,right,k)
    
    arr=[1,3,4,2,6,5,8,7,9,10]
    print(main(arr,0,9,6))

c语言源码：

#include<stdio.h>
    int p;
    int t;
    void swap(int a[],int m,int n){
    	int temp;
    	temp=a[m];
    	a[m]=a[n];
    	a[n]=temp;
    }
    int  partion(int a[],int left,int right){
        int k=left;
    	int s=a[k];      //将中间的这个数和第一个数交换 
       
    	while(left<right){
    		while(left<right&&a[right]>s){  // 从右向左找第一个小于x的数  
                  right--;
    		}
    			swap(a,right,left);
    		
    		while(left<right&&a[left]<=s){  // 从左向右找第一个大于等于x的数  
                 left++;
    		}
    			swap(a,left,right);
    	}
    	    a[left]=s;          //一趟划分结束，left为轴心
    	  return left;
    }
    int quick_find(int a[],int left,int right,int k){
    	if(k<0 && k-left+1>right){
    	   return -1;
    	}
    	if(left==right) return a[left];
    	int t=partion(a,left,right);
    	
    	if(t+1==k)  return a[t];   //基准值的位置刚好是第k位
    	else if(t+1>k)  //向基准值左边递归查找
    		return quick_find(a,left,t-1,k);
    	else   //向基准值右边递归查找
    		return quick_find(a,t+1,right,k);
    }
    
    
    
    int main(){
    	int a[]={1,2,5,7,4,3,10,6,9,8};
    	int u=9;
    	int k=5;
       printf("%d\n",quick_find(a,0,u,k));
    	
    	return 0;
    }