当前位置 —论文—政治— 范文

计算机相关论文范文数据库,与快速排序算法的优化相关本科毕业论文范文

本论文是一篇计算机相关本科毕业论文范文,关于快速排序算法的优化相关毕业论文范文。免费优秀的关于计算机及枢轴及数据结构方面论文范文资料,适合计算机论文写作的大学硕士及本科毕业论文开题报告范文和学术职称论文参考文献下载。

摘要快速排序算法是计算机内部排序程序设计中的一种重要操作,在现实生活中有广泛应用.本文主要对在排序过程中记录移动次数进行探讨优化,希望在计算机的学科发展大潮中贡献绵薄力量.

【关键词】快速排序记录移动

快速排序是对起泡排序的一种改进,在时间、空间复杂度同数量级的排序方法中,其平均性能最优.其基本思想是,通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序.

该文转载于 http://www.sxsky.net/zhengzhi/050115392.html

1快速排序算法实现

1.1一趟快速排序算法实现

假设待排序的序列为{L.r[s],L.r[s+1],等,L.r[t]},首先任意选取一个记录(通常可选第一个记录L.r[s])作为枢轴(或支点)(pivot),然后按下述原则重新排列其余记录:将所有关键字较它小的记录都安置在它的位置之前,将所有关键字较它大的记录都安置在它的位置之后.由此可以将该”枢轴”记录最后所落得位置i作分界线,将序列{L.r[s],等,L.r[t]}分割成两个子序列{L.r[s],L.r[s+1],等,L.r[i-1]}和{L.r[i+1],L.r[i+2],等,L.r[t]}.这个过程称做一趟快速排序(或一次划分).

如何写计算机毕业论文
播放:39500次评论:4447人

快速排序算法的优化参考属性评定
有关论文范文主题研究:	关于计算机的论文范文集	大学生适用:	自考毕业论文、在职研究生论文
相关参考文献下载数量:	29	写作解决问题:	怎么写
毕业论文开题报告:	文献综述、论文前言	职称论文适用:	杂志投稿、职称评副高
所属大学生专业类别:	怎么写	论文题目推荐度:	免费选题

一趟快速排序的具体做法是:附设两个指针low和high,他们的初值分别为low和high,设枢轴记录的关键字为pivotkey,则首先从high所指位置向前搜索找到第一个关键字小于pivotkey的记录和枢轴记录互相交换,然后从low所指位置起向后搜索,找到第一个关键字大于pivotkey的记录和枢轴记录互相交换,重复这两步直至low等于high为止.其算法如下:

intPartition(SqList&L,intlow,inthigh){

pivotkey等于L.r[low].key,

while(low

while(low等于pivotkey)--high,

L.r[low]<---->L.r[high],

while(low

L.r[low]<---->L.r[high],

}

returnlow,

}

1.2递归形式的快速排序算法

通过对一次划分所得的两个子序列递归排序,得到原序列的排序

算法实现如下：

voidQSort(SqList&L,intlow,inthigh){

if(low

pivotloc等于Partition(L,low,high),

QSort(L,low,pivotloc-1),

QSort(L,pivotloc+1,high),

}

2对一趟排序算法的优化

由上述算法知,在进行一次记录交换时,需要3次记录移动(

计算机相关论文范文数据库赋值)的操作.而在实际上,在排序过程中对枢轴记录的赋值是多余的.因为在排序过程中,当low>等于high时确定枢轴位置即可.因此可以将枢轴记录暂存,当一趟排序结束时才将枢轴记录移动到正确位置.此外,可以将指针的单向移动改为双向移动,即:low指针从开始位置向后搜索,直到遇到第一个大于pivotkey的记录；high指针从开始位置向前搜索,直到遇到第一个小于pivotkey的记录,然后交换low和high指针对应的记录.

算法实现如下:

intPartition(SqList&L,intlow,inthigh){

l等于low,

high等于high+1,

while(low

do{

low++,

}while(L.r[low].keydo{

high--,

}while(L.r[high].key>pivotkey)

swap(L.r[low],L.r[high]),//交换两条记录

}