排序的基本概念

1、基本观念1 排序的基本概念2 内部排序3 二叉树排序4 外部排序排序Chapter 77-1排序的基本概念一、排序的意义排序（sorting）是指将一些数据，按照某种排列规则，重新安排数据的次序，使其具有递增或递减的线性次序（linear order）关系。经过排序的数据比较容易阅读，并且利于统计与分析，同时也可加快数据查找（search）的速度。通常排序可分为两大类内部排序及外部排序。1 内部排序（Internal Sort）：指数据量小，可以一次将所有数据直接存储在主存储器内的排序法。2 外部排序（External Sort）：指数据量非常大，无法一次将所有数据直接存储在主存储器内，必须借

2、助外部辅助内存的排序法。二、内部排序常见的内部排序法有：1.选择排序法( Selection Sort )2.插入排序法( Insertion Sort )3.冒泡排序法( Bubble Sort )4.快速排序法( Quick Sort )5.归并排序法( Merge Sort )6.堆排序法( Heap Sort )7.基数排序法(Radix Sort)以上七种常见的内部排序法，若按照其算法的时间复杂度及键值的比较方式，可区分为：1.简单排序技术（Simple Sort Technique）有选择排序法、插入排序法及冒泡排序法等，皆属比较性排序法，即其排序方式是比较整个键值，而且每次比较均

3、是将数据作两两相比。这些方法的平均情况的时间复杂度及最坏情况的时间复杂度均为O(n2)。2.高级排序技术（Advanced Sort Technique）有快速排序法、归并排序法及堆排序法等，亦属比较性排序法，每次比较两个键值后，由两条路径中决定一条，形成决策树形式。这些方法的平均情况的时间复杂度及最坏情况的时间复杂度均为O(n log n)，但快速排序法的最坏情况的时间复杂度为O(n2)。3.基数排序技术（Radix Sort Technique）基数排序法（Radix Sort），是根据所采用数字基底（如二进制、八进位、十进制或十六进制），每次使用一位（digit）来分类数据，因此一次只比

4、较键值的某一位。这种有别于比较性排序法的排序方式称为分配性排序法，其又可依比较方向分为最重要键值优先排序（Most Significant Digit First；简称MSD）与最不重要键值优先排序（Least Significant Digit First；简称LSD）两种。三、外部排序典型的外部排序法有K路归并法（K-way Merge）及多相排序法（Polyphase Merge）。四、稳定与不稳定排序法1.稳定排序法 (Stable Sort)：一个排序方法称为稳定，是指经排序后，相同的键值仍然保持原来的相对次序。2.不稳定排序法 (Unstable Sort)：是指两个具有相同键值的

5、记录r(i)和r(j)，在源文件中r(i)放在r(j)的前，但经过排序的后，结果r(j)变成放在r(i)的前，则称此种排序法为不稳定排序法。说明：（以“+”记号区分两相同键值）7-2内部排序一、冒泡排序法（Bubble Sort）1.方法：冒泡排序法又称为交换排序法（Interchange Sort），相邻的键值两两相比，如果前一个比后一个大时，则互相对调，属于稳定排序法。2.说明：假设有5个数据，分别是26，5，37，1，61，利用冒泡排序法排序如下：注：由此可知5个数据的总共比较次数为10次( 4 + 3 + 2 + 1 )，而n笔数据的总共比较次数为(n-1) + (n-2) + +1

