首页 > 论文范文 > 教育综合论文 > 高等教育论文 > 高等教学法论文 > 快速排序教学研究

快速排序教学研究

2020-12-23 154 上传者：管理员

摘要：介绍了快速排序的概念;分析了传统快速排序的弊端,递归深度较大会导致算法效率低下;提出了一种基于关键值为序列平均值的快速排序算法,阐述了算法的详细运行过程,并分析了其优势;通过实验验证了基于关键值为序列平均值的快速排序算法性能优越。

关键词：
关键值
平均值
快速排序
电子信息技术
递归
加入收藏

快速排序算法是一种优秀的排序算法，它的平均时间复杂度为O(n*log2n)，与冒泡排序和插入排序相比较而言，已经有了很大的提高，n指待排序数据的规模，n越大，快速排序的优势越明显[1]。

快速排序的过程第一步是选择一个关键值，将排序序列进行划分，分成两个子序列，然后对这两个子序列再执行递归的快速排序，直至子序列中只含有一个元素为止。由此可见，选择关键值至关重要，关键值不同会导致划分的子序列的规模不同，这将严重影响快速算法的效率[2]。

传统的快速排序算法一般都会选择排序序列的第一个元素作为关键值，如果此时待排序序列已经基本有序，则选择第一个元素作为关键值会使递归的层次达到最大，增加了算法的时间复杂度。本文提出了基于关键值为序列平均值的快速排序算法，其以排序序列的平均值作为关键值，这会使递归的层次达到最小，使快速算法的效率更优[3]。

1、传统的快速排序算法

对于待排序的序列{a1,a2,a3……an}，传统的快速排序算法选择排序序列的第一个元素a1作为关键值(pivot)，假设排序是升序排序，序列会被pivot分成两个部分:{子序列1}，pivot，{子序列2}，子序列1中的值都小于等于pivot的值，子序列2中的值都大于等于pivot的值。

这个过程称为划分，划分算法的伪代码如表1所示:

表1划分算法伪代码

在序列划分执行完之后，要对两个子序列进行快速排序，这里的关键是计算出两个子序列的开始和结束位置，然后进行递归的快速排序，其对应的快速排序算法伪代码如表2所示:

表2快速排序算法伪代码

这种算法的缺点在于，当需要排列的序列元素基本有序时，递归的层次偏高，影响算法效率。设快速排序算法对应的函数的名称为qsort(序列，序列首元素位置，序列末元素位置)，则对一个需要升序排列的序列a[]={1,2,3,4,5,6,7}执行快速排序的执行过程qsort(a,0,6)如图1所示:

图1qsort(a,0,6)的执行过程

图1中递归调用的深度为6，如果有n个元素，则对应递归深度为n-1，算法的时间复杂度为O(n2)，此时快速排序的效率达到了最差[4]。

2、改进的快速排序算法

传统快速排序算法在序列基本有序的情况下效率较差，这是由于关键值选择不合理而导致的，因为首元素并不能把一个序列划分成两个大致相等的子序列，而采取序列平均值作为关键值进行划分，效果会优越得多[5]。

采取序列平均值作为关键值进行划分，也需要求得划分的位置，划分的算法和传统的快速排序算法相似，但也有不同，这不同之处就在于:序列平均值并不一定会出现在序列中，所以得到的两个子序列的位置计算需要额外的进行处理[6]。

比如对于序列{1,2,3,4,6}，其平均值为3.2，按照划分算法得到返回的位置值为2，也就是值3对应的位置，具体的过程如图2，共有5步:

图2划分序列1

很明显此时3.2并不是序列的元素之一，所以其划分的子序列不是{1,2}和{4,6}了，而是{1,2,3}和{4,6}。

对于序列{6,2,3,4,1}，其平均值为3.2，按照划分算法得到返回的位置值为3，也就是值4对应的位置，具体的过程如图3，共有7步:

图3划分序列2

很明显此时3.2并不是序列的元素之一，所以其划分的子序列不是{1,2}和{4,6}了，而是{1,2,3}和{4,6}。

如果序列平均值恰好出现在序列中，则跟传统的快速排序算法相似。

对于一个序列{a1,a2,a3……an}，如果采取序列平均值对序列进行划分后，再进行递归的快速排序时，根据上述三种情况，子序列的范围可以由以下规则确定:令划分函数返回的位置为k，如果a[k]大于序列平均值，则两个子序列的范围是{a1,a2,a3……ak-1}和{ak,ak+1,ak+2……an};如果a[k]小于序列平均值，则两个子序列的范围是{a1,a2,a3……ak}和{ak+1,ak+2……an};如果a[k]等于序列平均值，则两个子序列的范围是{a1,a2,a3……ak-1}和{ak+1,ak+2……an}[7]。

划分好子序列后，再对子序列进行递归的快速排序即可，划分算法的伪代码如表3，和传统算法的划分类似，只有pivot值进行了修改，这里pivot值等于序列的平均值。

新快速排序算法伪代码如表3所示:

表3新快速排序算法伪代码

这种算法即便是对一个基本有序的序列进行排序，也能得到较好的效果。假设新快速排序算法对应的函数的名称为nqsort，那么对图1的序列进行快速排序的过程nqsort(a,0,6)如图4所示:

图4nqsort(a,0,6)的执行过程

图4中递归调用的深度为3，如果有n个元素，则对应递归深度约等于log2n，算法的时间复杂度为O(n*log2n)，此时快速排序的效率得到了改善[8]。

3、实验分析

选定需要排序的序列的元素个数分别是q[i]={200,400,600，……，1800,2000}，在matlab14.0环境下随机生成q[i]个元素进行升序排序，tqsort[i]为传统快速排序所耗费的时间，tnqsort[i]为改进的快速排序所耗费的时间，yi=(tqsort[i]-tnqsort[i])/tnqsort[i]为时间优化率，对于每个yi计算10次，取其平均值y平均为平均时间优化率，则y平均对应的趋势图如图5:

图5平均时间优化率

由图5可见，排序元素个数越多，改进的快速排序算法的优势也就越明显，对于2000个元素的排序序列，平均时间优化率已经超出6%[9]。

4、结论

快速排序是一种用递归实现的排序方法，关键在于对排序序列的划分，划分的子序列不同，算法的效率就会有很大的不同，本文所阐述的快速排序算法，没有使用序列首元素充当关键值，而是采用了序列平均值充当关键值，这会减少递归的深度，减低算法的时间复杂度[10]。

采用了序列平均值充当关键值的快速排序算法也有其不足之处，例如对于序列{1,2,3,4,5,10000}这样的序列进行以序列平均值充当关键值的快速排序，递归深度也会较大，下一步的算法改进方向是采用序列中位数对应数值作为关键值对序列进行快速排序[11]。

参考文献：

[1]秦玉平,马靖善.数据结构(C语言版)[M](第3版).北京:清华大学出版社,2015.

[2]石嵩,李宏亮,朱巍.阵列众核处理器上的高效归并排序算法[J].计算机研究与发展,2016,53(2):362-373.

[3]马靖善,秦玉平.一种改进的归并排序算法[J].渤海大学学报(自然科学版),2009,30(2):190-192.

[4]严蔚敏,吴伟民.数据结构[M].北京:清华大学出版社,2001.

[5]施伯乐.数据结构教程[M].上海:复旦大学出版社,2011.

[6]林建秋,韩静萍.C语言程序设计[M].北京:机械工业出版社,2014.