原来写过一篇文章在笔记本里，后来中病毒我把它格了，也没上网没机会发表出来，主要内容是关于一种比较另类的排序方法的，我叫它散列排序法。凭我的记忆把算法的主要思想写下来。

排序法总体上可以分两大类，一类是基于‘比较’的，主要有大家非常熟悉的：选择排序，交换排序，插入排序，归并排序等，其算法的复杂度也是用‘比较’的次数衡量的，其中有非常高效和优秀的‘快速排序’，可以说是他们中间的佼佼者，无论从时间还是空间上说都有很好的性能；另外一类也就自然是不基于‘比较’的，《数据结构》上介绍过一种叫‘基数排序’，我觉得也很经典，今天我要向大家介绍的跟基数排序很类似，原理也非常简单。

和基数排序的方法非常类似，也是采用分配和收集，而我管它叫‘散列’，因为就和hash散列表一样，而且我可以说当数据比较均匀的离散分布的时候，效率是非常高的，可以花很少的几次散列就得到有序结果。

[写在前面，也跟基数排序一样只适用于整数排序，因为不基于比较就只能从元素，即数的本身出发了。]

先举个例子，设待排序的数是：
4,2,5,1,3

我们排序的任务就是让上面一列数有序，看看我们要做的结果是什么：
1,2,3,4,5

于是我们的任务就是，把前面一列数各位数放到‘正确’的位置上去，使得它有序。而一个数和它的正确位置就是一个映射关系，于是我们就是要找到一个函数f(x)，使f(x)->‘x的正确位置’！

上面的例子非常简单，f(x)=x，但实际情况非常复杂，其实像这样的f(x)是不可能有很好的数学表达式的，别指望在这里做更多的努力。于是我着手找近似的f(x)，我的想法是，只要让它不会错太多就行了，不完善的可以慢慢做得完善。

实际上f(x)就是一个散列函数，只不过它不是用来检索而是用来排序，我给出一个f(x)=[(x-min)*(n-1)/(max-min)]，其中min是这列数的最小值，max是这列数的最大值，n是这列数的个数，那值域就会在[0,n-1]，再用这些值找散列存储位置。

在这样一个近似的f(x)函数下，会出些‘意外’的情况，首先可能会有两个元素得到相同的f(x)值，也就是‘冲突’，冲突如何解决？可以采用拉链法，类似于hash表的冲突处理。

为什么要用拉链法，其实可以从集合的角度看这个算法，实际上我是把整个数列看成一个集合，然后我着手把它分成更小一些的子集，同时使这些子集‘集合间有序’，所谓集合间有序是指：
如果 集合A<集合B
那么 对于任意的x,x属于A，又对于任意的y,y属于B，都成立x<y

然后不断往下分，直到被分的集合中只含有一个元素为止，排序工作就完成了。

再来个例子：
1,4,3,7,3,2
于是
min=1,max=7,n=6
f(x)=[(x-1)*5/6]
第一次划分的结果是：
收集链表ID：0 1 2 3 4 5
[元素]      1 3 4     7
            2 3
就得到了四个子集，设对应ID的子集记为[ID]，那么它们是
{[0],[1],[2],[5]}   （它们也是第一次划分f(x)的值域）
它们是‘集合间有序’的。

算法到此全部描述完了，另外我还想说点具体实现的过程，虽然没源代码了，还有些细节问题。

1、f中的min,max该如何求？
给我们的排序任务，只给出数据地址和数据元素，并没有给出min和max，是不是需要先求一下呢？如果要求一下，又回到了比较的方法，于是整个算法就不是很好的不基于比较的算法。我的看法是，具体排序的时候如果能给出来可以尽量给出（比如，按一个城市所有人的年龄排序，范围可以是0~150），如果真给不出来，没关系，我们取那种类型的数据的最小值和最大值。但是这不会影响到效率吗？后面再讨论效率。
另外再提出个概念，叫‘区分度’，区分度就是指一次划分的时候，得到的子集内的元素的最大值和最小值之差的最大值；这样吧，可能不好理解。这样记，我记一次划分为：
div(min,max):（这样记是因为，一次划分是跟min和max分不开的，确定了min和max才能划分）
{parent} --> {[i]}
那这次划分的区分度就是
max{elem1-elem2|elem1,elem2属于[i]}
在前面的例子中就是1，因为[0]中2-1最大。
为什么要提这个概念，在你划分一次后如果没有得到结果，那必须再对子集进行划分，这时的子划分中的max-min正是前一次的区分度。如果还知道min，那子划分就确定了。而min是可以线性求出来的，于是子划分就完全确定下来了。
区分度约为(max-min)/n *

2、这个算法的效率如何？
首先从时间上考虑。整个排序的过程可以看成是把一个有n个元素的集合分成n个只有一个元素的子集的过程。而就以划分的次数来衡量的话，最差的情况是，连续几次划分都没有分成功，原有集合本身做为子集，但是这样的情况不会持续很久，随着更加细致的划分，区分度会不断变小，区分度的迭代递推式是：d'=d/n，实际上是非常快速的收敛。其次，如果每一次划分只能分成两个子集，效率会如何呢？注意到划分出的子集是集合间有序的，这会联想到快速排序的一次划分，没错快速排序的一次划分能且只能将元素划分成两个部分，这两个部分有序，所以应该和快速排序的效率相当。最后，如果每一次划分能分成两个子集以上，效率会更高吗？不用我说了，应该会更高吧~~
实际上对于离散分布比较均匀（等概率分布）的无序数，排起序来是非常高效的~！
另外从空间上考虑。这就比快速排序差太多了，整个辅助空间需要得很大，基本上需要和原有数据量一样多的空间，应该是O(n)，当n很大时，运行的实际耗时基本上都花在内存空间分配和回收上了。

评论