欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

从数组中找到第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 ));

}