问题描述：无序找第k小的数？
1、解法一
先排好序，再找第k小个数；返回A[k-1]；此解法的时间复杂度为：O(nlogn)；
2、解法二
情况一：k = 1 和 k = n 就是找数组的最小值和最大值；
情况二：找出中位数
3、找中位数(随机选择算法)
利用快速排序的原理，一轮排序，有2种情况：
if i = k-1；返回a[i]；
if i != k-1；左边/右边递归查找，时间复杂度为：O(n)；
具体思想：
分析：在大多数情况下的时间复杂度是：O(n)；但是最坏情况，完全顺序下找第k = n-1大数，此时的时间复杂度是：O(n^2)；
4、无序找第k小值
快排的升序实现思想，在加上递归查找；
(1)、代码实现
计算
安全
数据库
网络和加速
企业服务
#include<stdio.h>
void findKSmall(int *a, int start, int end, int key);
void findKSmall(int *a, int start, int end, int key){
int i = start;
int j = end;
int tmp = a[i];
//快排中的升序
while(i < j){
while(i < j && a[j] > tmp){
j--;
}
if(i < j){
a[i++] = a[j];
}
while(i < j && a[i] < tmp){
i++;
}
if(i < j){
a[j--] = a[i];
}
}
a[i] = tmp;
if(key-1 < i){
findKSmall(a, 0, i-1, key);
}else if(key-1 > i){
findKSmall(a, i+1, end, key);
}else{
return;
}
}
void main(void){
int a[] = {8, 4, 6, 9, 2, 3, 7, 9, 11, 10};
int count = sizeof(a)/sizeof(int);
int k;
int i;
printf("请输入要查找的第k小的数：");
scanf("%d", &k);
findKSmall(a, 0, count-1, k);
for(i = 0; i < count; i++){
printf("%d ", a[i]);
}
printf("\n%d\n", a[k-1]);
}结果截图
5、无序找第k大值
快排的降序实现思想，在加上递归查找；
(1)、代码实现
#include<stdio.h>
void findKBigger(int *a, int start, int end, int key);
void findKBigger(int *a, int start, int end, int key){
int i = start;
int j = end;
int tmp = a[i];
//快排中的降序
while(i < j){
while(i < j && a[j] < tmp){
j--;
}
if(i < j){
a[i++] = a[j];
}
while(i < j && a[i] > tmp){
i++;
}
if(i < j){
a[j--] = a[i];
}
}
a[i] = tmp;
if(key-1 < i){
findKBigger(a, 0, i-1, key);
}else if(key-1 > i){
findKBigger(a, i+1, end, key);
}else{
return;
}
}
void main(void){
int a[] = {8, 4, 6, 9, 2, 3, 7, 9, 11, 10};
int count = sizeof(a)/sizeof(int);
int k;
int i;
printf("请输入要查找的第k大的数：");
scanf("%d", &k);
findKBigger(a, 0, count-1, k);
for(i = 0; i < count; i++){
printf("%d ", a[i]);
}
printf("\n%d\n", a[k-1]);
}(2)、结果截图
6、线性算法
(1)、划分为5个一组的元素，在找出每一组的中值(对这5个数进行排序，找出中值)，时间复杂度：O(n)
(2)、用递归去找这些中值中的那一个中值(中值中的中值)；
(3)、此时用这个最中值的下标和k作比较，之后和上面的随机选择算法一样！！！
具体模型如下：
算法分析
找中值和第k小数时间复杂度均为：O(n)；比较好的解决了上述最坏时间复杂度为O(n^2)的情况；
3个元素一组的话，结果不成立；
5是这个算法能成功的最小数字，7个元素为一组算法也能成立，但是性能不会有所提高；
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
