资源描述：
《从零开始学算法：十种排序算法介绍(下)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、从零开始学算法：十种排序算法介绍（下）ProgramImpossible
2、2007-04-134:09
3、16Comments
4、本文内容遵从CC版权协议转载请注明出自matrix67.com 那么，有什么方法可以不用比较就能排出顺序呢？借助Hash表的思想，多数人都能想出这样一种排序算法来。 我们假设给出的数字都在一定范围中，那么我们就可以开一个范围相同的数组，记录这个数字是否出现过。由于数字有可能有重复，因此Hash表的概念需要扩展，我们需要把数组类型改成整型，用来表示每个数出现的次数。 看这样一个例子，假如我们要对数列314159265359进行排序。由于给
5、定数字每一个都小于10，因此我们开一个0到9的整型数组T[i]，记录每一个数出现了几次。读到一个数字x，就把对应的T[x]加一。 A[]=3,1,4,1,5,9,2,6,5,3,5,9 +---+---+---+---+---+---+---+---+---+---+ 数字i：
6、0
7、1
8、2
9、3
10、4
11、5
12、6
13、7
14、8
15、9
16、 +---+---+---+---+---+---+---+---+---+---+出现次数T[i]：
17、0
18、2
19、1
20、2
21、1
22、3
23、1
24、0
25、0
26、2
27、 +---+---+---+-
28、--+---+---+---+---+---+---+ 最后，我们用一个指针从前往后扫描一遍，按照次序输出0到9，每个数出现了几次就输出几个。假如给定的数是n个大小不超过m的自然数，显然这个算法的复杂度是O(m+n)的。 我曾经以为，这就是线性时间排序了。后来我发现我错了。再后来，我发现我曾犯的错误是一个普遍的错误。很多人都以为上面的这个算法就是传说中的计数排序。问题出在哪里了？为什么它不是线性时间的排序算法？原因是，这个算法根本不是排序算法，它根本没有对原数据进行排序。问题一：为什么说上述算法没有对数据进行排序？STOP!Youshouldthinkforawhi
29、le. 我们班有很多MM。和身高相差太远的MM在一起肯定很别扭，接个吻都要弯腰才行（小猫矮死了）。为此，我希望给我们班的MM的身高排序。我们班MM的身高，再离谱也没有超过2米的，这很适合用我们刚才的算法。我们在黑板上画一个100到200的数组，MM依次自曝身高，我负责画“正”字统计人数。统计出来了，从小到大依次为141,143,143,147,152,153,...。这算哪门子排序？就一排数字对我有什么用，我要知道的是哪个MM有多高。我们仅仅把元素的属性值从小到大列了出来，但我们没有对元素本身进行排序。也就是说，我们需要知道输出结果的每个数值对应原数据的哪一个元素。下文提
30、到的“排序算法的稳定性”也和属性值与实际元素的区别有关。问题二：怎样将线性时间排序后的输出结果还原为原数据中的元素？STOP!Youshouldthinkforawhile. 同样借助Hash表的思想，我们立即想到了类似于开散列的方法。我们用链表把属性值相同的元素串起来，挂在对应的T[i]上。每次读到一个数，在增加T[i]的同时我们把这个元素放进T[i]延伸出去的链表里。这样，输出结果时我们可以方便地获得原数据中的所有属性值为i的元素。 A[]=3,1,4,1,5,9,2,6,5,3,5,9 +---+---+---+---+---+---+-
31、--+---+---+---+ 数字i：
32、0
33、1
34、2
35、3
36、4
37、5
38、6
39、7
40、8
41、9
42、 +---+---+---+---+---+---+---+---+---+---+出现次数T[i]：
43、0
44、2
45、1
46、2
47、1
48、3
49、1
50、0
51、0
52、2
53、 +---+o--+-o-+-o-+-o-+-o-+--o+---+---+-o-+
54、
55、
56、
57、
58、
59、
60、 +--+ +-+
61、
62、 +-+ +---+
63、
64、
65、
66、 A[1]
67、
68、
69、 A[6] A[2] A[7]
70、 A[3] A[5] A[8]
71、
72、
73、
74、 A[12] A[4] A[10] A[9]
75、
