算法导论 中值与顺序统计

时间复杂度大于n小于n*log n

源码走起

--------------------------------------------------------------------------------------------------------------------

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define N 20
#define K 100
void happen_rand(int* p, int n);//生成随机数
void Printf(int* p, int n);//打印
int random(int* p, int left, int right, int centre);//随机选择
int quicksort(int* p, int left, int right);//快速排序

int main()
{
    int array[N] = { 0 };
    int i = 11;//scanf("%d",&i);
    happen_rand(array, N);
    random(array, 0, N - 1, i);
    Printf(array, N);
 
    return 0;
}

void Printf(int* p, int n) {
    for (int i = 0; i < n; i++) {
        printf("%d\n", p[i]);
    }
}

void happen_rand(int* p, int n)
{
    
    for (int i = 0; i < N; i++) {
        p[i] = rand() % K;

    }
}

int random(int* p, int left, int right, int i) {
    if (left == right) return p[left];
    int centre= quicksort(p, left, right);
    int k = centre - left + 1;//k的含义 该数组的第k个元素，而不是总数组的第k个元素，这段码，愚笨的我我分析了一个小时
    if (i == centre) return p[centre];
    if (i < k) return random(p, left, centre - 1, i);
    if(i>k)  return random(p, centre+1, right, i-k);//i-k代表在在该数组中的第几位，i-(centre+1)是错的，请自行脑补，提示；递归的时候要用相对于本次递归的变量



}

int quicksort(int *p, int left, int right) {//快速排序详见前期博客
    int benchmark = p[left];
    int l = left, r = right;
    while (l < r) {
        while (l < r && p[r] >= benchmark) { r--; }
        p[l] = p[r];
        while (l < r && p[l] <= benchmark) { l++; }
        p[r] = p[l];
    }
    p[l] = benchmark;
    return l;

}