| 快速排序的改进算法 |
| |
| 引用本文： | 周玉林,郑建秀.快速排序的改进算法[J].上饶师范学院学报,2001,21(6):11-15. |
| |
| 作者姓名： | 周玉林 郑建秀 |
| |
| 作者单位： | 1. 上饶师范学院数学与计算机系,江西,上饶,334001
2. 上饶信州区六中,江西,上饶,334001 |
| |
| 基金项目： | 上饶师范学院科研基金资助课题 |
| |
| 摘 要： | 对快速排序算法进行了改进,根据在待排序列基本有序的情况下,插入排序有较好的性能特点,在改进算法中,只对长度k大于的子序列递归调用快速排序,最后再对整个序列用插入排序方法排序,我们得到了时间复杂性为1.386 nlog(n/k) nk/4 3(n 1)/(k 1) O(logn)的排序算法,当k取值为8左右时,改进算法的性能较隹.
|
| 关 键 词： | 快速排序 插入排序 平均时间复杂性 |
| 文章编号： | 1004-2237(2001)06-0011-05 |
| 修稿时间： | 2001年6月9日 |
The Improved Algorithm on the Quicksort |
| |
| ZHOU Yu-lin ,ZHENG Jian-xiu.The Improved Algorithm on the Quicksort[J].Journal of Shangrao Normal College,2001,21(6):11-15. |
| |
| Authors: | ZHOU Yu-lin ZHENG Jian-xiu |
| |
| Institution: | ZHOU Yu-lin 1,ZHENG Jian-xiu 2 |
| |
| Abstract: | 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 . |
| |
| Keywords: | quicksort insertion sort average-case time-complexity |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