6、= n(n-1)/2次。3.算法：Procedure BUBSORT(R, n) for iß1 to n-1 do for jß1 to n-i do if kj+1<kj then tempßRj RjßRj+1 Rj+1ßtemp end if end for end forend BUBSORT1.以冒泡排序法（bubble sort）排序n个数据，其效率（efficiency）是：(A) O(1)(B) O(n)(C) O(n log n)(D) O(n2)。 87年二技电机【答案】 （D）【解析】 冒泡排序法的时间复杂度为O(

7、n2)，故选(D)。2.数列（21, 19, 37, 5, 2）经由冒泡排序法（bubble sort）由小到大排序，在第一次执行交换（swap）的后所得结果为(A) (19，21，37，5，2)(B) (21，19，5，37，2)(C) (21，19，37，2，5)(D) (2，21，19，37，5)84年二技设计【答案】 （A）【解析】 第一次执行交换（swap）的后，结果为（19，21，37，5，2），故选(A)。二、选择排序法（Selection Sort）1.方法：假设记录为R1，R2，Rn，其键值分别为K1，K2，Kn，将这些记录从小到大排序，属于不稳定排序法。步骤一：从所有的记录

8、中挑一个具有最小键值的记录，然后将该记录与第一个记录对调。步骤二：从剩余的数据中，再挑选最小的键值，然后将该记录与第二个记录对调，重复执行步骤二，直到只剩下一个键值为止。2.说明：排序下面的数据5，7，4，5+，6，3，8（以“+”来区分两个相同键值），结果如下图：注：选择排序法与冒泡排序法排序在n个数据的总共比较次数均为n(n-1)/2次。3.算法：Procedure SELSORT(R, n) for iß1 to n-1 do kßi for jßi+1 to n do if kj<kk then kßjend ifend forif ik

9、then tempßRi RißRk Rkßtemp end if end forend SELSORT注：选择排序法与冒泡排序法在做法上最大的不同点是：选择排序法每一次循环最多只有两个数据做交换，而冒泡排序法每一次循环最少有两个数据做交换。另外，冒泡排序法在最佳情况下，即数据已经是由小到大的顺序，只需n-1次的比较，在最差情况下，才需n(n-1)/2次的比较。但选择排序法不管是在最佳或最差的情况下，均需n(n-1)/2次的比较。三、插入排序法（Insertion Sort）1.方法：在i个排序好的记录R1，R2，R3，Ri中 (K1K2K3Ki )，插入一笔新的

10、记录，产生i+1个已排序好的数据，属于稳定排序法。2.说明：试以插入排序（insertion sort ）来重新排序以下数据。4，7，11，8，6，17，3，7+首先在整笔数据的前加入一个-以方便处理，过程如下：-4711861737+Pass1:-4711861737+Pass2:-4711861737+Pass3:-4711861737+Pass4:-4781161737+Pass5:-4678111737+Pass6:-4678111737+Pass7:-3467811177+Pass8:-34677+811173.算法：Procedure INSORT(R, n) k0ß f

11、or jß2 to n doTßRjcall INSERT(T, j-1) end forend INSORTProcedure INSERT(R, i) while k<ki doRi+1ßRiißi-1 end while Ri+1ßREnd INSERT3.下列有关插入排序（Insertion Sort）的叙述，哪一个错误？(A) Insertion Sort在最坏情况需要O(n2)的时间。(B) Insertion Sort在最佳情况可在O(n)内完成。(C) Insertion Sort平均需要O(n log n)的时间。(D)

12、 Insertion Sort的效率由输入数据的Left-Out-of-Order决定。 88年高考一试【答案】 （C）【解析】 Insertion Sort平均需要O(n2)的时间，故选(C)。四、归并排序法（Merge Sort）1.方法：将原来的归并段视为n个已分类好长度为1的小归并段，接着两两归并成为n/2个已分类好长度为2的归并段，一直重复如此动作，最后剩下一个归并段时排序就完成了，属于稳定排序法。步骤如下：步骤1：有n个长度为1的归并段，归并成为n/2个已排序好且长度为2的归并段。步骤2：有n/2个长度为2的归并段，归并成为n/4个已排序好且长度为4的归并段。步骤i：有n/2i-1

13、个长度为2i-1的归并段，归并成为n/2i个已排序好且长度为2i的归并段。2.说明：使用归并排序法（Merge Sort）来排序以下数据。11，8，14，7，6，8+，23，43.算法：Procedure MERGESORT(A, p, r) if p<r thenqß MERGESORT(A, p, q) MERGESORT(A, q+1, r) MERGE(A, p, q, r) end ifend MERGESORT Procedure MERGE(A, p, q, r) nextßp p1ßp p2ßq+1 while qp1 and rp

