1. TopK问题

在一堆数据选出符合条件的K个元素，如最大/小的k个元素等

描述：从arr[1, n]这n个数中，找出最大的k个数，这就是经典的TopK问题。
举例：从arr[1, 12]={5,3,7,1,8,2,9,4,7,2,6,6} 这n=12个数中，找出最大的k=5个。

排序（全排序）

sort(arr, 1, n); return arr[1, k];

时间复杂度： //快排 空间复杂度：
算法分析

✅无需额外空间 ❌全部排序 < 局部排序 ❌海量数据gg

局部排序（TopK排序）

冒泡排序取部分，每冒泡一次获取其中最大值，仅需冒泡k次（全排序需要冒泡n次）

for ( i=1 to k ) { bubble_find_max(arr, i); } return arr[1, k];

时间复杂度： 空间复杂度：
算法分析

✅节省非topK元素的计算资源

堆（TopK不排序）

用前k个元素创建小顶堆（堆顶为k个最大元素里的最小值），若非topk元素比堆顶大，入堆；否则继续比较
大顶堆——最小K；小顶堆——最大K

heap[k] = make_heap(arr[1, k]); for ( i=k+1 to n) { adjust_heap(heap[k], arr[i]) } return heap[k];

时间复杂度： 空间复杂度：
分析

最坏情况：每次插入元素都需调整堆，即 ✅可处理海量数据

随机选择算法（求第k个元素）

背景
快速排序：分治法，

void quick_sort(int[]arr, int low, inthigh){ if(low== high) return; int i = partition(arr, low, high); // 核心：分成两部分，一般以第一个元素为分隔， quick_sort(arr, low, i-1); quick_sort(arr, i+1, high); }

分治法（Divide&Conquer），把一个大的问题，转化为若干个子问题（Divide），每个子问题“都”解决，大的问题便随之解决（Conquer）。这里的关键词是“都”。从伪代码里可以看到，快速排序递归时，先通过partition把数组分隔为两个部分，两个部分“都”要再次递归。
减治法（Reduce&Conquer），把一个大的问题，转化为若干个子问题（Reduce），这些子问题中“只”解决一个，大的问题便随之解决（Conquer）。这里的关键词是“只”。（分治法特例），案例：二分查找
二分查找：减治法，

int BS(int[]arr, int low, inthigh, int target){ if(low> high) return -1; mid= (low+high)/2; if(arr[mid]== target) return mid; if(arr[mid]> target) return BS(arr, low, mid-1, target); else return BS(arr, mid+1, high, target); }

问题变成了arr[1, n]中找到第k大的数。
再回过头来看看第一次partition，划分之后：
i = partition(arr, 1, n);
如果i大于k，则说明arr[i]左边的元素都大于k，于是只递归arr[1, i-1]里第k大的元素即可；
如果i小于k，则说明说明第k大的元素在arr[i]的右边，于是只递归arr[i+1, n]里第k-i大的元素即可；

int RS(arr, low, high, k){ // randomized_select

if(low== high) return arr[low];

i= partition(arr, low, high);

temp= i-low; //数组前半部分元素个数

if(temp>=k)

  return RS(arr, low, i-1, k); //求前半部分第k大

else

  return RS(arr, i+1, high, k-i); //求后半部分第k-i大

}

时间复杂度： 空间复杂度：
分析

❎海量数据无法一次加载内存 ❎修改输入数组

随机选择算法可解决topK问题、中位数
再次强调一下：

• 分治法，大问题分解为小问题，小问题都要递归各个分支，例如：快速排序
  
• 减治法，大问题分解为小问题，小问题只要递归一个分支，例如：二分查找，随机选择

  分布式TopK

  海量数据存放多台机器，每台机器并行计算各自TopK，再汇总得到总的TopK
  思想 数据分片