非选择排序之桶排序

缘起

之前介绍的无论是选择排序还是冒泡还是插入还是快排还是堆排序, 都是基于CBA理论（comparison-based-algorithm）， 对应的结果集就是一棵树, 所以CBA最优时间复杂度就是 nlogn. 但是这里要讲的桶排序不属于比较排序,所以他的排序性能可以飙升到O(n).

分析

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
36
37
38
39
40
41
42
43
44
45
46
47
48
#include "stdafx.h"
#include <iostream>
#include <ctime>
#include <cstdlib>

#pragma warning(disable:4996)

const int MAX_K = 105; // 这个MAX_K的含义是参与排序的数的范围是[0,MAX_K]，注意, 非比较排序之所以那么快, 空间换时间. 所以这种基于hash的算法必须要明确参与排序的数字的范围

//#define LOCAL
using namespace std;

void bucketsort(int *a, int n)  // 粗糙版的桶排序
{
	int bucket[MAX_K];
	memset(bucket, 0, sizeof(bucket));
	for(int i = 0; i<n;i++) bucket[a[i]]++; // 装桶
	puts("排序后");
	for (int i = 0; i< MAX_K;i++) for(int j = 0; j<bucket[i]; j++) printf("%d ",i);
}

void bucketsort1(int *a, int n) // 桶排序 精细一点
{
	int bucket[MAX_K], _max = (1<<31), _min = (1<<31)-1; // 桶

	memset(bucket, 0, sizeof(bucket));
	for (int i = 0; i<n;i++)
	{
		bucket[a[i]]++; // 核心排序代码只有这一行for循环
		_max = max(_max, a[i]);
		_min = min(_min, a[i]);
	}
	puts("排序后");
	for (int i = _min; i<=_max;i++) for(int j = 0; j<bucket[i]; j++) printf("%d ",i);
}


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

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