欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

C++实现_topk排序

程序员文章站 2022-04-01 12:19:23
一、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