C++实现_topk排序
程序员文章站
2022-09-16 20:30:46
一、topk_堆排#include#include#include//堆排序using namespace std;void Swap(vector& tree, int a, int b) {int temp = tree[a];tree[a] = tree[b];tree[b] = temp;}void heapify(vector
一、topk_堆排
#include<iostream>
#include<vector>
#include<algorithm>
//堆排序
using namespace std;
void Swap(vector<int>& tree, int a, int b) {
int temp = tree[a];
tree[a] = tree[b];
tree[b] = temp;
}
void heapify(vector<int>& tree, int n, int i) {
if (i >= n)
return;
int min = i;
int c1 = 2 * i + 1;
int c2 = 2 * i + 2;
if (c1<n && tree[c1] < tree[min]) {
min = c1;
}
if (c2<n && tree[c2] < tree[min]) {
min = c2;
}
if (min != i) {
Swap(tree, min, i);
heapify(tree, n, min);
}
}
void print(vector<int>& tree,int n) {
for (int i = 0; i < n; i++) {
printf("%d ", tree[i]);
}
printf("\n");
}
void build_heap(vector<int>& tree,int n) {
int last_node = n - 1;
int parent = (last_node - 1) / 2;
for (int i = parent; i >= 0; i--) {
heapify(tree, n, i);
}
}
//核心
void heap_sort(vector<int>&arr,vector<int>&tree,int n) {
for (int i = n+1; i < arr.size();i++) {
build_heap(tree, n);
print(tree, n);
if (arr[i] > tree[0]) {
tree[0] = arr[i];
}
}
}
int main() {
vector<int> tree = { 2,3,4,15,2,15,534,34,53,4645,6,1234,23423,23423,2,6354,62,54123,4,12 };
/*验证
sort(tree.begin(), tree.end());
print(tree, tree.size());*/
vector<int> arr = tree;
int n = 7;
heap_sort(arr,tree, n);
return 0;
}
二、topk_sort排序
#include <iostream>
#include <vector>
#include <algorithm>
template <typename T>
void sorts(std::vector<T>& v) {
// sort vector ----- Ascend
sort(v.begin(), v.end());
}
template <typename T>
void print(std::vector<T>& v) {
for (auto num : v)
std::cout << num << " ";
std::cout << std::endl;
}
template <typename T>
std::vector<T> topK(std::vector<T>& v, int k) {
std::vector<T> tmp(v.begin(), v.begin() + k);
for (int i = k + 1; i < v.size(); ++i) {
sorts(tmp);
print(tmp);
if (v[i] < tmp[0])
continue;
tmp[0] = v[i];
}
return tmp;
}
int main() {
std::vector<int> v = { 2,3,4,15,2,15,534,34,53,4645,6,1234,23423,23423,2,6354,62,54123,4,12 };
std::vector<int> res = topK(v, 7);
print(res);
return 0;
}
本文地址:https://blog.csdn.net/SmartDemo/article/details/107572238