快速排序算法的分析与研究

Analysis and research of quick sorting algorithm

快速排序是排序算法中性能较好的一种,但存在对数据基本有序的情形下的性能瓶颈问题。为了保证快速排序在任何情况下的高效性,在对快速排序算法的时间效率进行充分的分析的基础上,指出支点元素的选取是影响快速排序算法效率的主要因素。提出了一种随机选择支点元素的快速快排方法,很好地避免了最坏情况的发生。通过实验验证了改进算法的正确性和高效性。

Quick sort is one of sorting algorithms with better performance,but it has choke point when sorted data is in ba-sic sort order. In order to ensure high efficiency of quick sort in any case,based on a full analysis of the time efficiency of quick sorting algorithm,it is pointed out that the main factor which affects the efficiency of quick sorting algorithms is the selec-tion of pointing element. Therefore,a quick sorting method of selecting the pointing element randomly is proposed,which makes the occurrence of the worst case well avoided. The correctness and efficiency of the improved algorithm were verified by experi-ments.