快速排序算法改进与分析.doc

本科毕业论文（设计） 指 导 手 册 题 目： 姓 名： 学 院： 专 业： 学 号： 指导教师姓名、职称： 完成日期： 2.毕业论文（设计）选题审批单 学生姓名 学 号 论文选题 选题论证： 指导教师初审意见： 签 名： 年 月 日 教研室复审意见： 签 名： 年 月 日 注：本页内容较多时可另附页。 3.毕业论文（设计）开题报告 题 目 开题日期 一、研究现状与意义 二、研究的主要内容（写作提纲）： 三、主要参考文献（不少于10项）： 目录 摘要 正文 引论 算法思想介绍 算法分析 算法的改进 测试结果及结论 三、注释 四、参考文献 一 摘要 排序是计算机程序设计中一种重要操作，本文论述了Ｃ语言中快速排序算法的改进，即快速排序与直接插入排序算法相结合的实现过程以及乱序法选择划分轴。在Ｃ语言程序设计中，实现大量的内部排序应用时，所寻求的目的就是找到一个简单、有效、快捷的算法。本文从两个小的方面对快速排序做出一点小的改动，使其在相同的数据排序中达到相对较短的时间。 A summary ???Sorting is an important operation in computer programming, this article discusses the quicksort algorithm improvements in the C language, quicksort implementation process as well as the out-of-order method combined with direct insertion sort algorithm to select the division axis. The C Programming Language, to achieve a large number of internal sorting applications, the purpose is to seek to find a simple, effective, and efficient algorithms. Quicksort make little changes to achieve a relatively short period of time in the same sort of data from two small part. 关键词：算法 改进插入式排序 快速排序 二 正文 1.引论 快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。 一趟快速排序的算法是： 1）设置两个变量i、j，排序开始的时候：i=0，j=N-1； 2）以第一个数组元素作为关键数据，赋值给key，即