三种高效排序算法性能分析
|
摘要
排序是计算机科学中的基本操作,快速排序、堆排序和归并排序是三种常用的效率较高的排序算法.为便于理解和掌握,并为具体问题选择适合的算法提供借鉴和依据,本文详细阐述了每种算法的基本思想和实现步骤,给出了每种算法的时间复杂度的推导过程,分析了每种算法的稳定性和适用情况.
Sorting is the basic operation in computer science.Three efficient and commonly used sorting algorithms include quick sorting,heap sorting and merge sorting.In order to facilitate understanding and mastery,and to provide a reference and basis for selecting the appropriate sorting algorithm for practical problems,this paper elaborates the basic ideas and implementation steps of each algorithm in detail,gives the derivation process of each algorithm time complexity,and analyzes the stability and application of each algorithm.
Sorting is the basic operation in computer science.Three efficient and commonly used sorting algorithms include quick sorting,heap sorting and merge sorting.In order to facilitate understanding and mastery,and to provide a reference and basis for selecting the appropriate sorting algorithm for practical problems,this paper elaborates the basic ideas and implementation steps of each algorithm in detail,gives the derivation process of each algorithm time complexity,and analyzes the stability and application of each algorithm.
引文
[1]秦玉平,马靖善.数据结构(C语言版)[M](第3版).北京:清华大学出版社,2015.
[2]SONAL B,DEEPTI G.Comparison of various sorting algorithms:a review[J].International Journal of Emerging Research in Management and Technology,2013,2(5):83-86.
[3]ANSHUMAN N,ANURAG U,SIDDHARTH B D,et al.Techniques and tradeoffs in sorting algorithms:a review[J].International Journal of Contemporary Research in Computer Science and Technology,2015,1(4):2395-5325.
[4]MARCIN W,ZBIGNIEW M,MARCIN G,et al.Preprocessing large data sets by the use of quick sort algorithm[C].Proceeding of International Conference on Knowledge,Information,and Creativity Support Systems,2013:7-9.
[5]WANG X.Analysis of the time complexity of quick sort algorithm[C].Proceeding of International Conference on Information Management,2011:408-410.
[6]DHIVAKAR P,JAYAPRAKASH G.Dual sorting algorithm based on quick sort[J].International Journal of Computer Science and Mobile Applications,2013,1(6):1-10.
[7]DIEKERT V,WEISS A.Quick heapsort:modifications and improved analysis[J].Theory of Computing Systems,2016,59(2):209-230.
[8]CANTONE D,CINCOTTI G.Quick heapsort,an efficient mix of classical sorting algorithms[J].Theoretical Computer Science.2002,285(1):25-42.
[9]SINGH J,SINGH R.Merge sort algorithm[J].International Journal of Research,2014,1(10):1203-1207.
[10]VIGNESH R,TRIBIKRAM P.Merge sort enhanced in place sorting algorithm[C].Proceeding of International Conference on Advanced Communication Control and Computing Technologies,2016:698-704.
[11]石嵩,李宏亮,朱巍.阵列众核处理器上的高效归并排序算法[J].计算机研究与发展,2016,53(2):362-373.
[12]马靖善,秦玉平.一种改进的归并排序算法[J].渤海大学学报(自然科学版),2009,30(2):190-192.
[2]SONAL B,DEEPTI G.Comparison of various sorting algorithms:a review[J].International Journal of Emerging Research in Management and Technology,2013,2(5):83-86.
[3]ANSHUMAN N,ANURAG U,SIDDHARTH B D,et al.Techniques and tradeoffs in sorting algorithms:a review[J].International Journal of Contemporary Research in Computer Science and Technology,2015,1(4):2395-5325.
[4]MARCIN W,ZBIGNIEW M,MARCIN G,et al.Preprocessing large data sets by the use of quick sort algorithm[C].Proceeding of International Conference on Knowledge,Information,and Creativity Support Systems,2013:7-9.
[5]WANG X.Analysis of the time complexity of quick sort algorithm[C].Proceeding of International Conference on Information Management,2011:408-410.
[6]DHIVAKAR P,JAYAPRAKASH G.Dual sorting algorithm based on quick sort[J].International Journal of Computer Science and Mobile Applications,2013,1(6):1-10.
[7]DIEKERT V,WEISS A.Quick heapsort:modifications and improved analysis[J].Theory of Computing Systems,2016,59(2):209-230.
[8]CANTONE D,CINCOTTI G.Quick heapsort,an efficient mix of classical sorting algorithms[J].Theoretical Computer Science.2002,285(1):25-42.
[9]SINGH J,SINGH R.Merge sort algorithm[J].International Journal of Research,2014,1(10):1203-1207.
[10]VIGNESH R,TRIBIKRAM P.Merge sort enhanced in place sorting algorithm[C].Proceeding of International Conference on Advanced Communication Control and Computing Technologies,2016:698-704.
[11]石嵩,李宏亮,朱巍.阵列众核处理器上的高效归并排序算法[J].计算机研究与发展,2016,53(2):362-373.
[12]马靖善,秦玉平.一种改进的归并排序算法[J].渤海大学学报(自然科学版),2009,30(2):190-192.