快速排序的改进算法  

The Improved Algorithm on the Quicksort

作　　者：周玉林[1] 郑建秀[2] 

机构地区：[1]上饶师范学院数学与计算机系,江西上饶334001 [2]上饶信州区六中,江西上饶334001

出　　处：《上饶师范学院学报》2001年第6期11-15,共5页Journal of Shangrao Normal University

基　　金：上饶师范学院科研基金资助课题

摘　　要：对快速排序算法进行了改进 ,根据在待排序列基本有序的情况下 ,插入排序有较好的性能特点 ,在改进算法中 ,只对长度k大于的子序列递归调用快速排序 ,最后再对整个序列用插入排序方法排序 ,我们得到了时间复杂性为 1.386nlog (n/k) +nk/ 4 + 3(n+ 1) / (k + 1) + O(logn )的排序算法 ,当 k取值为 8左右时 ,改进算法的性能较隹。In this paper we improved the quicksort algorithm. on the basic of the character: when the list is mainly in order, the insertion sort algorithm has a good performance, in our improved algorithm we recur quicksort on the sublist only when the length of it is larger than the value k, and after all recurrences we sort the whole list by insertion sort, by this way we obtain a improved algorithm in which the average-case time-complexity is2nln(n/k)+nk/4-3(n+1)/(k+1)+O(lnn),when we let k nearly 8, the quality of improved algorithm is the best .

关 键 词：快速排序 插入排序 平均时间复杂性 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]