快速排序及其改进算法

2017/06/02

算法设计与分析结课报告

快速排序及其改进算法-Fast sorting and its improved algorithm

摘 要

快速排序是排序算法中性能较好的一种,但存在对数据有序或者基本有序的情形下的性能瓶颈问题。

本文除了介绍经典的快速排序算法之外,还将介绍一些对排序算法优化的算法。通过实验数据证明改进算法的合理性和优越性,但也不乏一些局限性。在实际工作参考和使用的过程中,还要结合具体情况对快速排序算法进行优化。

关键词 快速排序算法;快速排序改进算法;

第1章 引 言

快速排序(Quicksort),又称划分交换排序(partition-exchange sort),由C. A. R. Hoare在1962年提出。快速排序算法的最好时间复杂性为O(n·log n),最坏的时间复杂性为O (n2),但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n·log n)算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。

第2章 快速排序

2.1 快速排序算法的基本思想

快速排序的基本思想是:通过一趟扫描将待排序的元素分割成独立的三个序列:第一个序列中的所有元素均不大于基准元素、第二个序列是基准元素、第三个序列中的所有元素均不小于基准元素。由于第二个序列已经处于正确位置,因此需要再按照此方法对第一个序列和第三个序列分别进行排序,整个排序的过程可以递归进行,最终可使整个序列变成有序序列。

(1)快速排序算法的分治策略体现 快速排序的基本思想是基于分治策略的,利用分治法可将快速排序的基本思想描述如下:设当前待排序的序列为R[ low : high ],其中 low≤high,如果序列的规模足够小则直接进行排序,否则分三步处理:①分解 ②求解子问题 ③合并

(2)基准元素的选取 从待排序序列中选取指导划分的基准元素是决定算法性能的关键。基准元素的选取应该遵循平衡子问题的原则,即使得划分后的两个子序列的长度尽量相同。选取的基准元素一定要保证算法正常结束。

2.2 快速排序算法描述

void QuickSort(int R[], int low, int high)
{
  int pivotpos; //基准元素
  if(low < high) //区间长度大于1时才须排序
  {
    pivotpos = Partition(R, low, high); //对元素集做划分
    QuickSort(R, low, pivotpos-1); //对左区间递归排序
    QuickSort(R, pivotpos+1, high); //对右区间递归排序
  }
}

对待排元素集R进行排序,最初的调用是QuickSort(R,1,length[S])。但是快速排序算法的关键是 Partition过程,由它对元素集及其子集进行划分。

2.3 快速排序算法一次划分的步骤

假设待排序序列为R[ low : high ],该划分过程以第一个元素作为基准元素。 步骤1:设置两个参数i和j,它们的初值分别为待排序序列的下界和上界,即i=low,j=high。 步骤2:选取待排序序列的第一个元素R[low]作为基准元素,并将该值赋给变量pivot(基准元素)。 步骤3:令j自j位置开始向前扫描,直到扫描到第一个小于pivot的元素R[j],将R[j]与R[i]进行交换,i++。 步骤4:令i自i位置开始向后扫描,直到扫描到第一个大于pivot的元素R[i],将R[j]与R[i]进行交换,j–。 步骤5:重复步骤3、4,从两端向中间靠拢直至i=j。此时i和j同时指向pivot的最终位置。

划分算法描述如下:

int Partition(int R[], int low, int high)
{
  int I = low, j = high, pivot = R[low];//用序列的第一个元素作为基准元素
  while( i < j ) //从序列两端向中间扫描,直至i等于j
  {
    while( i < j && R[j] >= pivot)
      j--; //从后往前查找第1个小于pivot的元素
    if(i<j) //查找到小于pivot的元素
      swap(R[i++], R[j]); //交换R[i]和R[j],并且i+1
    while( i < j && R[i] <= pivot)
      i++; //从前往后查找第1个大于pivot的元素
    if(i<j) //查找到大于pivot的元素
      swap(R[i], R[j--]); //交换R[i]和R[j],并且j-1
  }
return j;
}

2.4 优缺点分析

快速排序算法的时间主要耗费在划分操作上,并于划分是否平衡密切相关。 (1)最坏时间复杂性 最坏情况为每次划分选取的基准元素为待排序列最小(或最大)元素,导致划分后仅有一个元素到达正确的位置。并且可以求得最坏时间复杂性为O (n2)。 (2)最好时间复杂性 最好情况为每次划分选取的基准元素为待排序列的“中值”元素,此时时间复杂性为O (n·logn)。 (3)平均时间复杂度 使用归纳法可求得平均时间复杂性的数量级也为O (n·logn)。 (4)空间复杂性 最好情况下递归所需栈空间为O (n·logn),最坏O (n),平均O (logn)。