14、2if Ap1>Ap2SAVEnext ß Ap2p2ßp2+1elseSAVEnext ß Ap1p1ßp1+1end ifnextßnext+1 end while if qp1SAVEnext.rßAp1.q elseSAVEnext.rßAp2.r end if Ap.r ßSAVEp.rend MERGE注：归并排序法需要一个和要排序归并段大小一样的额外空间才能执行，在算法中出现的SAVE数组就是这样的用途。4.令n为数据笔数，则Merge Sort所需的时间复杂度为(A) O(n log n)(B

15、) O(n2)(C) O(log n)(D) O(n)。 87年二技管四【答案】 （A）【解析】 归并排序法的时间复杂度为O(n log n)，故选(A)。5.一整数序列26，59，77，31，51，11，19，42以merge sort排序第一阶段（pass）的归并结果为：(A) 31，51，11，42，26，77，59，19(B) 26，59，31，77，11，51，19，42(C) 11，19，26，31，42，59，51，77(D) 26，11，19，31，51，59，77，42。 83年二技管二【答案】 （B）【解析】 pass1：26，59，31，77，11，51，19，42pas

16、s2：26，31，59，77，11，19，42，51pass3：11，19，26，31，42，51，59，77故选(B)。6.请回答下列问题：(一) 输入8个整数存于数组（Array）中，其顺序为8，6，1，3，5，2，4，7。说明利用归并排序法（Mergesort）将上列八个元素排序的每一步过程。(二)若排序的数据为接近排序完成（Almost Sorted），则归并排序是否为一适合此类数据的排序方法？请说明的。88年关务【解析】 (一) (二)归并排序并不合适，因为归并排序对接近排序完成的数据并没有好处，其排序仍然需要O(n log n)时间。此时较适合使用插入排序、冒泡排序等方法，可以用接

17、近O(n)的速度完成。五、快速排序法（Quick Sort）1.方法：步骤一：取第一个记录的键值Km当作虚拟中间值。步骤二：由左而右，i = 2, . , n+1找到第一个KiKm，且由右而左，j = n, n-1, . ,1，找到第一个KjKm。步骤三：若i<j则Ri与Rj对调位置，否则Rm与Rj对调位置，将此归并段一分为二：（R1, R2, . , Rj-1）Rj（Rj+1, Rj+2, . , Rn），如此两个子归并段再重复执行步骤一到步骤三。2.说明：利用快速排序法排序以下的十个记录，其键值分别为：26，5，37，1，61，11，59，15，48，19。R1R2R3R4R5R6R

18、7R8R9R10265371611159154819ijR3与R10对调mijR1R2R3R4R5R6R7R8R9R10265191611159154837ijR5与R8对调mijR1R2R3R4R5R6R7R8R9R10265191151159614837ijR1与R6对调mji115191152659614837此时在26的左半部的键值皆比26小，而右半部皆比26大，全部排序过程如下所示：R1R2R3R4R5R6R7R8R9R10265371611159154819115191152659614837151119152659614837151119152659614837151115192

19、6596148371511151926483759611511151926374859611511151926374859613.流程图：4.算法：Procedure QSORT(m, n) if m<n then ißm jßn+1 kßkm loop repeat ißi+1 until KiK repeat jßj-1 until KjK if i<j then call CHANGE(Ri, Rj) else exit end if forever call CHANGE(Rm, Rj) call QSORT(m, j-1)

20、 call QSORT(j+1, n) end ifend QSORT Procedure CHANGE(R, S) tempßR RßS SßtempEnd CHANGE注：Quick Sort是平均执行时间最快的排序法，平均情况下的时间复杂度为O(n log n)，但最坏情况下的时间复杂度为O(n2)。Quick Sort属于不稳定排序法。7.利用快速排序法（quick sort）将n笔数据排序，在最差情况其时间复杂度（time complexity）为：(A) O(n2)(B) O(log2 n)(C) O(n)(D) O(1)。 87年高考一试【答案】 （

