快速排序算法的改进与分析

《快速排序算法的改进与分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、FUYANGTEACHERSCOLLEGE本科毕业论文（设计）指导手册题目：姓名：学院：专业：学号：指导教师姓名、职称：完成日期：2•毕业论文（设计）选题审批单学生姓名学号论文选题选题论证：指导教师初审意见：签名：年月日教研室复审意见：签名：年月日注：本页内容较多时可另附页。3•毕业论文（设计）开题报告题目开题日期一、研究现状与意义二、研究的主要内容（写作提纲）：三、主要参考文献（不少于10项）:目录、二、摘要正文12345引论算法思想介绍算法分析算法的改进测试结果及结论三、注释四、参考文献-摘要排序是计算机程序设计中一种重要操作，本文论述了C语言中快速排序算法的改进,即快速

2、排序与直接插入排序算法相结合的实现过程以及乱序法选择划分轴。在C语言程序设计屮，实现大量的内部排序应用时，所寻求的1=1的就是找到一个简单、有效、快捷的算法。本文从两个小的方面对快速排序做出一点小的改动，使其在相同的数据排序屮达到相对较短的时间。AsummarySortingisanimportantoperationincomputerprogramming,thisarticlediscussesthequicksortalgorithmimprovementsintheClanguage,quicksortimplementationprocessaswellasthe

3、out-of-ordermethodcombinedwithdirectinsertionsortalgorithmtoselectthedivisionaxis.TheCProgrammingLanguage,toachievealargenumberofinternalsortingapplications,thepurposeistoseektofindasimple,effective,andefficientalgorithms.Quicksortmakelittlechangestoachievearelativelyshortperiodoftimeinthes

4、amesortofdatafromtwosmallpart.关键词：算法改进插入式排序快速排序二正文1•引论快速排序（Quicksort）是对冒泡排序的一种改进。由C.A.R.Hoare在1962年提出。它的基本思想是：通过一•趟排序将要排序的数据分割成独立的两部分，其屮一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。2算法思想介绍设要排序的数组是A[0]……A[N-1],首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它人的数

5、都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。—趟快速排序的算法是：1）设置两个变量i、j,排序开始的时候：i=0,j=N-1；2）以第一个数组元素作为关键数据，赋值给key,即key=A[0]；3）从j开始向前搜索，即由后开始向前搜索（j-）,找到第一个小于key的值A[j],A[i]与A[j]交换；4）从i开始向后搜索，即由前开始向后搜索（i++）,找到第一个大于key的A[i],A[i]与A[j]交换；5）重复笫3、4、5步，直到i=j；（3,4步是在程序中没找到时候j=

6、j-1,i=i+1,直至找到为止。找到并交换的时候i,j指针位置不变。另外当i=j这过程一定正好是i+或卜完成的最后令循环结束。）3.算法分析下面是清华人学出版社严蔚敏《数据结构》的代码intPartition（intL[],intlow,inthigh）{//交换顺序表L中子序列L.r[low・.high]的记录，使枢轴记录到位,intpivot=L[low];while（lowpivot）high-;while(low

7、大于基准和小于基准的两个数交换if(low