优点:快速排序的优点在于平均性能好,快速排序算法是基于元素比较的内部排序算法中最快的,因此得名快速排序。 缺点:当初始序列呈基本有序状态时,退化为冒泡排序,时间复杂度下降为O (n2),当序列有序或者逆序的情况下最不利于发挥其长处。

第3章 改进算法

逐个介绍自己查到的改进算法(作者、论文题目、改进的具体内容,效果如何)

3.1 通过优化基准元素的选取

以下两种方法来自《现代电子技术》期刊第36卷第20期 文章题目:《快速排序算法的分析与研究》 作者:王春红; 王文霞

第 1 种方法是“三者取中值”的规则[1-2]。首先,比较待排数据中第一 、中间和最后一个位置上元素的关键字,取三者的中值为基准元素。然后,在划分开始前将该基准元素和该区间的第1个元素进行交换,此后的划分过程与上面所给的 PARTITION 算法完全相同。实践表明,采用三元素取中值的只需要几条if语句的判断即可,在时间上、空间上不会增加额外的开销,但结果可以大大改善快速排序在最坏情况下的性能。

第2种方法是随机化快速排序[3]。算法思路:每趟划分选取的基准元素不是固定的,而是用随机数产生器 Random(l, h) 随机选取位于 l 和 h 之间的随机数 t(l ≤ t ≤ h),然后用 S[t] 作为支点元素。这就打破了传统快速排序对数据元素初始输的依赖,相当于S[l..h]中的元素是随机分布的。

随机化快速排序算法描述如下:

void Randomize_QuickSort(int R[], int low, int high)
{
  int pivotpos; //基准元素
  if(low < high) //区间长度大于1时才须排序
  {
    pivotpos = Randomize_Partition(R, low, high); //使用随机分治法来划分
    Randomize_QuickSort(R, low, pivotpos-1); //对左区间递归排序
    Randomize_QuickSort(R, pivotpos+1, high); //对右区间递归排序
  }
}

int Randomize_Partition(int R[], int low, int high) //随机分治法
{
  int t = Random(low, high); //在low和high之间产生一个随机整数
  Swap(R[t],R[l]); //将选中的基准元素和首元素交换位置
  Retrun Partition(int R[], int low, int high); //调用常规划分方法
}

经实验对比,在元素有序情况下,两种排序算法在规模分别为100,200,500时比较次数的统计情况对比,如表3.1所示。

数据规模 100 200 500
随机快排比较次数 854 2078 6194
快速排序比较次数 4950 19900 124750

表3.1 两种排序算法的比较


以下方法来自《计算机工程》期刊第37卷第6期

文章题目:《高效快速排序算法研究》 作者:汤亚玲;秦锋

该篇文章提到的高效快速排序算法[4]和上面提到的“三者取中值”算法类似,基本思想是计算待排序序列的平均值,将平均值作为基准元素。由于算法从待排序数据均值的角度进行划分,能保证在最短的划分次数下,实现每次排序码划分成大小基本相等的两部分,因此快速排序的理想情况下的性能分析对于高效快速排序是适用的,即高效快速排序的性能始终都能保持在O(nlogn)。

从性能结果上看,每次求数据均值的时间代价并没有影响算法的整体效率,反而从根本上保证了算法性能的稳定性。同时,由于其划分均匀,性能稳定,数据是否已经有序或者是否存在孤立的数据点对排序性能的影响都很小。

下面的代码为递归思想描述的高效快速排序算法:

/*求出数组中元素从ay[l]到ay[r]中的平均值*/
int f_avg(int *ay,unsigned long int l,unsigned long int r,long int *avg) 
{ int i; 
  if(r<l) return 0; /*检验参数 l,r 的合法性*/
  else
  { *avg=0; 

    for( i=l;i<=r;i++) 
      *avg+=ay[i]/(r-l+1); /*求出平均值*/
    return 1; 
  } 
} 
/*高效快速排序*/
/*对数组 ay 中下标从 l 到 r 的元素进行排序*/
void EQ_sort(int *ay, unsigned long int l, unsigned long int r ) 
{
  unsigned long int i,j; long int mid; 
  if(r<=l)return; /*待排序码个数小于 2 个,算法结束*/
  if(!f_avg(ay,l,r,&mid)) return; 
  i=l;j=r; 
  while(i<j) 
  { while(ay[i]<=mid && i<j)i++; 
    while(ay[j]>=mid && i<j)j--; 
    if(i<j)
      swap(a[i],a[j]); /*交换*/
    else break; 
  }
  if(l<j&&j<r) /*对划分得到的子序列进行递归调用*/
  { Q_sort(ay, l, j-1); 
    Q_sort(ay, j, r); 
  } 
}

