【CPP】链表桶排序

转眼就开学这么久了呀，我又在干什么呢？这学期的数据结构装逼般地买了国外的教材，虽然比国内版难上许多，但是难也就代表讲了更多的东西，那就还是要啃下去呀。那么就来简单说说如何实现链表桶排序吧。

桶排序，又称基数排序，是一种稳定的排序算法，它对于空间的要求度较高（空间复杂度高），且并不是在任何场景下都适用，但是它作为一种简单易懂的排序算法，常见情况下效率比冒泡，选择排序等算法更高。它的时间复杂度是O (nlog(r)m)，其中r为所采取的基数，而m为堆数。但是由于各种原因，实际中并不是特别常用。

在这里我主要说一下桶排序的算法：

桶排序，顾名思义，就是用桶子来进行排序。我们想象现在摆在面前有15个正整数数据，这些数据大小与位数不尽相同，我们想要将他们从小到大排起来。于是乎，我们在面前摆了10个水桶，桶上标有0到9十个数字，然后我们先来遍历这些数据。我们先只看数据的最低位，将各个数据放进它们最低位对应的桶子里。然后我们自然就发现，虽然各个桶子内部的数据仍然是乱序的，但是从最低位来看我们的数据已经排完了。然后我们开始从第一个桶的第一个数开始，依次遍历每个桶的元素，将他们像之前提到过的队列一样一个个排出来再以他们的第二位压入桶中。在这里，两位数以下的数据就被压入了0号桶里，其他的数按照第二位排好了序。由于一开始对个位数排序过，又因为我们从小到大排出了各个数，所以现在所有10以内的数已经排好在0号桶中了。按照同样的方法，我们继续把2位数排进了0号桶，又将三位数排好，将四位数排好。。。直到我们除了0号桶外其他桶里没有元素时，我们便排好了所有数据！

桶排序，作为一种稳定的排序算法，在数据位数不复杂，位数不会太多但是乱时，能达到很高的效率。但是由于无限的桶排序需要利用链表，可能也会在链表处发生一些消耗。但是这些都可以通过不断优化代码来解决，合理地利用桶排序，可以简单地得到较高的计算效率。

然后我们来看看具体实现。首先是链表，之前文章中写过的链表大多太大型太复杂了，在这里我重写了一个效率较差，功能也只实现了最最基本的部分的小链表，虽然它的缺点很多，但是这个小链表比较短小。

链表与结点的声明：

链表已经很清楚了，在这里不再赘述它的具体实现，只要自己去努力实现出稳定的相同的函数就好。在这里的Sort是个简单的选择排序，和桶排序无关，没有必要实现，但可以用来测试Swap函数是否稳定。但是说起来Swap函数也没有必要，只是可以用来加深对链表的理解，写一个稳定好用的Swap可以锻炼自己的编写能力。还有这里的FindPreBYinp函数也没什么用场，只是按照惯例实现一下。这里面很多函数为了方便操作参数和返回值都是目标结点的前一个结点指针，这样写可以简化操作。

然后我们来看看桶排序的具体实现。

首先是简单的桶排序声明：

这只是一个很简单的类。只包含了桶排序的核心和一点小参数。其中的Cursor是用来获取各个元素的各个位数信息的参数。定义一个链表指针数组用来模拟上文说到的桶子。

这是构造函数。

不写默认构造函数，这个带参构造函数的目的是读取每个数的最低位然后输入桶中同时进行了第一次排序。

然后是关键的排序部分。

在这里，全部利用上面链表中的函数在for循环中模拟了上文说到的出桶进桶过程，提取某个桶的第一个数，判断后加入目标桶的尾部，然后再删除刚才的那个数循环，直到每个数都被处理过。然后不断循环，一位一位处理后直到每个数都按照要求被排序完成时循环跳出。

然后简单地Display整个桶。

析构函数，拷贝构造函数，默认构造函数，输入函数等等没有太多不同的东西，在这不再写。（摸了）

然后我们就能看到运行结果，前面是排序前的，后面是排序后的。

摸了摸了，链表的效率什么的，不存在的。

代码：链接：http://pan.baidu.com/s/1eRV24k6 密码：pnlp