1.堆排序
以求最大TopN为例，可以建立最大堆，再对将前K个数排出来，关于堆排序的知识可以查看我的这篇博客[排序算法]，求最小TopN也是同样的道理，建立最小堆即可，下面是代码实现
#include <iostream>
//#include <algorithm>
using namespace std;
void swap(int nums[],int i,int j){
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
void heapify(int nums[],int i,int len){
int left=2*i+1;
int right=2*i+2;
int newIndex=i;
if(left<len&&nums[left]>nums[newIndex]){
newIndex=left;
}
if(right<len&&nums[right]>nums[newIndex]){
newIndex=right;
}
if(newIndex!=i){
swap(nums,i,newIndex);
heapify(nums,newIndex,len);
}
}
void buildMaxHeap(int nums[], int len) {
for (int i = len/2-1; i >=0; --i){
heapify(nums,i,len);
}
}
void sort(int nums[],int len){
buildMaxHeap(nums,len);
for (int i = len-1; i >0; --i) {
swap(nums,0,len);
heapify(nums,0,--len);
}
}
int nums[30];
int main() {
srand(time(0));
int len= sizeof(nums)/ sizeof(int);
for (int i = 0; i < len; ++i) {
nums[i]=rand()%30;
}
for (int i = 0; i < len; ++i) {
printf("%d ",nums[i]);
}
printf("\n");
int k=0;
scanf("%d",&k);
sort(nums,len);
for (int i = len-1; i >len-k; --i) {
printf("%d ",nums[i]);
}
return 0;
}
2.比特位图（bitmap）
所谓的Bit-map就是用一个bit位来标记某个元素对应的Value，
而Key即是该元素。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省。我们知道，一般可以直接操控的最小的单位是字节，比如在C/C++中，定义一个类型char，对它进行各种操作。然后很多时候，面对一个很[大数据](https://so.csdn.net/so/search?q=%E5%A4%A7%E6%95%B0%E6%8D%AE&spm=1001.2101.3001.7020
"大数据")量，且我们仅仅希望知道某个数是否存在，我们不妨可以（ 有时候是必须 ）使用Bitmap算法来完成相关操作。适用于无重复的元素集合
#include <iostream>
#include <vector>
//#include <algorithm>
using namespace std;
void swap(int nums[],int i,int j){
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
int arr[20];
int main() {
//需要提前计算元素大小
vector<unsigned int > nums(6);
srand(time(0));
int len=sizeof(arr)/sizeof (unsigned int );
for (int i = 0; i < len; ++i){
arr[i]=rand()%100;
}
for (int i = 0; i < len; ++i){
printf("%d ",arr[i]);
}
printf("\n");
for (int i = 0; i < len; ++i){
int num=arr[i];
int idx=num>>5;
nums[idx]|=1<<(num&31);
}
for (int i = 0; i < nums.size(); ++i){
for (int j = 0; j < 4; ++j){
for (int k = 0; k < 8; ++k){
printf("%d",(1<<(8*j)<<(k))&nums[i]?1:0);
}
printf(" ");
}
printf("\n");
}
return 0;
}
3.随机选择
借助于快排中的分治法，不熟悉的小伙伴可以看上面我分享的博客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大的元素即可；
#include <iostream>
//#include <algorithm>
using namespace std;
void swap(int nums[],int i,int j){
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
int partition(int nums[],int leftBound,int rightBound){
int left=leftBound;
int right=rightBound-1;
int pivot=nums[rightBound];
while (left<=right){
while (left<=right&&nums[left]<=pivot)left++;
while (left<=right&&nums[right]>pivot)right--;
if(left<right)swap(nums,left,right);
}
swap(nums,left,rightBound);
return left;
}
int randomized_select(int nums[],int low,int high,int k){
if(low==high)return nums[low];
int i= partition(nums,low,high);
//数组前半部分元素个数
int temp=i-low;
//
if(temp>=k)return randomized_select(nums,low,i-1,k);
else return randomized_select(nums,i+1,high,k-i);
}
int nums[30];
int main() {
srand(time(0));
int len= sizeof(nums)/ sizeof(int);
for (int i = 0; i < len; ++i) {
nums[i]=rand()%30;
}
for (int i = 0; i < len; ++i) {
printf("%d ",nums[i]);
}
printf("\n");
int k=0;
scanf("%d",&k);
randomized_select(nums,0,len-1,k);
for (int i = len-1; i >len-k; --i) {
printf("%d ",nums[i]);
}
return 0;
}
可以求出TopN，但不是有序的
