跳到主要內容

臺灣博碩士論文加值系統

(18.97.9.172) 您好!臺灣時間:2025/02/16 21:22
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:曾志鴻
研究生(外文):Chih-hung Tzeng
論文名稱:排序演算法之研究
論文名稱(外文):Investigation on sorting
指導教授:陳維美
指導教授(外文):Wei-Mei Chen
學位類別:碩士
校院名稱:大同大學
系所名稱:應用數學學系(所)
學門:數學及統計學門
學類:數學學類
論文種類:學術論文
畢業學年度:93
語文別:英文
論文頁數:31
中文關鍵詞:堆積排序法快速排序法排序
外文關鍵詞:heapsortquickheapsortquicksortsorting
相關次數:
  • 被引用被引用:3
  • 點閱點閱:331
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
我們先對快速排序、堆積排序、和快速堆積排序的演算法效率的機率性質作徹底分析及模擬;之後,我們並改進了快速堆積排序法,並對其實驗得了些結果;再把改良後的排序法拿來和快速排序法、堆積排序法、快速堆積排序法在交換次數、比較次數、和執行的總時間上作比較。
In this thesis, we give a systematic study on the stochastic behaviors of heapsort, quicksort, and quickheapsort algorithm, respectively. Moreover, we propose a new variant of quickheapsort, and give experimental results on the performance of the improved quickheapsort. The costs considered include the numbers of swaps, the number of comparisons, and the total time used by quicksort, heapsort, quickheapsort, and the improved quickheapsort.
Contents
1. Introduction………………………………………………….. 1
2. Quicksort and Heapsort………………………………….….. 4
2.1 Quicksort…………………………………………………………………….. 4
2.1.1 The Quicksort algorithm…………………………………………..….. 4
2.1.2 Analysis of Quicksort……………………………………………….… 5
2.1.2.1 The Worst Case…………………………………………….. 6
2.1.2.2 The Best Case…………………………………………….… 6
2.1.2.3 The Average Case…………………………………………... 6
2.2 Heapsort……………………………………………………………………... 8
2.2.1 The Heapsort Algorithm……………………………………………... 8
2.2.2 Remarks…………...…………………………………………………. 10
3. QuickHeapsort………………………………………….…… 12
3.1 A Not In-Place Variant of the Heapsort Algorithm………………………... 12
3.2 Quickheapsort Algorithm………...………………………………….……… 14
4. An Improved QuickHeapsort….....…………………………. 18
4.1 Improved Quickheapsort Algorithm…………………...…………………... 18
5. Comparisons………………………………………………… 21
5.1 Comparison with the number of swaps……………………………………. 21
5.2 Comparison with the number of comparisons…...…...…………………… 25
5.3 Comparison with the Run time…………..…..…………...………………… 26
5.4 Conclusions………………...………………………………………………… 27
6. References...…………………………………………….…… 29
[1] J. L. Bentley, Programming Pearls, Addison-Wesley, 1986.
[2] D.Cantone and G. Cincotti, Quickheapsort, an efficient mix of classical sorting algorithms, CIAC, LNCS 1767, (2000), 150-162.
[3] R. D. Dutton, The weak-heap data structure, Technical report, University of Central Florida, Orlando, FL 32816, (1992).
[4] R.D. Dutton, Weak-heap sort, BIT, 33 (1993), 372-381.
[5] R.W. Floyd, Treesort 3(alg.245), Communications.of ACM, 7 (1964), 701.
[6] C.A.R. Hoare, Quicksort, Computing Journal, 5 (1962), 10-15.
[7] C.A.R Hoare, Algorithm 63(partition) and algorithm 65(find), Communications.of ACM, 4:7 (1961), 321-322.
[8] D. E. Knuth, The Art of Computer Programming, volume 3: Sorting and Searching, Addison-Wesley, Reading MA, 1975.
[9] M. D. McIlroy, A killer adversary for quicksort, Software-Practice and Experience, 29:4 (1999), 341-344.
[10] R. L. Rivest and D.E. Knuth, Bibliography 26: computer sorting, Computer Reviews, 13 (1972), 283-289.
[11] R.Sedgewick,Quicksort, PhD Thesis, Stanford University, 1975.
[12] R.Sedgewick, The analysis of quicksort programs, Acta Informatica, 7 (1977), 327-355.
[13] R. Sedgwick, Algorithms in C, Addison-Wesley, 1990.
[14] R. Sedgewick, Implementing quicksort programs, Communications Of ACM , 21:10 (1978), 847-857.
[15] R. Sedgewick, Quicksort, Garland Publishing, New York, 1980.
[16] J.W. Williams, Heapsort (alg.232), Communications of ACM, 7(1964), 347-348.
[17] I. Wegener, Bottom-Up-Heapsort, a new variant of Heapsort, beating, on an average, Quicksort (if n is not very small), Theoretical Computer Science, 118 (1993), 81-98.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top