快速排序算法..docx

对快速排序算法适用条件的探究 --刘晨飞 2013120101027政治与公共管理学院 信息管理与信息系统摘要 快速排序算法是对一个无序数据集合进行排序使其按某种规则（本文以按关键码升序为规则）有序排列的算法。快速排列算法是对起泡排序算法的该进，和起泡排序算法同属于交换排序算法，其核心思想是在待排序序列中选择两个记录，将其关键码进行对比，如果反序就交换它们的位置，起泡算法中记录的比较和移动是在相邻的位置进行的，记录的每次交换只能移动一个位置，因而总的比较次数比较多，针对这个问题，快速排序算法进行了优化。在快速排序算法中，记录的比较和移动是从两端向中间进行的，关键码较大的记录一次就能从前面移动到后面，关键码较小的记录一次就能从后面移动到前面，记录移动的距离较远，从而减少了总得比较次数和移动次数。探究快速排序算法的工作原理和适用条件有利于在实际开发的过程中灵活选择这两种算法，编写出高质量的程序。 关键词：快速排序算法，交换排序算法，移动次数，适用条件引言 排序是数据处理中经常使用到的算法，在数据统计中许多的分析手段都是建立在待处理数据集有序的前提之下的，例如统计分析中求中位数、四分位数、十分位数、百分位数、绘制回归分析图像等都需要首先将待处理数据排序。但是针对不同的待处理数据集合和不同的应用条件，实际使用中对排序算法有着不同的需求，所以产生了许许多多不同的针对不同场景的不同的排序算法，目前的排序算法主要分为以下几种：插入排序，主要思想是依次将一个待排序的记录按照其关键码的大小插入一个已经排好序的有序序列中，直到所有记录都处于有序状态。交换排序，主要思想是在待排序列中选择两个记录，将它们的关键码进行比较，如果反序就交换它们的位置。选择排序，主要思想是每趟排序在当前待排序列中选择关键码最小的记录，添加到有序序列中。归并排序，主要思想是将若干有序序列逐步归并，最终归并为一个有序序列。分配排序，主要思想是先将待排序记录序列分配到不同的桶里，然后再把各桶中的记录依次收集到一起。上述的每一类排序算法都有很多的具体实现，例如希尔排序、起泡排序、快速选择排序、堆排序、二路归并排序、桶式排序等等。其中在关键码分布较为随机，待排序列基本无序的时候，使用交换排序能取得较好的效果，但是在此种情况下，作为交换排序中最基本的起泡排序算法也有一些局限性。在起泡排序算法中，每次比较是在相邻的记录之间进行，关键码较大的记录从前向后移动和关键码较小的元素从后向前移动都需要很多次操作。在快速排序的算法中记录的移动通过和轴值的交换实现，在一次划分的过程中，关键码较大的记录可以一次从前面移动到后面，关键码较小的元素也可以一次从后面移动到前面，减少了总的比较次数和移动次数。快速排序算法的平均性能是迄今为止所有排序算法中最好的一种，因此得到了广泛的应用，研究快速排序算法的适用条件有利于适当地选用排序算法，开发出性能优良的应用。具体的研究方式为，针对不同种类的待分类数据集合和不同的需求，在各种算法的情况下计算运行时间和空间消耗，比对出快速排序算法的适用条件。正文快速排序算法简介快速排序算法的基本思想是将待排记录划分为两部分，一部分的关键码小于轴值的关键码，另一部分的轴值大于关键码，再对两部分分别采用这种算法处理，直到整个待排序列有序。显然这是一个递归调用的过程，递归终止的条件是需要处理的未分区序列长度为一。快速排序的一次将记录按轴值划分为两个部分称为一次划分，一次划分的示例如下:假设待排序列为：23 13 49 6 31 19 28在一开始需要选择轴值，轴值的选择可以是任意的，最简单的方法是选择第一个记录，还可以通过特定的算法选择较为适中的值作为轴值避免出现因待排序列恰巧为正序或者反序的情况下导致的算法复杂度增加。接下来均使用第一个记录作为轴值。选取23作为轴值，并标为红色：23 13 49 6 31 19 28从右侧开始扫描，遇到比关键码比23大的记录就继续扫描，正在扫描的记录为蓝色：23 13 49 6 31 192828大于23，应当处于23的右侧，不处理，继续扫描1923 13 49 6 3119 2819小于23，应当处于23的左侧，需要将19与23交换。交换之后23右侧的记录关键码均大于23，19左侧的记录关键码均小于23，故交换之后新一轮的扫描从19的下一个记录向右扫描。19 13 49 6 3123 2813小于23，应当处于23的左侧，不处理，继续扫描4919 13 49 6 3123 2849大于23，应当处于23的右侧，需要将49与23交换。交换之后23左侧的记录关键码均小于23，49右