摘要
排序是计算机科学中最重要的研究问题之一。2000年被列为20世纪对科学和工程计算的研究与实践影响最大的10大问题之一。文章介绍了基本的快速排序算法及三种枢轴元素的选取方法,全面深入地分析了快速排序算法最坏情况下的时间复杂度、平均情况下的时间复杂度、随机情况下的时间复杂度。并对快速排序算法和堆排序算法进行了比较,理论和实验结果表明,快速排序算法仍然是目前最好的排序算法之一。
Sorting is arguably the most studied problem in computer science,because of both its use in many applications and its intrinsic theoretical importance,one of the ten algorithms with the greatest influence on the development and practice of science and engineering in the 20th century. This paper introduces the basic quicksort algorithm and three methods of choice of the pivot and gives a broad of its worse-case、average-case and randomized complexity analysis. A comparison on the quicksort and heapsort is made. Some empirical data show that quicksort is still one of the best sorting algorithms.
出处
《微电子学与计算机》
CSCD
北大核心
2002年第6期6-9,共4页
Microelectronics & Computer
基金
国家"十五"预研资助项目
