基数排序 - 桶排序

时间复杂度 O(n*d) – d为数据的长度

每次比较一位（个位、十位。。。），所以取值范围就为0-9。
根据该特点，设计桶的概念 – 0号桶、1号桶…

1、思想

1）找出最长的数字，确定要处理的桶的趟数（位数）
2）依次由个位开始处理，把相应位数上的数字，放入相应序号的桶内，
完成后，再按照桶的序号，依次取出桶里面的数据，放回原始数据当中。
3）当处理完所有的位数，最终得到有序的序列。

2、局限性

1）数据类型改变，需要代码较大的修改。
对于之前的代码，如果换成浮点数等其他类型数据，大体代码思路一致。
但是基数算法不行，代码无法做到统一，需要进一步修改。
2）对于数据正负性，要求较高。
之前的代码，数据正负性影响不大，可比较即可。
对于基数排序，需要进一步堆数据进行修改。下文实现的代码，对于负数无法实现。

3、实现过程

1）从左到右依次遍历原始数据，先由个位开始比较。根据每个数据的个位，放入相应的桶中。一次遍历，如下图所示：

2）依次遍历各个桶，将其重新拷贝到原数据。

3）根据十位，依次放入对应桶中。

4）依次取出数据

因为此次数据最大为两位数，所以这次操作，就可以发现数据有序了。

4、核心代码：

1）循环每次取出位上的数字。

2）桶的定义，

需要为二维数组。使用vector<vector<int>>

4、代码实现

#include<iostream>
#include<stdlib.h> //包含随机数函数srand
#include<time.h> //需要用time作为随机数种子
#include<string>
#include<vector>

//基数排序代码
void RadixSort(int arr[], int size)
{
	int maxData = arr[0];

	//求得数据最大值
	for (int i = 1; i < size; i++)
	{
		if (maxData < arr[i])
		{
			maxData = arr[i];
		}
	}

	//使用系统自带的函数，求取最大值的位数
	int len = to_string(maxData).size();

	//定义桶的二维数组
	vector<vector<int>> vecs;//这里底层并没有空间

	int mod = 10;
	int dev = 1;

	//处理数据
	for (int i = 0; i < len; mod *= 10, dev *= 10, i++) //O(d) d为数据的长度
	{
		vecs.resize(10);

		for (int j = 0; j < size; j++)
		{
			//得到当前元素第i个位置的数字
			int index = arr[j] % mod / dev;
			vecs[index].push_back(arr[j]);
		}

		//依次遍历所有的桶，把元素拷贝回原始的数组当中
		int idx = 0;
		for (auto vec : vecs)
		{
			for (int v : vec)
			{
				arr[idx++] = v;
			}
		}

		//清空桶内元素，方便下次使用
		vecs.clear();
	}

}

测试

int main()
{
	int arr[10];
	srand(time(NULL));

	for (int i = 0; i < 10; i++)
	{
		arr[i] = rand() % 100 + 1;
	}

	for (int v : arr)
	{
		cout << v << "  ";
	}
	cout << endl;

	RadixSort(arr, sizeof(arr) / sizeof(arr[0]));

	for (int v : arr)
	{
		cout << v << "  ";
	}
	cout << endl;

	return 0;
}

5、 对于有负数情况下，代码修改

1）桶，需要设计为20个。增加负数存放的位置。

vecs.resize(20);

2）求取最大值位数时，需要增加abs() – 绝对值函数

//求得数据最大值
for (int i = 1; i < size; i++)
{
	if (maxData < abs(arr[i]))
	{
		maxData = abs(arr[i]);
	}
}

3） 数据的存放

取得所需位数后，再加10。
负数放于0-9的桶中，正数放于10-19的桶中。

	for (int j = 0; j < size; j++)
		{
			//得到当前元素第i个位置的数字
			int index = arr[j] % mod / dev + 10;
			vecs[index].push_back(arr[j]);
		}

代码实现

//基数排序代码
void RadixSort(int arr[], int size)
{
	int maxData = arr[0];

	//求得数据最大值
	for (int i = 1; i < size; i++)
	{
		//为了处理负数，使用abs(),取绝对值
		if (maxData < abs(arr[i]))
		{
			maxData = abs(arr[i]);
		}
	}

	//使用系统自带的函数，求取最大值的位数
	int len = to_string(maxData).size();

	//定义桶的二维数组
	vector<vector<int>> vecs;//这里底层并没有空间

	int mod = 10;
	int dev = 1;

	//处理数据
	for (int i = 0; i < len; mod *= 10, dev *= 10, i++)
	{
		vecs.resize(20);//20个桶，为了能处理负数 -9 --  9

		for (int j = 0; j < size; j++)
		{
			//得到当前元素第i个位置的数字
			int index = arr[j] % mod / dev + 10;
			vecs[index].push_back(arr[j]);
		}

		//依次遍历所有的桶，把元素拷贝回原始的数组当中
		int idx = 0;
		for (auto vec : vecs)
		{
			for (int v : vec)
			{
				arr[idx++] = v;
			}
		}

		//清空桶内元素，方便下次使用
		vecs.clear();
	}

}

测试