非比较排序之计数排序

缘起

【1】中讲解了非比较排序中的一种——桶排序. 这里介绍非比较排序的第二种——计数排序， 非比较排序的性能都是可以到达O(n)这种线性性能的. 因为都是使用hash进行空间换时间. 注意, 正因为需要空间换时间, 所以基于hash的排序算法需要明确参与排序的数值有一定的范围. 范围越大, 越消耗空间.

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include "stdafx.h"
#include <iostream>
#include <ctime>
#include <cstdlib>

#pragma warning(disable:4996)

const int MAX_K = 105; // 这个MAX_K的含义是参与排序的数的范围是[0,MAX_K]
const int MAX_N = 100; // 最多100个数参与排序

//#define LOCAL
using namespace std;

void countsort(int *a, int n)
{
	int jishu[MAX_K], sort[MAX_N];
	memset(jishu, 0, sizeof(jishu));
	for (int i = 0; i<n;i++) jishu[a[i]]++; // 桶
	for (int i = 1; i< MAX_K; i++) jishu[i] += jishu[i-1]; // 求部分和序列
	for (int i = n-1; ~i; i--) sort[--jishu[a[i]]] = a[i]; // 注意, 对于某些i而言, a[i]是相等的. 所以jishu[a[i]]就是后者减1的关系
	puts("排序后");
	for (int i = 0; i< n; i++) printf("%d ", sort[i]);
}


int main()
{
#ifdef LOCAL
	freopen("d:\\data.in","r",stdin);
#endif

	int a[8]={49, 38 , 35, 97 , 76, 73 , 27, 49 };
	countsort(a, 8);
	return 0;
}

参考

【1】https://yfsyfs.github.io/2019/05/25/%E9%9D%9E%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F%E4%B9%8B%E6%A1%B6%E6%8E%92%E5%BA%8F/