C++实现几种常见的排序算法（下）

• 6、堆排序
• 7、计数排序
• 8、基数排序

这里用的是闫神的模板，具体可以看这个链接，具体注释放在代码里了。

#include
#include
using namespace std;
#include

//这里以大根堆为例

//弹出元素的话，就是更新堆顶，进行push_down 操作
//插入元素的话，就是更新堆底，进行push_up   操作

//n表示完全二叉树的所有节点个数，i表示当前节点
void push_down(vector& heap, int n, int i)
{
	//这里堆的根节点是从1开始的
	int max = i;  
	int left = 2 * i;
	int right = 2 * i + 1;

	if (left < n && heap[left] > heap[max])
		max = left;
	if (right < n && heap[right] > heap[max])
		max = right;
	if (i != max)		//当前节点i不是最大值时交换
	{
		swap(heap[i], heap[max]);
		push_down(heap, n, max);
	}
}

//从树的倒数第二层第一个结点开始
void push_up(vector& heap, int i)
{
	while (i / 2 && heap[i / 2] < heap[i])
	{
		swap(heap[i / 2], heap[i]);
		i /= 2;
	}
}

void heapSort(vector& num, int n)
{
	int size = n;
	//1、建立大根堆
	for (int i = 1; i < n + 1; i++)
		push_up(num, i);

	//2、排序
	for (int i = 1; i < n + 1; i++)
	{
		swap(num[1], num[size]);		//交换最底部的到第一个位置
		size--;
		push_down(num, size, 1);
	}
}
int main()
{
	vector num;
	int n;
	cin >> n;
	num.resize(n + 1);		//这里重新开辟一下空间
	
	for (int i = 1; i < n + 1; i++)
		cin >> num[i];

	heapSort(num, n);

	//这里堆的根节点是从1开始的
	for (int i = 1; i < n + 1; i++)
	{
		cout << num[i] << ' ';
	}
	cout << endl;

	return 0;
}

#include
#include
using namespace std;
#include

//计数排序一般是用来排序 0 到 100 之间的数字的最好的算法，它不是比较排序，所以排序的速度快于任何比较排序算法

//核心：将输入的数据值转化为键，存储在额外开辟的数组空间中，统计该数据值的元素的个数count[i]


void countingSort(vector& num, int n)
{
	vector count(101, 0);

	for (int i = 0; i < n; i++)			//遍历num数组
	{
		count[num[i]]++;				//num[i]范围在0-100
	}

	//在两个数组中遍历，能用两个变量尽量用两个变量
	for (int i = 0, k = 0; i < 101; i++)//此时i是遍历count数组
	{
		while (count[i])
		{
			num[k++] = i;		//将键的值重新存储到num[k]中
			count[i]--;			//每存储一个，键对应的个数-1
		}
	}
}
int main()
{
	vector num = { 8,9,1,4,2,3,6,7,5,5 };

	countingSort(num, num.size());

	for (auto i : num) {
		cout << i << " ";
	}
	cout << endl;
	return 0;
}

#include
#include
using namespace std;
#include

//这里使用的是0-999的三位数排序，先排低位，再排高位

int get(int x, int i)
{
	while (i--)
		x /= 10;		//求余
	return x % 10;		//求模
}

void radixSort(vector& num,int n)
{
	//分十个桶(0-9)
	vector> count(n);		//定义二位数组，每个桶用于存放

	for (int i = 0; i < 3; i++)			//i = 0排序个位，i = 1排序十位，i = 2排序百位
	{
		for (int j = 0; j < 10; j++)
			count[j].clear();			//每次分配前清空各桶的元素
		for (int j = 0; j < n; j++)
		{
			count[get(num[j], i)].push_back(num[j]);
		}
		
		//每轮循环并且按桶排完序之后，放回到原数组中
		for (int j = 0, k= 0; j < 10; j++)		//循环桶
		{
			for (int x : count[j])
			{
				num[k++] = x;
			}
		}
	}
}


int main()
{
	vector num = { 999, 457, 71, 1, 471, 65, 2, 12, 748, 12 };

	radixSort(num, num.size());

	for (auto i : num) {
		cout << i << " ";
	}
	cout << endl;
	return 0;
}