21、A）【解析】 快速排序法在最坏情况下其时间复杂度为O(n2)，故选(A)。8.快速排序法（quick sort）采用下列何种策略：(A) 分治（divide and conquer）。(B) 贪心方法（greedy method）。(C) 动态规划（dynamic programming）。(D) 回溯（back tracing）。87年高考一试【答案】 （A）【解析】 Divide and conquer：将问题分成独立的N个小问题，再把分别处理的各个小问题的解归并成完整的解答，故选(A)。9.拟以快速排序法（quick sort）将下述表（list）由小到大排序：Carol，Bob，Ali

22、ce，Peter，John。假若经过一趟后，此表的次序为(A) Carol，Alice，Bob，Peter，John。(B) Carol，Alice，Bob，John，Peter。(C) Alice，Bob，Carol，Peter，John。(D) Bob，Carol，Alice，Peter，John。【答案】 （C）【解析】 故选(C)。10.Show that quicksort is an unstable sorting method.87年交大资科所【解析】 若原始数据为7, 4, 14, 8, 6, 11, 8+, 5，则快速排序法步骤如下：因为8原来在8+的前，但经快速排序法的后

23、，8反而在8+的后，故快速排序法是不稳定排序法。Step 1：64578118+14Step 2：54678118+14Step 3：45678118+14Step 4：45678+81114Step 5：45678+8111411.Explain the term "quicksort", show how quicksort works by applying it to the following data:6, 1, 8, 2, 4, 3, 10, 9, 7, 589年清大资科所【解析】 R1R2R3R4R5R6R7R8R9R10mn6182431097511031

