配列TOP Kアルゴリズムについて(スナップおよび最小スタック方式Cコード)

TOP Kは所与の集合の最大のK個の要素を返し,この集合は10億,可能性が高いため,アルゴリズムに対する要求が高い.以下は私のまとめです.
一、迅速な順序付けの分治アルゴリズム思想を採用して解く:
クイックソートの考え方は、1つのフラグポイントを使用して配列を2つの部分に分け、そのポイントより小さいデータをそのポイントの左側に移動し、そのポイントより大きいデータをそのポイントの右側に移動し、再帰し、最後に秩序に達することです.同様に,この考えを用いて配列のTOP Kを求めることもできる.また、最初の要素の左右のフラグを使用して、その点より小さい要素を左側に移動し、その点より大きい要素を右側に移動し、最初のpartition後に3つの場合があります.
1、標識点の右側のデータはちょうどK-1で、それでは標識点をプラスして要求するTOP Kの要素です
2、フラグポイント右側のデータ個数NがK-1より小さい場合、フラグポイント左側の集合の中でTOP(K-N)を探す必要があり、再帰的に実現できる
3、フラグポイント右側のデータ個数NがK-1より大きい場合、フラグポイント右側の集合にTOP K個の要素を必要とし、再帰的に実現する
コードは次のとおりです.

#include <stdio.h>
#include <unistd.h>

void getRand(int* data, int length) {
    int i;
    srand((unsigned int) getpid());
    for (i = 0; i < length; i++) {
        data[i] = rand() % 1000;
    }
    //print the array
    printf("generate the array using rand:
");
    for (i = 0; i < length; i++) {
        printf("%d ", data[i]);
    }
    printf("
");
}

void partition(int arr[], int low, int high, int *pos){
        int key = arr[low];
        int i = low, j = high;
        while(i < j){
                while(i < j && arr[j] > key) j--;
                if(i < j){
                        arr[i++] = arr[j];
                }
                while(i < j && arr[i] < key) i++;
                if(i < j){
                        arr[j--] = arr[i];
                }
                //arr[i] = key;
        }
        arr[i] = key;
        *pos = i;
}

int topK(int arr[], int low, int high, int k){
        int pos =0;
        partition(arr, low, high, &pos);
        int num = high - pos + 1;
        int index = -1;
        if(num == k){
                index = pos;
        }else if(num > k){
                index = topK(arr, pos + 1, high, k);
        }else{
                index =  topK(arr, low, pos -1, k - num);
        }
        return index;
}

int main(){
        int arr[10] = {0};
        getRand(arr, 10);
        int pos;
        pos = topK(arr, 0, 9, 5);
        for(;pos < 10;pos++){
                printf("%d\t", arr[pos]);
        }
        printf("
");
}

このアルゴリズムの欠点は,データに対して頻繁な移動操作が必要であり,データ量が大きい場合はファイル形式で分治計算を行う必要があることである.
二、最小スタックを用いてTOP K要素を取得するのは良い方法である.
なぜ最小スタックを使用するかというと、最小スタックトップは最小の要素であり、スタックトップより大きい要素だけがスタックに参加し、スタックをadjustするからです.この方式はK個の要素の最小スタックを維持するだけである.

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

void print(int arr[], int size){
        int i = 0;
        for(; i < size;i++){
                printf("%d\t", arr[i]);
        }
}
//       
void add(int arr[],int size,int num){
        if(num > arr[0]){
                arr[0] = num;
                //   
                int i = 0;
                for(;i < size -1 && num > arr[i+1];i++){
                        arr[i] = arr[i+1];
                }
                arr[i] = num;
        }
}
//      （     1）
void sink(int arr[], int size, int num){
        if(num > arr[1]){
                arr[1] = num;
                int i = 1;
                while(2 * i <= size){
                        int j = 2 * i;
                        if(j < size && arr[j + 1] < arr[j]) j++;
                        if(arr[i] > arr[j]){
                                int tmp = arr[i];
                                arr[i] = arr[j];
                                arr[j] = tmp;
                                i = j;
                        }else{
                                break;
                        }
                }
        }
}

void getRand(int* data, int length) {
    int i;
    srand((unsigned int) getpid());
    for (i = 0; i < length; i++) {
        data[i] = rand() % 1000;
    }
    //print the array
    printf("generate the array using rand:
");
    for (i = 0; i < length; i++) {
        printf("%d ", data[i]);
    }
    printf("
");
}

int main(int argc, char *argv[]){
        int arr[11] = {0};
        int heap[10] = {0};
        int heap2[11] = {0};
        getRand(arr, 11);
        int i;
        for(;i< 11;i++){
                add(heap, 10, arr[i]);
                sink(heap2, 10, arr[i]);

        }
        print(heap, 10);
        int j = 1;
        for(; j < 11;j++){
                printf("%d\t", heap2[j]);
        }
}