[Day28]程序菜鸟自学C++资料结构演算法 – 基数排序法(Radix sort)

前言：甚麽是基数排序法？在我刚刚接触这个名词的时候心中满是问号，有很多排序法看到名称或许就能猜出是怎麽运行的，但是却完全摸不透基数排序，藉由这边文章，让我们来探讨基数排序的秘密吧！

多关键字排序：

先来讲讲甚麽是多关键字排序，之前介绍到的排序法大多都只要一个关键字，有时候某些资料会存在多个关键字(例如扑克牌的数值和花色)，而多关键字排序能依优先方式分成两种。

• 最高位优先 (Most Significant Digit First , MSD)
• 最低位优先 (Least Significant Digit First , LSD)
  以扑克牌当举例，将数值大小设定为最高位，花色设定成最低位。
  MSD就是将相同数值的牌放在一起，共13堆。
  LSD则是将相同花色的牌放在一起，共分4堆。
  注意！！！每个关键字必须是稳定的，不然排序会整个乱掉。

基数排序：

是一种非比较型整数排序演算法，原理是将整数按位元数切割成不同的数字，然後按每个位数分别比较。操作方法可以想像成将二位数值写在一堆卡片上，先依十位数牌成十堆卡片，然後在每一堆卡片依照个位数进行排序，最後将十堆卡片依序堆好来完成排序。
如果要排序的资料有位数不等的情况下，先将位数较短的数前面补0，然後从最低位开始依次进行一次排序，这样从最低位排序一直到最高位排序完成以後，数列就变成一个有序序列。
由於整数也可以表达字串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用於整数。
参考资料：https://zh.wikipedia.org/wiki/%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F

基数排序的MSD：分别依序从百位、十位，最後到个位数进行排序。
基数排序的LSD：分别依序从个位、十位，最後到百位数进行排序。

执行效率分析：基数排序的执行效率和快速排序非常相像，以n个键值来说，在二层回圈的内层是O(n)，外层最多执行Log n次，所以时间复杂度是O(n Log n)。
基数排序需要伫列的额外记忆体作为储存空间使用。是一种稳定性的排序法，因为元素是存入伫列，伫列先进先出的特性并不会交换到相同键值的元素。

基数排序实作：基数排序比较复杂，可以重建一个资源档方便撰写。

这次采用系统取乱数的方法来选定要排序的数值。

首先是基数排序过程的函式。

再来式主程序内容。

最後附上执行结果。

本日小结：以往都是自己创建数列来排序，这次用比较不一样的系统取乱数来表示，但也不算是太复杂的东西，主要还是难在基数排序和以往的排序法不太一样，以往的排序都是互相比较，基数排序有点像是对每个数分类，分类到最後才排序出结果，这一部分就复杂很多了，当初用链结串列实作的时候，也是对了超久，好险最後还是有成功做出来，下一篇要来讲解最後一个桶排序和对至今讲过的排序法做一个比较٩(●˙▿˙●)۶…⋆ฺ

#include <iostream>;
#include <cstdlib>;
#include<ctime>;
using std::cout;

struct LNode {
	int val;
	LNode* next{ 0 };
	LNode() :next(0) {}
};

//t位整数
LNode *radixsort(LNode *L, int t) {
	int i, j, d, m = 1;
	LNode *temp, *head[10], *tail[10];

	for (j = 1; j <= t; j++) { //初始化伫列0~9
		for (i = 0; i <= 9; i++) {
			head[i] = 0;
			tail[i] = 0;
		}
		while (L) { //将L的每个元素分配到相应的伫列中

			//得到m对应的那一位数字；m=个、十、百
			d = static_cast<int>(L->val / m) % 10;

			//类似get_front+remove_front的函式
			temp = L;
			L = L->next; //下一个节点
			temp->next = 0;

			if (head[d]) { //伫列不为空
				tail[d]->next = temp; //进入伫列
				tail[d] = temp; //末端指针指向新节点
			}
			else { //伫列为空
				head[d] = temp; //伫列头部指向新节点
				tail[d] = temp; //伫列尾部指向新节点
			}
		}
		//寻找第一的非空的伫列
		d = 0;
		while (!head[d]) 
			d++;

		//伫列头节点作为收集後的链结串列投节点
		L = head[d]; 

		//temp指向链结串列L的末节点
		temp = tail[d];
		
		//将其余非空伫列的节点加到链结串列L的末端
		d++;
		while (d < 10) {
			if (head[d]) {
				temp->next = head[d]; //非空伫列d合并到链结串列L後面
				temp = tail[d]; //temp指向链结串列L的末节点
			}
			d++;
		}
		m = m * 10; //处理更高位
	}
	return L;
}

int main() {
	//初始化乱数发生器种子
	srand(static_cast<unsigned int>(time(NULL)));
	const int size = 20; //生成20个乱数
	int n[size]; //放入n
	int i, max = -1, t = 0; //t表示最大乱数的位数
	
	//生成一组乱数
	LNode* start = 0, * end = 0, * temp = 0;
	for (i = 0; i < size; i++) {
		n[i] = rand(); //用rand生成具体的乱数，并放入n
	}

	//确定最大值并创建一个储存乱数的链结串列
	for (i = 0; i < size; i++) {
		if (n[i] > max) //找最大值
			max = n[i];

		temp = new LNode(); //创建节点
		temp->val = n[i]; //填充乱数

		if (start) { //push_back()；新节点加到链结串列尾部
			end->next = temp;
			end = temp;
		}
		else { //新节点成为链结串列的第一个节点
			start = temp;
			end = temp;
		}
	}
	while (max > 0) { //确定最大乱数的位数t
		t = t + 1;
		max = max / 10;
	}
	cout << "基数排序前： \n";
	temp = start;
	//for (i = 0; i < size; i++) {
	while (temp) {
		cout << temp->val << " ";
		temp = temp->next;
	}
	cout << "\n";
	//基数排序
	start = radixsort(start, t);

	cout << "基数排序的结果\n";
	temp = start;
	//for (i = 0; i < size; i++) {
	while(temp){
		cout << temp->val << " ";
		temp = temp->next;
	}
	cout << "\n";
	return 0;
}