十种排序算法介绍(下) zz

时间:2021-12-07 21:54:54
出自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]    |