从数组中找到第k小元素
程序员文章站
2024-03-15 22:17:54
...
#include <stdio.h>
#include <stdlib.h>
int Element_k( int data[] , int key ,int low , int high ){
//基于快排的思想,如果pivot=data[low], low=k 那么pivot就是第k小的元素
int pivot = data[low] ;
int low_temp = low ;
int high_temp = high ; //使用temp标记当前位置,以便找到递归的头和尾
while( low < high ){
while(low < high && pivot <= data[high]) --high;
data[low] = data[high] ;
while(low < high && pivot >= data[low]) ++low;
data[high] = data[low] ;
}
data[low] = pivot ;
//以上是快速排序的划分
if( low==key ) return data[low];
else if( low>key )
return Element_k( data , key , low_temp , low-1 );
else //第k小的元素在pivot的左边,那么递归就变成查找第k-low小的元素
return Element_k( data , key-low , low+1 , high_temp );
}
int main(){
int data[50] , n , key ;
printf("输入节点个数:\n");
scanf("%d",&n);
printf("输入数组:\n");
for(int i = 0 ; i < n ; i++){
scanf("%d",&data[i]);
}
printf("查找第k小的元素:\n");
scanf("%d" , &key);
printf("%d",Element_k( data , key , 0 , n-1 ));
}
上一篇: 如何在10亿个整数中找出前1000个最大的数(TopN算法)
下一篇: Unity 射线碰撞检测