从零开始学算法：十种排序算法介绍(下).doc

HYPERLINK"http://www.matrix67.com/blog/archives/178"\o"PermanentLinkto从零开始学算法：十种排序算法介绍（下）"从零开始学算法：十种排序算法介绍（下）
HYPERLINK"http://www.matrix67.com/blog/archives/category/program-impossible"\o"查看ProgramImpossible的全部文章"ProgramImpossible|2007-04-134:09|16Comments|本文内容遵从HYPERLINK"http://creativecommons.org/licenses/by-nc-sa/3.0/deed.zh"\t"_blank"CC版权协议转载请注明出自matrix67.com
那么，有什么方法可以不用比较就能排出顺序呢？借助Hash表的思想，多数人都能想出这样一种排序算法来。我们假设给出的数字都在一定范围中，那么我们就可以开一个范围相同的数组，记录这个数字是否出现过。由于数字有可能有重复，因此Hash表的概念需要扩展，我们需要把数组类型改成整型，用来表示每个数出现的次数。看这样一个例子，假如我们要对数列314159265359进行排序。由于给定数字每一个都小于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!Youshouldthinkforawhile.我们班有很多MM。和身高相差太远的MM在一起肯定很别扭，接个吻都要弯腰才行（HYPERLINK"http://fayecatshome.spaces.live.com"\t"_blank"小猫矮死了）。为此，我希望给我们班的MM的身高排序。我们班MM的身高，再离谱也没有超过2米的，这很适合用我们刚才的算法。我们在黑板上画一个100到200的数组，MM依次自曝身高，我负责画“正”字统计人数。统计出来了，从小到大依次为141,143,143,147,152,153,...。这算哪门子排序？就一排数字对我有什么用，我要知道的是哪个MM有多高。我们仅仅把元素的属性值从小到大列了出来，但我们没有对元素本身进行排序。也就是说，我们需要知道输出结果的每个数值对应原数据的哪一个元素。下文提到的“排序算法的稳定性”也和属性值与实际元素的区别有关。问题二：怎样将线性时间排序后的输出结果还原为原数据中的元素？STOP!Youshouldthinkforawhile.同样借助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]||||A[12]A[4]A[10]A[9]|A[11]形象地说，我们在地上摆10个桶，每个桶编一个号，然后把数据分门别类放在自己所属的桶里。这种排序算