十种排序算法介绍（下） zz

出自matrix67.com 那么，有什么方法可以不用比较就能排出顺序呢？借助Hash表的思想，多数人都能想出这样一种排序算法来。
    我们假设给出的数字都在一定范围中，那么我们就可以开一个范围相同的数组，记录这个数字是否出现过。由于数字有可能有重复，因此Hash表的概念需要扩展，我们需要把数组类型改成整型，用来表示每个数出现的次数。
    看这样一个例子，假如我们要对数列3 1 4 1 5 9 2 6 5 3 59进行排序。由于给定数字每一个都小于10，因此我们开一个0到9的整型数组T[i]，记录每一个数出现了几次。读到一个数字x，就把对应的T[x]加一。

  A[]= 3, 1,4, 1, 5, 9, 2, 6, 5, 3, 5, 9
              +---+---+---+---+---+---+---+---+---+---+
      数字 i： | 0 | 1 | 2 | 3 | 4 | 5 |6 | 7 | 8 | 9 |
              +---+---+---+---+---+---+---+---+---+---+
出现次数T[i]： | 0 | 2 | 1 | 2 | 1 | 3 | 1 | 0 | 0 | 2 |
              +---+---+---+---+---+---+---+---+---+---+

    最后，我们用一个指针从前往后扫描一遍，按照次序输出0到9，每个数出现了几次就输出几个。假如给定的数是n个大小不超过m的自然数，显然这个算法的复杂度是O(m+n)的。

    我曾经以为，这就是线性时间排序了。后来我发现我错了。再后来，我发现我曾犯的错误是一个普遍的错误。很多人都以为上面的这个算法就是传说中的计数排序。问题出在哪里了？为什么它不是线性时间的排序算法？原因是，这个算法根本不是排序算法，它根本没有对原数据进行排序。


问题一：为什么说上述算法没有对数据进行排序？
STOP! You should think fora while.

    我们班有很多MM。和身高相差太远的MM在一起肯定很别扭，接个吻都要弯腰才行（小猫矮死了）。为此，我希望给我们班的MM的身高排序。我们班MM的身高，再离谱也没有超过2米的，这很适合用我们刚才的算法。我们在黑板上画一个100到200的数组，MM依次自曝身高，我负责画“正”字统计人数。统计出来了，从小到大依次为141,143, 143, 147, 152, 153,...。这算哪门子排序？就一排数字对我有什么用，我要知道的是哪个MM有多高。我们仅仅把元素的属性值从小到大列了出来，但我们没有对元素本身进行排序。也就是说，我们需要知道输出结果的每个数值对应原数据的哪一个元素。下文提到的“排序算法的稳定性”也和属性值与实际元素的区别有关。


问题二：怎样将线性时间排序后的输出结果还原为原数据中的元素？
STOP! You should think fora while.

    同样借助Hash表的思想，我们立即想到了类似于开散列的方法。我们用链表把属性值相同的元素串起来，挂在对应的T[i]上。每次读到一个数，在增加T[i]的同时我们把这个元素放进T[i]延伸出去的链表里。这样，输出结果时我们可以方便地获得原数据中的所有属性值为i的元素。

  A[]= 3, 1,4, 1, 5, 9, 2, 6, 5, 3, 5, 9
              +---+---+---+---+---+---+---+---+---+---+
      数字 i： | 0 | 1 | 2 | 3 | 4 | 5 |6 | 7 | 8 | 9 |
              +---+---+---+---+---+---+---+---+---+---+
出现次数T[i]： | 0 | 2 | 1 | 2 | 1 | 3 | 1 | 0 | 0 | 2 |
              +---+o--+-o-+-o-+-o-+-o-+--o+---+---+-o-+
                    |    |  |   |  |    |          |
                +--+  +-+   |   |  +-+  +---+      |
                |     |  A[1]  |    |      |    A[6]
              A[2]  A[7]    |  A[3]  A[5]  A[8]    |
                |          |