高效查找Top K：基于直接插入排序的算法解析与C代码实现

在数据处理和分析中，我们经常需要从海量数据中找到排名靠前的元素。比如，获取电商平台上销量最高的商品，或者社交媒体上最热门的话题。这类问题都可以抽象为 Top K 问题，即从n个数据中找到最大的K个元素。

本文将介绍一种基于 直接插入排序 的 Top K 算法，该算法适用于 有限空间 和 K远小于n 的场景。

算法步骤

假设我们有一个包含n个整数的数组a，目标是找到其中最大的K个元素，并将结果存储在数组b中。

初始化结果数组: 创建一个大小为K的数组b，用于存放最终的 Top K 数据。2. 复制初始元素: 将数组a中的前K个元素复制到数组b中。3. 对结果数组排序: 对数组b进行插入排序，确保最大的元素位于数组的末尾。4. 遍历剩余元素: 对于数组a中剩余的元素（从第 K+1 个元素开始），依次执行以下操作： - 比较大小: 将当前元素与数组b中最后一个元素（即当前的第K大元素）进行比较。 - 插入元素: - 若当前元素大于数组b的最后一个元素，则将当前元素插入到b中的正确位置，保持b的有序性，并将b中最后一个元素移除，保证b中始终只有K个元素。 - 若当前元素 小于等于 数组b的最后一个元素，则直接跳过，继续处理下一个元素。5. 输出结果: 遍历完数组a后，数组b中存放的就是 Top K 个数据。

C代码实现c#include <stdio.h>

#define K 10 // 设置TopK的大小#define N 100000 // 原始数据的长度

void insertionSort(int* arr, int n) { int i, j, key; for (i = 1; i < n; i++) { key = arr[i]; j = i - 1; while (j >= 0 && arr[j] < key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; }}

void getTopK(int* a, int* b) { // 复制前K个元素到结果数组b for (int i = 0; i < K; i++) { b[i] = a[i]; }

// 对结果数组b进行插入排序    insertionSort(b, K);

// 遍历剩余的元素    for (int i = K; i < N; i++) {        // 当前元素大于最后一个元素，插入到正确的位置        if (a[i] > b[K - 1]) {            int j = K - 2;            while (j >= 0 && a[i] > b[j]) {                b[j + 1] = b[j];                j--;            }            b[j + 1] = a[i];        }    }}

int main() { int a[N] = { /* 原始数据 */ }; int b[K] = { 0 }; // 结果数组

getTopK(a, b);

// 输出TopK结果    printf('Top %d 数据为：', K);    for (int i = 0; i < K; i++) {        printf('%d ', b[i]);    }    printf('

');

return 0;}

时间复杂度分析

直接插入排序算法的时间复杂度为 O(n*K)，其中 n 为原始数据的长度，K 为 Top K 的大小。当 K 远小于 n 时，该算法的时间复杂度接近于 O(n)，可以高效地计算出 Top K 个数据。

总结

本文介绍了一种基于直接插入排序的 Top K 算法，并提供了详细的步骤说明和 C 代码实现。该算法适用于有限空间和 K 远小于 n 的场景。在实际应用中，我们可以根据具体的需求选择合适的 Top K 算法。