2025年【排序进阶】快速选择算法

科技前沿 • 2025-01-25 23:24 • 阅读 66

大家好，我是讯享网，很高兴认识大家。

一.定义

快速选择算法（Quickselect）是一种在未排序的数组中查找第k小/大元素的算法，时间复杂度为O(n)。它的基本思想是选择一个基准值（pivot），将数组分为两部分，一部分小于等于基准值，一部分大于基准值。然后根据k与基准值的大小关系，选择其中一部分进行递归搜索，直到找到第k小/大元素为止。

快速选择算法和快速排序算法的思路类似，但是快速选择算法只需要对一部分数组进行快速排序，而不需要对整个数组进行排序。因此，快速选择算法的平均时间复杂度为O(n)，最坏时间复杂度为O(n^2)，但是最坏情况出现的概率很小。

快速选择算法的时间复杂度为O(n)，空间复杂度为O(1)

二.基本步骤

选择一个基准值pivot，可以选择数组中的任意一个元素。
将数组分为两部分，一部分小于等于pivot，一部分大于pivot。

讯享网
如果k小于等于左边部分的元素个数，那么继续在左边部分中查找第k小元素；否则，在右边部分中查找第k-left个小元素。
重复步骤2和3，直到找到第k小元素为止。

三.核心代码（注释讲解）

void search(int left,int right) //递归函数，left和right表示当前搜索的区间 { int i=left,j=right,pivot=arr[(left+right)/2]; //取中间值作为基准值 while(i<=j) //当i<=j时进行循环 { while(arr[j]>pivot) //从右往左找到第一个小于等于基准值的数 j--; while(arr[i]<pivot) //从左往右找到第一个大于等于基准值的数 i++; if(i<=j) //如果i<=j，交换arr[i]和arr[j]的值 { swap(arr[i],arr[j]); i++; j--; } } //快排后数组被划分为三块： left<=j<=i<=right if(k<=j) search(left,j); //如果k在左区间，只需要搜左区间 else if(i<=k) search(i,right); //如果k在右区间，只需要搜右区间 else //如果k在中间区间，直接输出arr[j+1]并结束程序 { cout<<arr[j+1]; exit(0); //任务完成，强制结束！ } }

讯享网

四.具体题目

P1923 【深基9.例4】求第 k 小的数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

五.【AC】答案

讯享网#include<iostream> #include<stdio.h> using namespace std; int arr[],k; //定义全局变量，存储输入的数组和要查找的第k小数 inline long long read(){ //快速读入函数 char cc=getchar(); long long f=1,ans=0; while(cc<'0' ||cc>'9'){ if(cc=='-') f=-1; cc=getchar(); } while(cc>='0' && cc<='9'){ ans=ans*10+ (cc-'0'); //注意这里是ans*10+... cc=getchar(); } return f*ans; } void search(int left,int right) //递归函数，left和right表示当前搜索的区间 { int i=left,j=right,pivot=arr[(left+right)/2]; //取中间值作为基准值 while(i<=j) //当i<=j时进行循环 { while(arr[j]>pivot) //从右往左找到第一个小于等于基准值的数 j--; while(arr[i]<pivot) //从左往右找到第一个大于等于基准值的数 i++; if(i<=j) //如果i<=j，交换arr[i]和arr[j]的值 { swap(arr[i],arr[j]); i++; j--; } } //快排后数组被划分为三块： left<=j<=i<=right if(k<=j) search(left,j); //如果k在左区间，只需要搜左区间 else if(i<=k) search(i,right); //如果k在右区间，只需要搜右区间 else //如果k在中间区间，直接输出arr[j+1]并结束程序 { cout<<arr[j+1]; exit(0); //任务完成，强制结束！ } } int main() { int n; n=read(); //读入数组长度 k=read(); //读入要查找的第k小数 for(int i=0;i<n;i++) //循环读入数组元素 arr[i]=read(); search(0,n-1); //从整个数组的区间开始搜索 return 0; }