在迅驰 1.6 GHz、512 MB 内存,VC 6.0 平台上,对不同数据量进行测试(数据由随机函数 Rand()产生)。表 3.2、3.3 给出了各种排序方法在每种情形下所消耗的时间。

排序数个数 归并排序 堆排序 快速排序 高效快速排序
800 0 0 0 0
8000 10 10 0 0
80 000 30 40 40 0
800 000 470 511 401 10
8 000 000 3525 9492 7761 120

表3.2 一趟排序消耗时间对比(单位:ms)


排序数个数 归并排序 堆排序 快速排序 高效快速排序
800 0 0 0 0
8 000 20 10 170 0
80 000 20 10 340 20
800 000 80 70 堆栈溢出 30
8 000 000 671 910 堆栈溢出 40

表3.3 二趟排序消耗时间对比(单位:ms)

高效快速排序是一种能稳定地将快速排序的时间效率改进到 nlogn 数量级的算法,通过充分的实验数据和理论证明了该算法的正确性和实用性。同时,高效快速排序递归深度为 logn,这在待排序数据量非常大(如达到天文数字级别)时,其引起的递归调用的时空开销不容忽视。

3.2 用插入排序改进快速排序算法[5]

以下方法来自《上饶师范学院学报》期刊第21卷第6期

文章题目:《快速排序的改进算法》 作者:周玉林;郑建秀

根据插入排序在待排对象基本有序下具有较好性能这一特点[6],改进快速排序,在快速排序的递归调用中,只对长度大于等于某数k时递归,最后再对整个序列用插入排序来完成排序过程。

改进后的算法描述如下:

QUICK-INSERT-SORT(A,1,n)
 QUICKSORT(A,1,n)  //先调用快速排序
 For j= 2 to n do  //再采用插入排序对基本有序序列进行排序
  x= A[j]
  i= j - 1
  while i> 0 and A[i]> x do
   A[i+1]= A[i]
   i= i- 1
  if(i+1≠j)  then  A[i+1] = x

QUICKSORT(A,p,r)
  if r–p > k then //当区间长度大于k时递归, k为指定的某数
   q= PARTITION(A,p,r)
   QUICKSORT(A,p,q- 1)
   QUICKSORT(A,q+ 1,r)

PARTITION(A,p,r)
  x= A[p]
  i= p
  j= r
  while(i<j)do
  while( i<j )and( A[j]>x )do
    j= j - 1
  A[i]= A[j]
  i= i+ 1
  while(i< j)and(A[i]< x)do
   i= i+ 1
  A[j]= A[i]
  j= j- 1
A[i]= x

改进后算法的平均时间复杂性为:2nln(n/k)- 3(n+ 1)/(k+ 1)+ nk/4+ O(lnn),并且经计算和实验数据得出,使用该改进算法,当k=8左右的值时(即只对长度大于8的元素集合使用快速排序,否则使用插入排序)效果最佳!具体计算方法和实验数据请请参考当期文章。

第4章 总结与体会

快速排序的基本思想是基于分治策略,将一个序列利用基准元素分割为独立的三个序列(包括基准数)。然后对三个序列分别进行排序,整个排序的过程可以递归进行。 优化快速排序,关键优化基准元素的选取,基准元素的大小直接决定了快速排序时间的复杂度。

快速排序对于数量多,越无序的数列排序效果越好。所以在数据量少量,或者数据趋近有序的情况下可以使用其他排序算法进行排序。快速排序的使用也可以融合的其他排序算法优点,如在数据量小的时候使用插入排序等方法更加便捷。

参考文献

[1] 王善坤,陶祯蓉.一种三路划分快速排序的改进算法[J].计算机应用研究,2012(7):2513-2516.

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

[3] 王春红,王文霞.快速排序算法的分析与研究[J].现代电子技术,2012,36(20):54-56.

[4] 汤亚玲,秦锋. 高效快速排序算法研究[J]. 计算机工程,2011,37(6):75-78.

[5] 周玉林,郑建秀. 快速排序的改进算法[J]. 上饶师范学院学报,2001,20(6):11-15.

[6] 潘金贵,顾铁成,等.现代计算机常用数据结构和算法[M].南京:南京大学出版社,1994.

Post Directory