24、5246109781521354610978121235461097845123456109787101234568971079123456789107712345678910991234567891012.Show that quicksort algorithm takes O(n2) time when the input file is already in sorted order.【解析】 T(n)cn+T(n-1)cn+(cn+T(n-2)2cn+T(n-2)3cn+T(n-3)(n-1)cn+T(1)= O(n2)13.使用Quick Sort的方法来排序数据时，何种情况下会产

25、生最坏情况？（比方说数据是In Reverse Order等）试证明你的答案。82年交大资管所，84年高考【解析】 快速排序（Quick Sort）是指在n个记录R1, R2, . , Rn的归并段中把键值k的记录放在S(i) 的位置上，则kjks(i) 当j< S(i)且kjks(i) 当j> S(i)；经此放置后，该归并段被分为两个部份归并段为(R1, R2, . , RS(i)-1) R S(i) (R S(i)+1, . , Rn)RS(i)的位置从此固定，而其左右的两个归并段可以分别再被排序。综合言的，其步骤如下：(1) 取第一个记录的键值k当作虚拟中间值。(2) 由左向

26、右找到第一个kik，i = 2, 3, . , n 且由右向左找到第一个kjk，j = n, n-1, . ,1。(3)若i<j则将Ri与Rj的位置对调并回到(2)，否则R与Rj的位置对调，将此归并段一分为二（R1, R2, . , RS(i)-1）R S(i)（R S(i)+1, . , Rn）如此这两个归并段可独立执行(1)到(3)步骤，直到完成排序。快速排序法在最坏情况下其时间复杂度为O(n2)。当数据已经完全由小到大或者由大到小排列时，则每次一分为二时，被分割的归并段大小为0与n-1个数据，从此继续处理大小为n-1的归并段，如此反复执行n-1次，而每次执行比较的时间最多为O(n)

27、；因此，在最坏的情况下，亦即数据已经由大到小或者由小到大排列时，快速排序法的时间复杂度为O(n2)。亦即T(n)cn+T(n-1) cn+c(n-1)+T(n-2) cn+c(n-1)+c+T(0) =c*(n(n+1)/2)= O(n2)14.Give a worst case input sequence for the quicksort algorithm.86年东吴转学考，87年辅大转学考【解析】 当输入的记录顺序是由大到小排列时，会产生最坏情况。例如输入顺序是5，4，3，2，1时。15.请以C语言或类似语法写一个Quick Sort的子程序，自行定义输入参数，需以递归的方式表示。

28、88年中原资管所【解析】 void quick_sort(int array, int left, int right) int mid； if (left<right) mid=partition(array, left, right); quick_sort(array, left, mid-1); quick_sort(array, mid+1, right); void partition(int array, int left, int right) int i, j, temp, pivot; pivot=arrayleft; do for(i=left+1;arrayi &

29、gt;= pivot;i+) for(j=right;arrayj <= pivot;j+) if(i<j)temp=arrayi;ai=aj;aj=temp; while(i<j); aleft=aj;aj=pivot; return(j); 六、堆排序法（Heap Sort）1.堆树的定义：是一个完全二叉树（complete binary tree）。每一个节点的值大于等于其子节点的值。2.方法：步骤一：建立一个完全二叉树。步骤二：将完全二叉树化成堆树。步骤三：将树根和最后一个节点对调，再做调整，重复步骤二及步骤三，直到只剩下一个节点为止。3.说明：数组中的数据如下： 使

30、用heap sort来排序此数据。【解析】 建立一(1)完全二叉树。（依照数据顺序编排成完全二叉树）(2)将完全二叉树调整成堆树。(3)做heap tree排序（由小à大）。4.算法： Procedure HEAPSORT(A) call BUILDHEAP(A) for ißlength(A) downto 2 do A1 Ai heapsizeßheapsize-1 call HEAPIFY(A, 1) end for end HEAPSORT Procedure BUILDHEAP(A) heapsizeßlength(A) for iß

31、 downto 1 do call HEAPIFY(A, i) end for end BUILDHEAP Procedure HEAPIFY(A, i) lßLEFT(i)rßRIGHT(i)if lheapsize and Al>Ai then largestßlelse largestßiend ifif rheapsize and Ar>Alargest then largestßrend ifif largesti thenAi AlargestCall HEAPIFY(A, largest)end if end HEAP

32、IFY Procedure LEFT(i) return 2i end LEFT Procedure RIGHT(i) return 2i+1 end RIGHT注：(1)堆树可分为最大堆树（Max Heap）与最小堆树（Min Heap）两种，完全视各子树的根（root）在子树中是最大值或最小值而定。例如一数组的数据为： 则对应（建立）的最大堆树及最小堆树分别为：(2)建立堆树的方式可分为两种：一种是先将全部的数据存入一个数组，亦即先建立一个完全二叉树（complete binary tree），然后再将此完全二叉树调整成一最大堆树或最小堆树。另一种就是将数据一次一个地加入最大堆树或最小堆树

33、中，即一边加入数据一边做调整的方式。例如数据为：5，8，2，6，4，1，3，7，分别以数组及一次一个数据的加入方式来建立最小堆树的过程如下：(一) 数组的方式：1. 建立一个完全二叉树。2. 将完全二叉树调整成最小堆树。(二)一次一个数据的加入方式：1. 加入5。 2. 加入8。3. 加入2。 4. 加入6。5. 加入4。6. 加入1。 7. 加入3。8. 加入7。16.令n代表数据笔数，则heap sort的时间复杂度为(A) O(log n)(B) O(n)(C) O(n log n)(D) O(n2)。 83年二技管理【答案】 (C）【解析】 n笔数据需要作(n-1)次对调，每次对调需要

34、调整二叉树成堆树，调整二叉树需要从树根一直比较到树叶，所需要比较次数为二元数的高度log n，因此共需要的比较次数为O(n log n)，故选(C)。17.以下哪一个用heap处理，较有效率。(A)priority queue(B)k-way merge(C)depth first search(D)breadth first search。82年二技管理【答案】 （A）【解析】 树根节点的值为最大，当使用priority queue时，树根节点的优先级最大，故选(A)。18.将5、4、3、2、1依次插入空的min-heap，则heap内容依次为：(A)12453(B)12345(C)1325

35、4(D)13245。 88年二技管理【答案】 （A）【解析】 1. 插入5。 2. 插入4。3. 插入3。4. 插入2。5. 插入1。 因此最后结果为：故选(A)。19.Store the numbers 30, 12, 9, 8, 6, 2, 3 in a min-heap tree in that order. Which of the following array represents this min-heap tree.(A) A1=2, A2=6, A3=3, A4=12, A5=8, A6=9, A7=30.(B) A1=2, A2=8, A3=3, A4=30, A5=9,

36、A6=12, A7=6.(C) A1=2, A2=3, A3=6, A4=8, A5=9, A6=12, A7=30.(D) A1=2, A2=6, A3=3, A4=30, A5=8, A6=9, A7=12.87年交大资科所【答案】 （B）【解析】 最后结果为：20.设要排序（Sort）的数据为：5, 1, 10, 2, 15, 3，若采用堆排序法（Heap Sort），则当堆树（Heap tree）第三次建成时，其树根节点数据内容是：(A)3(B)10(C)15(D)5。【答案】 （D）【解析】 1. 建立一个完全二叉树（complete binary tree）：2. 将完全二叉树调整

37、成最大堆树。3. 做Heap Sort因此第三次建成时，树根节点数据内容为5，故选(D)。21.下列那一个二叉树（Binary）是最小堆树（Minimum heap）？(A)(B)(C)(D)【答案】（C）【解析】 最小堆树：(1)是一个完全二叉树。(2)每个节点的键值小于等于其子节点的键值。22.下图为一最大堆（max heap），求插入其值为13的节点（node）后的结果？依阶度顺序（level order）列出：(A) 14，13，12，10，8，7，6(B) 14，12，13，10，8，6，7(C) 14，13，12，10，8，6，7(D) 14，12，13，10，8，7，6 87年高

38、考一试【答案】（B）【解析】故选(B)。23.试以下列数据26，73，15，42，39，7，92，84说明堆排序（heap sort）的过程。【解析】 Step 1：建立完全二叉树。Step 2：将二叉树化成堆树。Step 3：将树根和二叉树的最后节点调换，再作调整。Step 1：Step 2：Step 3：在数组中的结果为：24.(1) 何谓堆（heap）？(2) 为什么有n个元素即可知堆可完全存在大小为n的数组中？(3) 将下图中的堆表示为数组。(4) 将88移去后，则该堆变为如何？(5) 若将100插入(3)的堆，则该堆变为如何？【解析】 (1)1. 堆是一个完全二叉树。2. 每个节点的

39、键值大于等于其子节点的键值。(2)完全二叉树可以照顺序存入一维数组中。PARENT(i) = LCHILD(i) = 2i，RCHILD(i) = 2i +1(3)A： 1 2 3 4 5 6 7 8 9 10 11 12 88 45 65 30 28 58 55 29 5 1 8 20(4)(5)25.最小堆树(min heap)是一完全二叉树(complete binary tree)，且是最小树(min tree)，最小树的定义是一个节点(node)的键值(key value)不可大于它的儿子(如果有儿子的话)的键值。考虑将下面的最小堆树去掉(delete)键值为"9"

40、;的节点，而仍保持为一最小堆树，试绘出结果。【解析】 Step 1：将节点9删除。Step 2：将最后的节点28移至树根。Step 3：再作调整的工作。七、基数排序法(Radix Sort)1.方法：将含有相同位数键值数据置于同一个桶(bucket)，由基数p来决定要几个桶，若有n组数据，则需要有n×p个位置。排序过程可采用LSD(Least-Significant Digit)从右边位数开始往左边依次比较。2.说明：使用基数排序法(Radix Sort)来排序以下数据：11，7，4，123，31，88，349，9，31+，18若用LSD来处理共有10个数字，以十进制为基底，且位数最

41、多为三位，因此n = 10，p = 10，共需执行三次分配与归并。(1)先以个位数做分配：Pass1:bucketcontent0111, 31, 31+23123bucketcontent454677888, 189349, 9 归并后顺序为：11, 31, 31+, 123, 4, 7, 88, 18, 349, 9(2)再以十位数做分配：Pass2:bucketcontent04, 7, 9111, 182123331, 31+43495678889归并后顺序为：4, 7, 9, 11, 18, 123, 31, 31+, 349, 88(3)最后以百位数做分配：Pass3:bucket

42、content04, 7, 9, 11, 18, 31, 31+, 88112323349456789归并顺序为：4, 7, 9, 11, 18, 31, 31+, 88, 123, 349注： 基数排序法是一个稳定排序法。 基数排序法需要一个很大的额外空间O(n ×p)才能执行。 其在平均情况下的时间复杂度为O(n logp K)，1Kp，而在最坏情况下的时间复杂度为O(n logp K) O(n)。八、各种内部排序法汇总 itemtypenameaverage timeworst timestabilityextra spacerequiredSimpleBubbleO(n2)O

43、(n2)stableO(1)SelectionO(n2)O(n2)unstableO(1)InsertionO(n2)O(n2)stableO(1)AdvanceMergeO(n log n)O(n log n)stableO(n)QuickO(n log n)O(n2)unstableO(log n) O(n)HeapO(n log n)O(n log n)unstableO(1)RadixRadixO(n logpK)O(n logp K) O(n)stableO(n × p)26.若以计算机处理桥牌比赛四位比赛者手持牌张的数据，并将个人所持牌花色与牌点予以排序(花色大小为：梅花

44、<方块<红心<黑桃，牌点大小为2<3<4 <9<10<J<Q<K<A)(一)请问如要用基数排序法(Radix sort)来排序，则需要使用那种数据结构，数量多少？(二)要排序几次(pass)才会完成。并说明的。88年残障【解析】 (一)需要利用队列(queue)做为存放的bin，其中在排列花色时需要4个bin，排列牌点时需要13个bin，由于bin可以共享，因此总共需要13个队列。(二) 因为有两个digit，因此只要2个pass就会完成。27.(1)一个排序法常会讨论其是否稳定(Stable)，请说明何谓稳定的排序。(2)下列

45、排序法是基数排序法(Radix Sort)，或称分配式排序法(Distribution Sort)请问其是否为稳定的排序法。1.输入：要排序的数据记录。2.输出：已排序的数据记录。3.变量：队列C(Queue)：QUEUE0，QUEUEr(存于中间结果)M：键值的位数。4.处理程序：重复下列步骤M次：由最小有效位数起至最大有效位数止。依每一有效位数的值J，放于队列QUEUE。重新组合数据列，QUEUE0中数据在前，QUEUE1至QUEUEr中数据依次排在其后。(3)稳定性(Stability)有何用处？【解析】 1.归并段中若存在有几个相同大小的Key值，经过排序后仍保持原有的次序。2.基数排

46、序为稳定的排序法：【例如】：使用基数排序法，将下列键值的数据录由小到大排序：7，11，15，11+。使用个位数排序如下：bucketcontent0111，11+23451567789整理的结果如下：11，11+，15，7使用十位数排序如下：bucketcontent07111，11+，1523456789最后结果为：7，11，11+，153.相同key的记录具有不同的副key，副key的次序不会被破坏。7-3二叉树排序1.方法：二叉树排序即先将所有的数据建成二叉树，再利用中序法来遍历。步骤如下：步骤一：将第一个数据放在树根。步骤二：然后输入的数据皆与树根做比较；若比树根大，则置于右子树，反之，置于左子树，重复步骤二，直到全部的数据均加入到二叉树为止。步骤三：二叉树建立完