《计算机组成与结构：DS and AL_Lecture9_sorting》由会员分享，可在线阅读，更多相关《计算机组成与结构：DS and AL_Lecture9_sorting（83页珍藏版）》请在金锄头文库上搜索。
1、DATA STRUCTURES ANDALGORITHMSLecture 9 Sortingbuptsse2ROAD MAPSORTINGWhat is sortingInserting SortingInsertion sort Shell sortExchange SortingBubble sort QuickSort Selection SortingSelection Sort HeapSortMergeSort Radix Sort (Bucket Sort)3Sorting ProblemSorting: For a given list of records (R1, R2,
2、, Rn), where Ri = Ki + data, arrange the elements so that they are inascending order K1 = K2 ,= . = K2 =.= KnAn ordered list is a list in which each entry has a key, and the keys are in order.Stable: if i j and Ki = Kj and Ri precedes Rj in the sorted list, then the sorting algorithm is stable.4inte
3、rnal sort vs. external sortCategories:Insertion sort and Shell sort（插入排序）Bubble sort and QuickSort（交换排序）Selection Sort and HeapSort（选择排序)MergeSort and Bucket SortSome O(n2) sorting schemeseasy to understand and to implementnot very efficient, especially for large data sets5Criteria:To analyze sortin
4、g algorithms, we consider both the number of comparisons of keys and the number of times entries must be moved inside a list, particularly in a contiguous list.# of key comparisons# of data movementsBoth the worst-case and the average performance of a sorting algorithm are of interest. To find the a
5、verage, we shall consider what would happen if the algorithm were run on all possible orderings of the list.6Sortable Lists Structure of data element typedef struct int key; /表示排序关键字 elemtype otherinfo; /排序记录中的其他数据项 Snode; Structure of sortable listtypedef struct Snode RMaxsize+1; /存放待排序全体记录 int len
6、gth; /排序记录个数 SList; 7ROAD MAPSORTINGWhat is sortingInsertion SortingInsertion sort Shell sortExchange SortingBubble sort QuickSort Selection SortingSelection Sort HeapSortMergeSort Radix Sort (Bucket Sort)8Insertion SortingInsertion Sorting1) Basic idea: Insertion sorts are based on the process of r
7、epeatedly inserting a new element into already sorted list.The list is regarded as two parts: a sorted sublist and a un-sorted sublist. In initially,the sorted sublist is R1, un-sorted sublist is R2.Rn,and i references the first element of un-sorted sublist.When i i n n repeat: the first element of
8、un-sorted sublist-Ri is inserted into its proper position among the already sorted list R1, R2 ,., Ri-19At the i- th stage, Ri is inserted into its proper position among the already sorted R1,R2 ,.,Ri-1.Compare Ki with each of these elements, starting from the right end, and shift them to the right
9、as necessary. Use array position 0 to store a copy of Ki to prevent “falling off the left end” in these right-to-left scans. 10Example:2121252525*25*161608081 2 3 4 5 6 1 2 3 4 5 6 temp212125494925*25*161608082525i = 21 2 3 4 5 6 temp212125254925*25*161608084949i = 349490 position as temp11212125254
10、94925*161608081 2 3 4 5 61 2 3 4 5 6 temp21212525494925*25*160808i = 51 2 3 4 5 6 temp21212525494925*25*161608i = 6i = 425*25*1616080821212525494925*25*161608081 2 3 4 5 6Finish121649161616161 2 3 4 5 6 temp21212525494925*25*08081 2 3 4 5 6 temp21212525494925*25*161608081616i = 5j = 4i = 5j = 3 Thes
11、ortingprocesswheni=5132525*1616161621212525494925*25*08081 2 3 4 5 61 2 3 4 5 6 temp2121494925*25*08081 2 3 4 5 6 temp212525494925*25*161608081616161625252121i = 5j = 2i = 5j = 1i = 5j = 0161614 3）Alogrithm： void InsertSort(SqList &L) for(i=2；i=L.length；i+)if(L.Ri.key L.Ri-1.key) /小于时小于时,将将Ri插入有序表插入
12、有序表 L.R0 =L.Ri； / R0 is a sentinel for( j=i-1；L.R0.key binary searchreduce # of comparisons, # of moves unchangedList insertion sortarray - linked listsequential search, move - 017ROAD MAPSORTINGWhat is sortingInserting SortingInsertion sort Shell sortExchange SortingBubble sort QuickSort Selection
13、SortingSelection Sort HeapSortMergeSort Radix Sort (Bucket Sort)18Shell Sort1) Basic idea: group the list into several sublist and apply insertion sort in each sublist. Continue in this manner, finally apply insertion sort to all records.First, group the list into several sublist by interval d d1App
14、ly insertion sort in each sublist.Group the list again by interval d d2(d(d2dd1n), n), and apply insertion sort in each sublist.Continue in this manner, until d dt t=1=1. .191-sort grouping ：13 4 49 38 27 49 55 65 97 761-sorted ：4 13 27 38 49 49 55 65 76 97Example： 49 38 65 97 76 13 27 49 55 45-sort
15、ed ：13 27 49 55 4 49 38 65 97 765-sort grouping：49 38 65 97 76 13 27 49 55 43-sorted ：13 4 49 38 27 49 55 65 97 763-sort grouping ：13 27 49 55 4 49 38 65 97 7620At the very start of Shell sorting, d d is largerlarger and the size of each sublist is smallsmall. Insertion sort in every sublist is effi
16、cient. With d d become more smaller, the size of every sublist more larger, but the sublists become rough ordered. Insertion sort in every sublist is also efficient. How to determine d d :Shell: d d1 1= = n n/2/2 , , d di+1i+1= = d di i/2/2 , , d dt t = 1 = 1Knuth: : d di+1i+1= = d di-1i-1 /3/3 d dt
17、 t is prime number. In any case, d dt t = 1 = 1Shell Sort Algorithm21void ShellSort(SqList &L,int dlta,int t)void ShellSort(SqList &L,int dlta,int t) / / 按增量序列按增量序列按增量序列按增量序列dlta0.t-1dlta0.t-1对顺对顺对顺对顺序表序表序表序表L L作希作希作希作希尔尔尔尔排序。算法排序。算法排序。算法排序。算法.5 .5 int k; int k; for(k=0;kt;+k) for(k=0;kt;+k) ShellIn
18、sert(L,dltak); / ShellInsert(L,dltak); / 一趟增量一趟增量一趟增量一趟增量为为为为dltakdltak的插入排序的插入排序的插入排序的插入排序 printf( printf(第第第第%d%d趟排序趟排序趟排序趟排序结结结结果果果果: ,k+1);: ,k+1); print(L); print(L); Shell Sort Algorithm22void ShellInsert(SqList &L,int dk) void ShellInsert(SqList &L,int dk) / / 对顺对顺对顺对顺序表序表序表序表L L作一趟希作一趟希作一趟希作
19、一趟希尔尔尔尔插入排插入排插入排插入排/ /序。本算法是和一趟直接插入排序相比，序。本算法是和一趟直接插入排序相比，序。本算法是和一趟直接插入排序相比，序。本算法是和一趟直接插入排序相比， / / 作了以下修改：作了以下修改：作了以下修改：作了以下修改： / 1./ 1.前后前后前后前后记录记录记录记录位置的增量是位置的增量是位置的增量是位置的增量是dkdk，而不是，而不是，而不是，而不是1 1; ; / 2.r0 / 2.r0只是只是只是只是暂暂暂暂存存存存单单单单元，不是哨兵。当元，不是哨兵。当元，不是哨兵。当元，不是哨兵。当j=0j=0时时时时，插入位置已找到。算法，插入位置已找到。算法
20、，插入位置已找到。算法，插入位置已找到。算法.4 .4 int i,j; int i,j; for(i=dk+1;i=L.length;+i) for(i=dk+1;i0<(L.r0.key,L.rj.key);j-=dk) for(j=i-dk;j0<(L.r0.key,L.rj.key);j-=dk) L.rj+dk=L.rj; / L.rj+dk=L.rj; / 记录记录记录记录后移，后移，后移，后移，查查查查找插入位置找插入位置找插入位置找插入位置 L.rj+dk=L.r0; / L.rj+dk=L.r0; / 插入插入插入插入 Shell Sort Algorithm232)
21、 Analysis:2) Analysis:Time Complexity:Time Complexity:n n1.25 1.25 1.6 1.6n n1.251.25 Space ComplexitySpace Complexity : : O(1)O(1)Shell Sorting is not Shell Sorting is not stable.stable.24ROAD MAPSORTINGWhat is sortingInserting SortingInsertion sort Shell sortExchange SortingBubble sort QuickSort S
22、election SortingSelection Sort HeapSortMergeSort Radix Sort (Bucket Sort)25Exchange SortingExchange sorts systematically interchange pairs of elements that are out of order until eventually no such pairs remain = list is sorted. One example of an exchange sort is bubble sort: very inefficient, but q
23、uite easy to understand.26Bubble Sort1) Basic idea:On the first pass: compare the first two elements, and interchange them when they are out of order. Next compare the second and third elements until compare the last two elements. The largest element in the list will “sink” to the end of the list, s
24、ince it will obviously be moved past all smaller elements. Some of the smaller items have “bubbled up” toward their proper positions nearer the front of the list.Scan and compare the list again, leaving out the last item (already in its proper position).Repeat it until there is not out of order in t
25、he list.2721212525494925*25*161608081 2 3 4 5 6212125*25*i = 1= 1252525251616ExchangExchang=1=12121ExchangExchang=1=1i = 2= 20808494908081616494925*25*Bubble Sort ExampleExample281 2 3 4 5 6i = 4= 4ExchangExchang=0=021211616080825*25*49492525i = 3= 3ExchangExchang=1=121211616080825*25*4949252529void
26、 bubble_sort(int a,int n) / 将将a中整数序列重新排列成自小至大有序的整数序列中整数序列重新排列成自小至大有序的整数序列(起泡排序起泡排序) int i,j,t; Status change; for(i=n-1,change=TRUE;i1&change;-i) change=FALSE; for(j=0;jaj+1) t=aj; aj=aj+1; aj+1=t; change=TRUE; Bubble Sort AlgorithmAlgorithm303) Analysis3) AnalysisTime ComplexityTime Complexity ：Bes
27、t case(when the list is already in order): Only n-1 comparisons and no element move. Worse case(when the list is in reverse order)Comparisons of keys: Move element:Space ComplexitySpace Complexity： O(1)O(1)Bubble Sorting is Bubble Sorting is stable.stable.O(O(n n2 2) )31ROAD MAPSORTINGWhat is sortin
28、gInserting SortingInsertion sort Shell sortExchange SortingBubble sort QuickSort Selection SortingSelection Sort HeapSortMergeSort Radix Sort (Bucket Sort)32QuickSortA more efficient exchange sorting scheme than bubble sort because a typical exchange involves elements that are far apart fewer interc
29、hanges are required to correctly position an element.331) Basic ideaQuicksort uses a divide-and-conquer strategya recursive approach to problem-solving in which the original problem partitioned into simpler sub-problems,each subproblem considered independently. Subdivision continues until subproblem
30、s obtained are simple enough to be solved directlyChoose some element called a pivot. Perform a sequence of exchanges so that all elements that are less than this pivot are to its left and all elements that are greater than the pivot are to its right. divides the (sub)list into two smaller sublists,
31、 each of which may then be sorted independently in the same way. 34QuickSortIf the list has 0 or 1 elements, return. Else do:Pick an element in the list to use as the pivot.Split the remaining elements into two disjoint groups:SmallerThanPivot = all elements pivotReturn the list rearranged as: Quick
32、sort(SmallerThanPivot), pivot, Quicksort(LargerThanPivot) 35Partitioning strategyInitial: 49 38 65 97 76 13 27 49 i jAfter Step1: 27 38 65 97 76 13 49 i i jAfter Step2: 27 38 97 76 13 65 49 i jAfter Step3: 27 38 13 97 76 65 49 i i jAfter Step4: 27 38 13 76 97 65 49 i j jPivot Key 49 (temp)36Partitio
33、ning strategyFinish one Time sort: 27 38 13 49 76 97 65 49 Initial: 49 38 65 97 76 13 27 49 One timePartitioning : 27 38 13 49 76 97 65 49 Individual Quick sort: 13 27 38 49 65 76 97Final soerted: 13 27 38 49 49 65 76 97 37int Partition (RedType R, int low, int high) / Partition R0 = Rlow; pivotkey
34、= Rlow.key; / pivot while (lowhigh) while(low=pivotkey) - high; / From right to leftRlow = Rhigh;while (lowhigh & Rlow.key=pivotkey) + low; / From left to rightRhigh = Rlow;Rlow = R0; return low;QuickSort Algorithm38void QSort (RedType & R, int s, int t ) / Quick sort Rs.t if (s t) / length is more
35、then 1 / QSortpivotloc = Partition(R, s, t); / first time partitioning Rs.t QSort(R, s, pivotloc-1); / For low sequence sorting，pivotloc is pivot positionQSort(R, pivotloc+1, t); / Quick sort high sequenceQuickSort Algorithm39void QuickSort( SqList & L) / Sorting sequence table QSort(L.r, 1, L.lengt
36、h); / QuickSort first time call QSort FunctionQuickSort Algorithm40Quick sort algorithm AnalysisQuick sort algorithm AnalysisTime complexity ：Best case: Always partition in half. Position a list with n element needs O(n). T(n) is the time taken to sort n elements T(n)=cn+2T(n/2) for some c =cn+2(cn/
37、2+2T(n/4) . 1 2 2)Optimizations for Quicksort:Better PivotFirst or last entry: Worst case appears for a list already sorted or in reverse order.Central entry: Poor cases appear only for unusual orders.Random entry: Poor cases are very unlikely to occur.Better algorithm for small sublistsEliminate re
38、cursionQuick sort algorithm AnalysisQuick sort algorithm Analysis42ROAD MAPSORTINGWhat is sortingInserting SortingInsertion sort Shell sortExchange SortingBubble sort QuickSort Selection SortingSelection Sort HeapSortMergeSort Radix Sort (Bucket Sort)43Selection SortingBasic idea: make a number of p
39、asses through the list or a part of the list and, on each pass, select one element to be correctly positioned.44Selection SortBasic idea: The list is regarded as two parts: a sorted sublist and a un-sorted sublist. In initially,the sorted sublist is , un-sorted sublist is R1,R2.Rn.In each pass, the
40、smallest element in the un-sorted sublist might be found and then moved to its proper location.Continue in this manner. After n-1 times selection and insertion, the list is in order.45At the i- th stage, the sorted sublist is R1,R2.Ri-1 , un-sorted sublist is Ri,Ri+1.Rn. Scan the unsorted sublist to
41、 locate the smallest element and find it in position. Interchange this element with the ith element (Ri).4621212525494925*25*161608081 2 3 4 5 6212125*25*i = 1= 14949252516162525161608084949080825*25*49492121i = 2= 2i = 3= 30808161625*25*25252121InitializationInitializationsmallest 08Interchange 21,
42、08smallest 16Interchange 25,16smallest 21Interchange 49,2147494925*25*1 2 3 4 5 625*25*i = 5= 5252516160808494925*25*49492121Finishi = 4= 40808161625252121smallest 25*No Interchangesmallest 25No Interchange2525212116160808482) Analysis2) AnalysisTime complexity ：Movement of elementsBest case: 0Bad c
43、ase: 3(n-1)Comparison: On the first pass through the list, the first item is compared with each of the n - 1 elements that follow it; On the second pass, the second element is compared with the n - 2 elements following it, etc.A total of (n-1) + (n-2) + + 1 = (n*(n-1)/2 comparisons thus required for
44、 any listSpace complexity: O(1)Selection Sort is not stable(2 2 1 - 1 2 2).O(O(n n2 2) )49ROAD MAPSORTINGWhat is sortingInserting SortingInsertion sort Shell sortExchange SortingBubble sort QuickSort Selection SortingSelection Sort HeapSortMergeSort Radix Sort (Bucket Sort)50Heaps and HeapSort1) Wha
45、t is a heap?Definition: A heap is a list (R1,R2.Rn), in which each entry contains a key, (K1,K2.Kn), and every Ki in the list satisfies:OR(i=1,2,. n/2 )kik2ikik2i+1kik2ikik2i+151E.g.(96,83,27,38,11,9）E.g.(13,38,27,50,76,65,49,97)962791138831327384965765097Aheaplistcanberegardasacompletebinarytree.Th
46、erootofthetreemustbethelargest(smallest)elementinthelist.MinHeapMaxHeap52Basic idea:Basic idea:The list is regarded as two parts: a sorted sublist and a un-sorted sublist. In initially,the sorted sublist is , un-sorted sublist is R1,R2.Rn.Regarding the un-sorted list R1,R2.Rn as a complete binary tr
47、ee stored in an array, and convert the complete binary tree to a heap. The root of the tree, R1, is the largest (smallest) element in the list. Swap R1 with the end element of the un-sorted sublist Ri, and put it into sorted sublist. Convert the un-sorted sublist R1,R2.Ri-1 to a heap. Continue in th
48、is manner, until the un-sorted sublist is empty. 2) HeapSort53The difficultiesThe difficulties：How to convert a complete binary tree to a heap？ Build Heap Build HeapAfter elements swapping, how to convert the un-sorted sublist R1,R2.Ri-1 to a heap? Heap Adjust Heap AdjustSolution of the second probl
49、emSolution of the second problemPercolate-Down(Percolate-Down(向下向下过滤）过滤）54Apply the Percolate-Down algorithm to tree Apply the Percolate-Down algorithm to tree that root number from that root number from n/2n/2 to 1, and convert to 1, and convert these trees into heaps, respectively.these trees into
50、 heaps, respectively.The Percolate-Down algorithm is applied to The Percolate-Down algorithm is applied to nodes nodes n/2n/2 , , n/2n/2 -1,-1,1 1Down-UpDown-Up)BuildHeap552121252525*25*494916160808123456i2121252525*25*161649490808136542i21 25 49 25* 16 0821 25 49 25* 16 08Initial Keyword Set21 25 4
51、9 25* 16 0821 25 49 25* 16 08i i = 3, adjustment = 3, adjustment55BuildinitialMaxHeap4)HeapAdjustment562121252525*25*494916160808123456i4949252525*25*16162121080813654221 25 49 25* 16 0821 25 49 25* 16 0849 25 21 25* 16 0849 25 21 25* 16 08i = 1,adjustment,Final MaxHeapFinal MaxHeapi = 2, adjustment
52、56574949252525*25*2121161608081234560808252525*25*16162121494913654249 25 21 25* 16 0849 25 21 25* 16 0808 25 21 25* 16 08 25 21 25* 16 4949Exchange #1 with #6Exchange #1 with #6 Initial HeapInitial Heap5758252525*25*0808212116164949123456161625*25*080825252121494913654225 25* 21 08 16 25 25* 21 08
53、16 494916 25* 21 08 16 25* 21 08 25 4925 49Exchange #1 with #5Exchange #1 with #5Adjust #1 to #5 into Adjust #1 to #5 into MaxHeapMaxHeap585925*25*161608082121252549491234560808161625*25*25252121494913654225* 16 21 08 25* 16 21 08 25 4925 4908 16 21 08 16 21 25* 25 4925* 25 49Exchange #1 with #4Exch
54、ange #1 with #4Adjust #1 to #5 into Adjust #1 to #5 into MaxHeapMaxHeap 59602121161625*25*0808252549491234560808161625*25*25252121494913654221 16 08 21 16 08 25* 25 4925* 25 4908 16 08 16 21 25* 25 4921 25* 25 4960Exchange #1 with #3Exchange #1 with #3Adjust #1 to #3 into Adjust #1 to #3 into MaxHea
55、pMaxHeap 611616080825*25*2121252549491234560808161625*25*25252121494913654216 08 16 08 21 21 25* 25 4925* 25 490808 16 21 25* 25 4916 21 25* 25 4961Exchange #1 with #2Exchange #1 with #2Adjust #1 to #2 into Adjust #1 to #2 into MaxHeapMaxHeap 62Heap Sort AlgorithmvoidHeapSort(HeapType&H)for(i=H.leng
56、th/2;i0;i-)HeapAdjust(H,i,H.length);/把H.r1.H.length建成最大堆for(i=H.length;i1;i-)H.r1H.ri;/堆顶记录交换到H.r1.i的最后HeapAdjust(H,1,i-1);/把H.r1.i-1建成最大堆6263Adjustment AlgorithmtypedefSqListHeapType;voidHeapAdujst(HeapType&H,ints,intm)/已知H.rs.m中除H.rs外均满足堆定义,/本函数将H.rs.m调整为大顶堆.rc=H.rs;for(j=2*s;j=m;j*=2)/沿key较大的子结点向
57、下筛选if(jm&H.rj.key=H.rj.key)break;H.rs=H.rj;s=j;H.rs=rc;645) AnalysisTime complexity ：O(O(n nloglog2 2n n) )Space complexity: O(1)Heapsort is not stable.Heapsort is suitable only for contiguous lists.65ROAD MAPSORTINGWhat is sortingInserting SortingInsertion sort Shell sortExchange SortingBubble sort
58、 QuickSort Selection SortingSelection Sort HeapSortMergeSort Radix Sort (Bucket Sort)66Merge SortSorting schemes are internal-designed for data items stored in main memory external-designed for data items stored in secondary memory. Previous sorting schemes are all internal sorting:required direct a
59、ccess to list elements(not possible for sequential files)made many passes through the list(not practical for files)Mergesort can be used both as an internal and an external sort. basic operation is merging, that is, combining two lists that have previously been sorted so that the resulting list is a
60、lso sorted. 67 Given two sorted lists (listi, , listm) (listm+1, , listn)generate a single sorted list(sortedi, , sortedn)We chop the list into two sublists of sizes as nearly equal as possible and then sort them separately. Afterward, we carefully merge the two sorted sublists into a single sorted
61、list.1) Merge682) MergeSortBasic idea:If the list is (R1,R2.Rn), we chop(划分） the list into n sublists (the size of each sublist is 1), and perform merging for contiguous two sublist of them separately. We get n/2 sorted sublists one pass mergesortMerge the n/2 sorted sublists into a n/4 sorted list.
62、Continue in this manner, until merge the two sorted sublists into a single sorted list.69ExampleInitial Keys： 49 38 65 97 76 13 27After One time： 38 49 65 97 13 76 27After two times： 38 49 65 97 13 27 76Final： 13 27 38 49 65 76 9770lenlen=1=1lenlen=2=2lenlen=4=4lenlen=8=8lenlen=16=16713) AnalysisTim
63、e complexity ：O(nlogO(nlog2 2n)n)Space complexity: O(n)O(n) Mergesort requires twice the space.MergeSort is stable. Mergsort is also good for sorting linked lists.72ROAD MAPSORTINGWhat is sortingInserting SortingInsertion sort Shell sortExchange SortingBubble sort QuickSort Selection SortingSelectio
64、n Sort HeapSortMergeSort Radix Sort (Bucket Sort)73Bucket Sort (Radix Sort)1) Radix(基数): if the key k ki i of a record is consist of d d component k ki i1 1,k,ki i2 2, ,k ki id d , , and all k ki ij j come from the same domain, that is C C1 1 k ki ij j C Crdrd (1 (1 j d), j d), rdrd is called radix(
65、基数).E.g.: for decimal, rd=10 CE.g.: for decimal, rd=10 C1 1=0, C=0, C1010=9=9E.g.: for lowercase, rd=26 CE.g.: for lowercase, rd=26 C1 1= = a a , C, C1010= = z z 74Sorting with several keysExample: for cardSuits: Face values: 2 3 4 5 6 7 8 9 10 J Q K A2 3 4 5 6 7 8 9 10 J Q K A 2, , 2, , A, A, 2, ,
66、2, , A, A, 2, , 2, , A, A, 2, , 2, , A AThis is lexically sorted. R0,R1, Rn-1 are said to be sorted with respect to the keys K0, K1, , Kr-1 iffMSD (Most Significant Digit first):sort on K0, then K1, .LSD (Least Significant Digit first): sort on Kr-1, then Kr-2, .2) Radix Sort0in-175Initialize rd emp
67、ty bins.Distribute n into different bins based on the value of Kid. Then scan the non-empty bins, and collect the record to reestablish the list for the next pass.Repeat Repeat the the operations operations for for K Ki id-1d-1, , K Ki id-2d-2, , , , K Ki i1 1 , , until until after after the last th
68、e last “ “distribution” ” and and “ “collection” for K Ki i1 1. . BasicideaofRadixSort76ExampleInitialization:278109063930589184505269008083109589269278063930083184505008e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一一趟趟分分配配930063083184505278008109589269一趟收集：一趟收集：77505008109930063269278083184589二趟收集：二趟收集：
69、083184589063505269930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9二二趟趟分分配配008109278930063083184505278008109589269一趟收集：一趟收集：78008063083109184269278505589930三趟收集：三趟收集：109008184930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9三三趟趟分分配配063083269278505589505008109930063269278083184589二趟收集：二趟收集：793) AnalysisTime comp
70、lexity: O (O (rd *nrd *n ) )。Space complexity: O(O(n n+2+2rdrd) )Radix Sort is stable. 80Sorting Summary各种内部排序方法性能比较81Sorting Summary从依据的不同原则看，内部排序大致可分为：从依据的不同原则看，内部排序大致可分为：从依据的不同原则看，内部排序大致可分为：从依据的不同原则看，内部排序大致可分为：插入排序插入排序插入排序插入排序交换排序交换排序交换排序交换排序选择排序选择排序选择排序选择排序归并排序归并排序归并排序归并排序记数排序记数排序记数排序记数排序从时间复杂度看
71、，内部排序可分为：从时间复杂度看，内部排序可分为：从时间复杂度看，内部排序可分为：从时间复杂度看，内部排序可分为： (1)(1)(1)(1)简单排序方法简单排序方法简单排序方法简单排序方法( ( ( (包括直接插入排序、冒泡排序、选择排序包括直接插入排序、冒泡排序、选择排序包括直接插入排序、冒泡排序、选择排序包括直接插入排序、冒泡排序、选择排序) ) ) )，其时间复杂度为，其时间复杂度为，其时间复杂度为，其时间复杂度为O(nO(nO(nO(n2 2 2 2) ) ) )； (2)(2)(2)(2)先进的排序方法先进的排序方法先进的排序方法先进的排序方法( ( ( (包括堆排序、归并排序、快速
72、排序包括堆排序、归并排序、快速排序包括堆排序、归并排序、快速排序包括堆排序、归并排序、快速排序) ) ) )，其时间复杂，其时间复杂，其时间复杂，其时间复杂O(nlogO(nlogO(nlogO(nlog，n)n)n)n)；(3)(3)(3)(3)基数排序，其时间复杂度为基数排序，其时间复杂度为基数排序，其时间复杂度为基数排序，其时间复杂度为O(dO(dO(dO(dn)n)n)n)。 从空间复杂度看，内部排序可分为：从空间复杂度看，内部排序可分为：从空间复杂度看，内部排序可分为：从空间复杂度看，内部排序可分为： (1)(1)(1)(1)归并排序，其空间复杂度为归并排序，其空间复杂度为归并排序，
73、其空间复杂度为归并排序，其空间复杂度为O(n)O(n)O(n)O(n)； (2)(2)(2)(2)快速排序，其空间复杂度为快速排序，其空间复杂度为快速排序，其空间复杂度为快速排序，其空间复杂度为O(logO(logO(logO(log n)(n)(n)(n)(但在最坏情况下为但在最坏情况下为但在最坏情况下为但在最坏情况下为O(n)O(n)O(n)O(n)；(3)(3)(3)(3)其他排序方法，其空间复杂度为其他排序方法，其空间复杂度为其他排序方法，其空间复杂度为其他排序方法，其空间复杂度为O(1)O(1)O(1)O(1)。 4 4 4 4从稳定性看，内部排序可分为：从稳定性看，内部排序可分为：
74、从稳定性看，内部排序可分为：从稳定性看，内部排序可分为： (1)(1)(1)(1)稳定的排序方法稳定的排序方法稳定的排序方法稳定的排序方法( ( ( (包括直接插入排序，冒泡排序，归并排序包括直接插入排序，冒泡排序，归并排序包括直接插入排序，冒泡排序，归并排序包括直接插入排序，冒泡排序，归并排序) ) ) )； (2)(2)(2)(2)不稳定的排序方法不稳定的排序方法不稳定的排序方法不稳定的排序方法( ( ( (希尔排序、选择排序、快速排序、堆排序希尔排序、选择排序、快速排序、堆排序希尔排序、选择排序、快速排序、堆排序希尔排序、选择排序、快速排序、堆排序) ) ) )。利用序列。利用序列。利用
75、序列。利用序列4,34,34,34,3，4,24,24,24,2可以说明选择排序、快速排序、堆排序是不稳定的。可以说明选择排序、快速排序、堆排序是不稳定的。可以说明选择排序、快速排序、堆排序是不稳定的。可以说明选择排序、快速排序、堆排序是不稳定的。 内部排序的方法很多，从不同的角度思考，可对内部排序进行不同的分类 82Sorting Summary(1)(1)直接插入排序适合于原始数据基本有序或直接插入排序适合于原始数据基本有序或直接插入排序适合于原始数据基本有序或直接插入排序适合于原始数据基本有序或n n较小较小较小较小(n16)(n16)的情况。的情况。的情况。的情况。(2)(2)快速排序
76、适合于原始数据杂乱无章，快速排序适合于原始数据杂乱无章，快速排序适合于原始数据杂乱无章，快速排序适合于原始数据杂乱无章，n n较大且对稳定性没有要求的情况。较大且对稳定性没有要求的情况。较大且对稳定性没有要求的情况。较大且对稳定性没有要求的情况。(3)(3)堆排序堆排序堆排序堆排序( (或归并排序或归并排序或归并排序或归并排序) )适合于适合于适合于适合于n n较大，原始数据可能出现正序或逆序且对稳定性没有较大，原始数据可能出现正序或逆序且对稳定性没有较大，原始数据可能出现正序或逆序且对稳定性没有较大，原始数据可能出现正序或逆序且对稳定性没有要求的情况。要求的情况。要求的情况。要求的情况。(4
77、)(4)归并排序适合于归并排序适合于归并排序适合于归并排序适合于n n较大，内存空间允许且要求排序稳定的情况。较大，内存空间允许且要求排序稳定的情况。较大，内存空间允许且要求排序稳定的情况。较大，内存空间允许且要求排序稳定的情况。(5)(5)基数排序的效率与原始数据的排列顺序无关，直接选择排序的比较次数与初始状基数排序的效率与原始数据的排列顺序无关，直接选择排序的比较次数与初始状基数排序的效率与原始数据的排列顺序无关，直接选择排序的比较次数与初始状基数排序的效率与原始数据的排列顺序无关，直接选择排序的比较次数与初始状态无关，但记录移动次数与初始状态有关。态无关，但记录移动次数与初始状态有关。态
78、无关，但记录移动次数与初始状态有关。态无关，但记录移动次数与初始状态有关。在最好情况下，直接插入排序和冒泡排序最快；在平均情况下，快速排序最快；在最在最好情况下，直接插入排序和冒泡排序最快；在平均情况下，快速排序最快；在最在最好情况下，直接插入排序和冒泡排序最快；在平均情况下，快速排序最快；在最在最好情况下，直接插入排序和冒泡排序最快；在平均情况下，快速排序最快；在最坏情况下，堆排序和归并排序最快。坏情况下，堆排序和归并排序最快。坏情况下，堆排序和归并排序最快。坏情况下，堆排序和归并排序最快。在以比较为基础的排序方法中，最少比较次数为在以比较为基础的排序方法中，最少比较次数为在以比较为基础的排序方法中，最少比较次数为在以比较为基础的排序方法中，最少比较次数为nlnl，最多比较次数为，最多比较次数为，最多比较次数为，最多比较次数为n(n-1)/2n(n-1)/2，最，最，最，最坏情况下能达到的最好的时间复杂度为坏情况下能达到的最好的时间复杂度为坏情况下能达到的最好的时间复杂度为坏情况下能达到的最好的时间复杂度为O(n logO(n log2 2n)n)。 内部排序的方法很多，就其性能而言，很难提出一种被认为是最好的方法，每一种方法都有各自的适用范围。83
