基数排序

发表于

思路

基数排序是将所有的待排数据（只能是正整数）的位数统一，数位较短的数据需要在开头补零。然后，从最低位开始，依次进行排序，这样从最低位一直到最高位依次进行排序后，就可以得到一个有序的数列。

图示（参考链接）

image

代码实现

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
/*
 * 寻找位数的最大值
 */
int max_bit(int * data, int len)
{
	int bit = 0;
	int i = 0;
	for (i = 0; i < len; i++)
	{
		int bit_temp = 0;
		int temp = data[i];
		while (1)
		{
			if ( (temp / 10) == 0 && temp == 0)
				break;
			bit_temp++;
			temp = temp / 10;	
		}
		if (bit_temp > bit)
			bit = bit_temp;
	}
	return bit;
}

/*
 * 基数排序
 */
void RadixSort(int * data, int len)
{
	//得到最大位数值
	int bit = max_bit(data,len);
	int r = 1;
	int count[10];
	int * tmp = (int *)calloc(len,sizeof(int));
	//对每个位上的数进行排序
	int i = 0;
	int index = 0;
	printf("bit = %d\n", bit);
	for (index = 0; index < bit; index++)
	{
		//装桶之前要先清桶
		memset(count, 0, 10*sizeof(int));
		for (i = 0; i < len; i++) //记录每个桶的记录数
		{
			int k = data[i] / r;
			int q = k % 10;     
			count[q]++;
		}
		//为存储桶里的数据腾出足够的空间，这样好存储。
		//通过画图可以容易理解这个循环的含义
		for (i = 1; i < 10; i++)
		{
			count[i] += count[i - 1];
		}
		//这个循环从后往前走是为了保证数据的稳定性，
		//因为每个桶里的数据都是从该桶底部往上存放的
		for (int j = len - 1; j >= 0; j--)
		{
			int p = data[j] / r;
			int s = p % 10;
			tmp[count[s] - 1] = data[j];
			count[s]--;
		}
		//将排好的数据复制回去
		for (i = 0; i<len; i++)
		{
			data[i] = tmp[i];
			printf("%d,", data[i]);
		}
		printf("\n");
		r = r * 10;                //从个位开始，依次往前走
	}
	free(tmp);
}
int main()
{
	int data[] = { 329, 457, 657, 839, 436, 720, 355 };
	RadixSort(data, 7);
	int i;
	for (i = 0; i < 7; i++)
		printf("%d,", data[i]);
	printf("\n");
	system("pause");
	return 0;
}

算法分析

通过代码实现，我们可以知道算法的时间复杂度为：O(k * n).其中k为位数最长的值，n为元素的个数。