Course3排序Sort

《Course3排序Sort》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Course3排序Sort▓Outlines本章重點Sort分類觀點初等排序方法(Avg.Case:O(n2))InsertionSortSelectionSortBubbleSort高等排序方法(Avg.Case:O(nlogn))QuickSortMergeSortHeapSortRadixSort2InternalSortv.s.ExternalSort.StableSortingMethodv.s.UnstableSortingMethod.▓Sort分類觀點3InternalSortv.s.ExternalSor

2、t觀點:資料量的多寡InternalSort:Def:資料量少，可以一次全部置於Memory中進行sort之工作目前大多數的Sort方法皆屬此類ExternalSort:Def:資料量大，無法一次全置於Memory中，須藉助輔助儲存體(E.g.Disk)進行sort之工作4假設欲排序的資料中，有多個記錄具有相同的鍵值(如:…,k,…,k,…)，經過排序之後，結果可能為:…,k,k,…:會得到此結果的排序方法稱之為Stable…,k,k,…:會得到此結果的排序方法稱之為Untable例:原始:5,4,2,6,4,7,1St

3、able:1,2,4,4,5,6,7Unstable:1,2,4,4,5,6,7StableSortingMethodv.s.UnstableSortingMethod曾有不必要的Swap發生!!5Avg.CaseTimeComplexity:O(n2)InsertSortSelectionSortBubbleSort▓初等排序方法65:Solution:將第i筆記錄插入到前面(i-1)筆已排序好的記錄串列中，使之成為i筆已排序好的記錄串列。(需執行n-1回合)範例:Asequence9,17,1,5,10。以遞增(in

4、crease)排序▓InsertSort(插入排序)7根據上例，可知若有n筆記錄，則需做(n-1)回合。Algorithm主要由2個副程式組成:Insert副程式將某一筆記錄x插入到S[1]~S[i-1]等i-1筆已排序好的串列中，使之成為i筆已排序好的串列。即:決定x插入的位置Sort副程式(可當作主程式)將未排序好的記錄透過Insert的動作，使之成為排序好的記錄共需做n-1回合，且由第二筆資料開始做起，迴圈:fori=2ton8Insert副程式Sort副程式(可看成主程式)91234567824513範例:Ins

5、ert副程式:已排序未排序ijx=S[i]987x5S10分析TimeComplexityBestCaseWorstCaseAverageCaseSpaceComplexityStable/Unstable11Time-ComplexityBestCase:O(n)當輸入資料已經是由小到大排好時。[分析方法1]:Solution:比較一次比較一次比較一次比較一次n筆資料需作(n-1)回合，且每回合只比較1次即可決定x的插入位置。總共花費(n-1)次比較即完成Sort工作。Timecomplexity=O(n)

6、12[分析方法2]:利用遞迴時間函數T(n)=T(n-1)+1=(T(n-2)+1)+1=T(n-2)+2=(T(n-3)+1)+2=T(n-3)+3=…=T(0)+nT(n)=O(n)前(n-1)筆比較的執行次數第n筆資料的最佳比較次數沒有資料，所以比較次數T(0)=013Solution:WorstCase:O(n2)當輸入資料是由大到小排好時。[分析方法1]:比一次比二次比三次比四次n筆資料總共比較次數=1+2+3…+(n-1)=[n(n-1)]/2。Timecomplexity=O(n2)14[分析方法2]:利用

7、遞迴時間函數T(n)=T(n-1)+(n-1)=(T(n-2)+(n-2))+(n-1)=T(n-2)+(n-2)+(n-1)=(T(n-3)+(n-3))+(n-2)+(n-1)=…=T(0)+0+1+2+…+(n-3)+(n-2)+(n-1)=1+2+…+(n-3)+(n-2)+(n-1)=n(n-1)/2T(n)=O(n2)前(n-1)筆比較的執行次數第n筆資料的最差比較次數沒有資料，所以比較次數T(0)=015AverageCase:O(n2)[分析方法]:利用遞迴時間函數T(n)=T(n-1)+n/2=T(n-

8、1)+cn=T(n-2)+c(n-1)+cn=…=T(0)+c(1+2+…+n)=c[n(n+1)]/2∴T(n)=O(n2)前(n-1)筆比較的執行次數第n筆資料的平均比較次數第n筆資料與前n-1筆資料可能的比較次數有1次，2次，3次，…，(n-1)次。因此，第n筆資料與前n-1筆資料的比較次數總合為