找出N个无序数中第K大的数

时间:2021-09-27 19:02:24

使用类似快速排序,执行一次快速排序后,每次只选择一部分继续执行快速排序,直到找到第K个大元素为止,此时这个元素在数组位置后面的元素即所求

时间复杂度:

       1、若随机选取枢纽,线性期望时间O(N)

       2、若选取数组的“中位数的中位数”作为枢纽,最坏情况下的时间复杂度O(N)

      

利用快速排序的思想,从数组S中随机找出一个元素X,把数组分为两部分Sa和Sb。Sa中的元素大于等于X,Sb中元素小于X。这时有两种情况:

            1. Sa中元素的个数小于k,则Sb中的第k-|Sa|个元素即为第k大数;
           2. Sa中元素的个数大于等于k,则返回Sa中的第k大数。
 
 
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#define    N 10

int Partition(int *array, int low, int high) {
    int temp = array[low];
    while (low != high) {
        while (low<high && array[high]>=temp) high--;
        array[low] = array[high];
        while (low<high && array[low]<=temp) low++;
        array[high] = array[low];
    }
    array[low] = temp;
    return low;
}

void findk(int k, int *array, int low, int high) {
    int pos;
    pos = Partition(array, low, high);
    if (pos == k - 1) printf("第%d大的数是%d\n", k, array[k - 1]);
    else if (pos > k - 1) {  //左边堆元素个数Sa大于k,则在左边堆中找第k大的数
        findk(k, array, low, pos - 1);
    }
    else {  //左边堆元素个数Sa小于k,则在右边堆中找第 k -Sa个元素
        findk(k - pos, array, pos + 1, high);
    }
}

void printArray(int *a) {
    for (int i = 0;i < N;++i) {
        printf("%3d", a[i]);
    }
    printf("\n");
}

int main() {
    int *a = (int*)calloc(N, sizeof(int));
    srand(time(NULL));
    for (int i = 0;i < N;++i) {
        a[i] = rand() % 100;
    }
    printArray(a);
    findk(5, a, 0, N - 1);
    return 0;
}