论文部分内容阅读
摘要：排序在计算机科学领域的研究中占着举足轻重的作用，快速排序算法较其它排序算法而言是基于关键字比较的一种性能较好的划分交換排序算法，主要是根据所选取的基准元素将序列划分开来，第一个序列中的元素均不大于基准元素，第二个序列中的元素均不小于基准元素，最终使得整个序列变为有序序列。其平均时间复杂性是O（nlogn）。由此看来，从待排序序列中选取指导划分的基准元素是决定算法性的关键。本文主要是通过对各种快速排序改进算法的分析比较，也即不同的基准元素选择方法展开讨论。
关键词：快速排序；基准元素；时间复杂性；划分
对于计算机科学领域而言，排序是一项关键的技术，广泛应用于计算机的信息数据处理操作，特别是在当今大数据时代背景下，数据量巨大，数据元素处理更为频繁，对于排序算法的研究以及改进更为至关重要。由此看来，对于额外空间开销小、运行速度快的高效率的排序方法的研究广受众多算法研究人员的欢迎。算法的好坏的衡量标准主要是该算法运行时的执行时间的快慢以及算法运行时所将占用的额外存储空间的大小。
1 快速排序
1.1基本思想
快速排序的基本思想是：通过一趟排序算法把所需要排序的序列的元素分割成两大块，其中，一部分的元素都要小于或等于另外一部分的序列元素，然后仍根据该种方法对划分后的这两块序列的元素分别再次实行快速排序算法， 排序实现的整个过程可以是递归的来进行调用， 最终能够实现将所需排序的无序序列元素变为一个有序的序列。
1.2性能分析
快速排序的机能在平常情形下可约等于O（nlogn）。在对传统快速排序算法进行具体应用时， 一般选取待排序序列元素中的第一个元素作为基准元素进行比较划分。当给定序列元素几乎有序或有序时，该快速排序算法的速度将会大打折扣；对于给定序列已是有序的情况， 快速排序等同于冒泡排序， 其算法效率将转成O（n）。
最坏可能是每次划分找到的基准元素都是当前序列中最小（或最大）的元素，划分的结果是基准左侧的子区间为空（或右侧的子区间为空），而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数少一。时间复杂度为O（n2）在最好情况下，每次划分所取的基准都是现在无序序列的"中值"元素，划分的结果是基准的左、右两个无序序列的长度基本一致。总的关键字比较次数：O（nlogn）。
尽管快速排序的最坏时间为O（n2），但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快者，快速排序亦因此而得名。它的平均时间复杂度为O（nlogn）。
1.3快速排序算法的分治策略的体现
快速排序的基本思想是基于分治策略的，利用分治法可将快速排序的基本思想描述为：设当前待排序的序列为R[low：high]，其中low<=high，如果序列的规模足够小则直接进行排序，否则分三步来进行处理：①分解②求解子问题③合并。
2 改进算法
支点（基准）元素的选取是影响快速排序算法效率的关键要素。若所选择的基准元素应能将数组E分成大小几近相同的部分，就可以来保证快速排序算法的高效性。即基准元素的选取应遵循平衡子问题的原则，使得划分后的两个子序列的长度尽量相同。
基准元素最佳的选择方法是选择E中元素的中值作为支点元素。但是现实情况和运用中，虽然有些理论上来说好的算法能够做到快速的找到等待排序序列元素的中值，可是因为其开销过大使得快速排序不能够应用于我们的现实实现中，使其效率反而低于基本的快速排序。一般而言基准元素的选取方法根据考虑因素可以存在很多种，但是主要有：（1）“三者取中间”的方法。也即在等待排序元素的序列中，将该序列的第一个元素、中间位置的元素和最后一个元素分别进行比较，选取三者的中间值作为基准元素。（2）随机快速排序。取位于第一个元素low和最后元素high之间的随机数k（left<=k<=right），用E[k]作为基准元素。（3）取第一个元素。即以待排序序列的首元素作为基准元素。（4）取最后一个元素。即以待排序序列的尾元素作为基准元素。（5）取位于中间位置的元素。即以待排序序列位于中间位置的元素作为基准元素。
对于快速排序基准元素的选取，能够有效地改进排序的效率的同时，而又不会额外增加开销的方法主要有以下两种：（1）随机化快速排序。算法思路：每趟划分所选取的基准元素的位置是不固定的，而是通过随机数产生器Random（low，high），找到位于low和high之间的一个随机数k，然后选择E[k]作为基准元素来实现划分并且进行排序。于是使得所需进行排序的序列元素的分布一定会是随机排列的。主要的算法表示如下：
quicksort（&E，low，high）{
//对E[low..high]中元素进行快速排序
int k；//划分后的基准元素位置记录
if low m =randPar（E，low，high）；
//随机分治法找到m的值
quicksort（E，low，k-1）；
//基准元素左侧元素进行排序
quicksort（E，k+1，high）；
//基准元素右侧元素进行排序
}}
int randPar（E，low，high）；//随机分治法{
int t=random（low，high）；
//产生low和high中间一个随机值
change（E[t]，E[low]）；// 基准元素与首位元素交换
return randPar（E，low，high）；
}
（2）“三者取中”的方法的主要点在于：首先，通过比较待排序序列的数据元素中的首位 、中间和末尾位置上的关键字，选择三者的中间值作为基准元素。然后，划分元素之前先将该基准元素与该区间的首个元素进行交换，运用若干条简单的if判断语句即可以实现“三者取中”的规则，在不会增加额外的时间开销和空间开销的同时，又能够显著地改善最坏情况下的快速排序算法的效率。
3 总结与体会
传统的快速排序算法的执行时间主要是浪费在划分操作的实现上，并且与划分是否平衡有很大关系，因此对于基准元素的选取至关重要。由于快速排序算法的执行时递归的，所以就需要程序分配出一个栈空间来存放每一层递归调用的必要的信息以及达到“保护现场”的效果，其最大的容量应该与递归调用的深度保持相同。
对于排序算法的改进以及寻找不同于传统算法的高效的算法，不管是在过去，现在乃至未来，都会是一项艰巨而又重要的挑战。
参考文献：
[1]葛建梅 快速排序的一种改进算法 北华大学计算机科学技术学院 2008.
[2]王秋芬 吕聪颖 周春光 算法设计与分析 清华大学出版社 2011.
[3]王春红 王文霞 快速排序算法的分析与研究 2013.
[4]连顺金 快速排序的一种改进算法 2009.
[5]霍红卫 许进 快速排序算法研究 2002.
关键词：快速排序；基准元素；时间复杂性；划分
对于计算机科学领域而言，排序是一项关键的技术，广泛应用于计算机的信息数据处理操作，特别是在当今大数据时代背景下，数据量巨大，数据元素处理更为频繁，对于排序算法的研究以及改进更为至关重要。由此看来，对于额外空间开销小、运行速度快的高效率的排序方法的研究广受众多算法研究人员的欢迎。算法的好坏的衡量标准主要是该算法运行时的执行时间的快慢以及算法运行时所将占用的额外存储空间的大小。
1 快速排序
1.1基本思想
快速排序的基本思想是：通过一趟排序算法把所需要排序的序列的元素分割成两大块，其中，一部分的元素都要小于或等于另外一部分的序列元素，然后仍根据该种方法对划分后的这两块序列的元素分别再次实行快速排序算法， 排序实现的整个过程可以是递归的来进行调用， 最终能够实现将所需排序的无序序列元素变为一个有序的序列。
1.2性能分析
快速排序的机能在平常情形下可约等于O（nlogn）。在对传统快速排序算法进行具体应用时， 一般选取待排序序列元素中的第一个元素作为基准元素进行比较划分。当给定序列元素几乎有序或有序时，该快速排序算法的速度将会大打折扣；对于给定序列已是有序的情况， 快速排序等同于冒泡排序， 其算法效率将转成O（n）。
最坏可能是每次划分找到的基准元素都是当前序列中最小（或最大）的元素，划分的结果是基准左侧的子区间为空（或右侧的子区间为空），而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数少一。时间复杂度为O（n2）在最好情况下，每次划分所取的基准都是现在无序序列的"中值"元素，划分的结果是基准的左、右两个无序序列的长度基本一致。总的关键字比较次数：O（nlogn）。
尽管快速排序的最坏时间为O（n2），但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快者，快速排序亦因此而得名。它的平均时间复杂度为O（nlogn）。
1.3快速排序算法的分治策略的体现
快速排序的基本思想是基于分治策略的，利用分治法可将快速排序的基本思想描述为：设当前待排序的序列为R[low：high]，其中low<=high，如果序列的规模足够小则直接进行排序，否则分三步来进行处理：①分解②求解子问题③合并。
2 改进算法
支点（基准）元素的选取是影响快速排序算法效率的关键要素。若所选择的基准元素应能将数组E分成大小几近相同的部分，就可以来保证快速排序算法的高效性。即基准元素的选取应遵循平衡子问题的原则，使得划分后的两个子序列的长度尽量相同。
基准元素最佳的选择方法是选择E中元素的中值作为支点元素。但是现实情况和运用中，虽然有些理论上来说好的算法能够做到快速的找到等待排序序列元素的中值，可是因为其开销过大使得快速排序不能够应用于我们的现实实现中，使其效率反而低于基本的快速排序。一般而言基准元素的选取方法根据考虑因素可以存在很多种，但是主要有：（1）“三者取中间”的方法。也即在等待排序元素的序列中，将该序列的第一个元素、中间位置的元素和最后一个元素分别进行比较，选取三者的中间值作为基准元素。（2）随机快速排序。取位于第一个元素low和最后元素high之间的随机数k（left<=k<=right），用E[k]作为基准元素。（3）取第一个元素。即以待排序序列的首元素作为基准元素。（4）取最后一个元素。即以待排序序列的尾元素作为基准元素。（5）取位于中间位置的元素。即以待排序序列位于中间位置的元素作为基准元素。
对于快速排序基准元素的选取，能够有效地改进排序的效率的同时，而又不会额外增加开销的方法主要有以下两种：（1）随机化快速排序。算法思路：每趟划分所选取的基准元素的位置是不固定的，而是通过随机数产生器Random（low，high），找到位于low和high之间的一个随机数k，然后选择E[k]作为基准元素来实现划分并且进行排序。于是使得所需进行排序的序列元素的分布一定会是随机排列的。主要的算法表示如下：
quicksort（&E，low，high）{
//对E[low..high]中元素进行快速排序
int k；//划分后的基准元素位置记录
if low
//随机分治法找到m的值
quicksort（E，low，k-1）；
//基准元素左侧元素进行排序
quicksort（E，k+1，high）；
//基准元素右侧元素进行排序
}}
int randPar（E，low，high）；//随机分治法{
int t=random（low，high）；
//产生low和high中间一个随机值
change（E[t]，E[low]）；// 基准元素与首位元素交换
return randPar（E，low，high）；
}
（2）“三者取中”的方法的主要点在于：首先，通过比较待排序序列的数据元素中的首位 、中间和末尾位置上的关键字，选择三者的中间值作为基准元素。然后，划分元素之前先将该基准元素与该区间的首个元素进行交换，运用若干条简单的if判断语句即可以实现“三者取中”的规则，在不会增加额外的时间开销和空间开销的同时，又能够显著地改善最坏情况下的快速排序算法的效率。
3 总结与体会
传统的快速排序算法的执行时间主要是浪费在划分操作的实现上，并且与划分是否平衡有很大关系，因此对于基准元素的选取至关重要。由于快速排序算法的执行时递归的，所以就需要程序分配出一个栈空间来存放每一层递归调用的必要的信息以及达到“保护现场”的效果，其最大的容量应该与递归调用的深度保持相同。
对于排序算法的改进以及寻找不同于传统算法的高效的算法，不管是在过去，现在乃至未来，都会是一项艰巨而又重要的挑战。
参考文献：
[1]葛建梅 快速排序的一种改进算法 北华大学计算机科学技术学院 2008.
[2]王秋芬 吕聪颖 周春光 算法设计与分析 清华大学出版社 2011.
[3]王春红 王文霞 快速排序算法的分析与研究 2013.
[4]连顺金 快速排序的一种改进算法 2009.
[5]霍红卫 许进 快速排序算法研究 2002.