快速排序的改进算法.pdf.pdf

维普资讯
福建电脑年第期
快速排序的改进算法

.
【摘要】:排序是计算机科学中一个非常重要的研究问题。年,排序曾被列为世纪对科学和工程计算的研究与
实践影响最大的十大问题之一。本文在分析通常的快速排序算法的平均时间复杂度的基础上,提出了一种新的改进算法,提
高了快速排序算法的性能。
【关键词】: 快速排序;时间复杂度;直接插入排序;枢轴
.引言上述算法为一次划分算法。序列已经被枢轴记录划分成了
排序是计算机程序设计中的一种重要操作。。具体的算法
:
大。有资料表明,在一些商用计算机上,用在排序上的时问&,
//对顺序表中的予序列巾..
达到%一% 。为了提高排序效率,人们已对排序进行了许多
//长度大于
。决定排序效率的因素有很多,包括时问,; ,,
复杂度、空间复杂度、排序方法的稳定性等等。通常人们都以时,一; //将低子序列递归排序,是枢
。而轴位置
,; /将高子序列递归排序

序方法。、
.通常的算法—递归调用程序
快速排序也是交换排序的一种,是对冒泡排序&
/对顺序表作挟速捧序
的改进。它的基本思想是,在待排序列中选取一个记录枢轴记
.,:
录。以该记录的关键字为标准称为基准值,将其它所有待排//

。
。然后再通过递归的方法,分别对下面我们来分析快速排序的平均时间性能。
..】进行快速排序所需时问,则
置为止。由算法可见.
。如果基准,。忙一—.
,,
,,可以
序,同时其时间复杂度变为。为了避免这种情况的出现,我表示之为某个常数;. ..一和
们通常依照”三者取中”的法则来选取基准值,即把序列最左边、. .. 中记录进行快速排序厶,.一和,,
最右边及序列最中间的三个记录的关键字中的中间值作为基准所需时问。假设待排序列中的记录是随机排列的,则在一趟排序
值。/.之间任何一值的概率相同,快速排序所需时问
”三者取中”的规则可以大大改善快速排序在最坏情况的平均值则为
下的运行效率下面我们将给出通常情况下人们所使用的快速∑】
排序算法『:
/&, 鲁∑
,,一次划分算法,先找到基准值对应的记录,然后再对记录序列进行一次划分