C/C++教程

C++快速排序的分析与优化详解

本文主要是介绍C++快速排序的分析与优化详解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

相信学过数据结构与算法的朋友对于快速排序应该并不陌生,本文就以实例讲述了C++快速排序的分析与优化,对于C++算法的设计有很好的借鉴价值。具体分析如下:

一、快速排序的介绍

快速排序是一种排序算法,对包含n个数的输入数组,最坏的情况运行时间为Θ(n2)[Θ 读作theta]。虽然这个最坏情况的运行时间比较差,但快速排序通常是用于排序的最佳的实用选择。这是因为其平均情况下的性能相当好:期望的运行时间为 Θ(nlgn),且Θ(nlgn)记号中隐含的常数因子很小。另外,它还能够进行就地排序,在虚拟内存环境中也能很好的工作。

和归并排序一样,快速排序也是基于分治法(Divide and conquer):

分解:数组A[p..r]被划分成两个(可能为空)的子数组A[p..q-1]和A[q+1..r],使得A[p..q-1]中的每个元素都小于等于A[q],A[q+1..r]中的每个元素都大于等于A[q]。这样元素A[q]就位于其最终位置上了。

解决:通过递归调用快速排序,对子数组A[p..q-1]和A[q+1..r]排序。

合并:因为两个子数组是就地排序,不需要合并,整个数组已有序。

伪代码如下:

PARTITION(A, p, r) 
  x = A[p] 
  i = p 
  for j=p+1 to r 
    do if A[j] <= x 
      then i = i+1 
         exchange(A[i],A[j]) 
  exchange(A[p], A[i]) 
  return i 
 
QUICKSORT(A, p, r) 
  if p < r 
    then q = PARTITION(A, p, r) 
       QUICKSORT(A, p, q-1) 
       QUICKSORT(A, q+1, r) 

二、性能分析

1、最坏情况

快速排序的最坏情况发生在当数组已经有序或者逆序排好的情况下。这样的话划分过程产生的两个区域中有一个没有元素,另一个包含n-1个元素。此时算法的运行时间可以递归地表示为:T(n) = T(n-1)+T(0)+Θ(n),递归式的解为T(n)=Θ(n^2)。可以看出,快速排序算法最坏情况运行时间并不比插入排序的更好。

2、最好情况

如果我们足够幸运,在每次划分操作中做到最平衡的划分,即将数组划分为n/2:n/2。此时得到的递归式为T(n) = 2T(n/2)+Θ(n),根据主定理的情况二可得T(n)=Θ(nlgn)。

3、平均情况

假设一:快排中的划分点非常偏斜,比如每次都将数组划分为1/10 : 9/10的两个子区域,这种情况下运行时间是多少呢?运行时间递归式为T(n) = T(n/10)+T(9n/10)+Θ(n),使用递归树解得T(n)=Θ(nlgn)。可以看出,当划分点非常偏斜的时候,运行时间仍然是Θ(nlgn)。

假设二:Partition所产生的划分既有“好的”,也有“差的”,它们交替出现。这种平均情况下运行时间又是多少呢?这时的递归式为(G表示Good,B表示Bad):

G(n) = 2B(n/2) + Θ(n)

B(n) = G(n-1) + Θ(n)

解:G(n) = 2(G(n/2-1) + Θ(n/2)) + Θ(n) = 2G(n/2-1) + Θ(n) = Θ(nlgn)

可以看出,当好、差划分交替出现时,快排的运行时间就如全是好的划分一样,仍然是Θ(nlgn) 。

三、快排的优化

经过上面的分析可以知道,在输入有序或逆序时快速排序很慢,在其余情况则表现良好。如果输入本身已被排序,那么就糟了。那么我们如何确保对于所有输 入,它均能够获得较好的平均情况性能呢?前面的快速排序我们默认使用数组中第一个元素作为主元。假设随机选择数组中的元素作为主元,则快排的运行时间将不 依赖于输入序列的顺序。我们把随机选择主元的快速排序叫做Randomized Quicksort。

在随机化的快速排序中,我们不是始终选择第一个元素作为主元,而是从数组A[p…r]中随机选择一个元素,然后将其与第一个元素交换。由于主元元素是随机选择的,我们期望在平均情况下,对输入数组的划分能够比较对称。

伪代码如下:

RANDOMIZED-PARTITION(A, p, r) 
  i = RANDOM(p, r) 
  exchange(A[p], A[i]) 
  return PARTITION(A, p, r) 
 
RANDOMIZED-QUICKSORT(A, p, r) 
  if p < r 
    then q = RANDOMIZED-PARTITION(A, p, r) 
      RANDOMIZED-QUICKSORT(A, p, q-1) 
      RANDOMIZED-QUICKSORT(A, q+1, r) 

我们对3万个元素的有序序列分别进行传统的快速排序 和 随机化的快速排序,并比较它们的运行时间:

/************************************************************************* 
  > File Name: QuickSort.cpp 
  > Author: SongLee 
 ************************************************************************/ 
#include<iostream> 
#include<cstdlib> // srand rand 
#include<ctime> // clock_t clock 
using namespace std; 
 
void swap(int &a, int &b) 
{ 
  int tmp = a; 
  a = b; 
  b = tmp; 
} 
 
// 传统划分操作 
int Partition(int A[], int low, int high) 
{ 
  int pivot = A[low]; 
  int i = low; 
  for(int j=low+1; j<=high; ++j) 
  { 
    if(A[j] <= pivot) 
    { 
      ++i; 
      swap(A[i], A[j]); 
    } 
  } 
  swap(A[i], A[low]); 
  return i; 
} 
 
// 随机化划分操作,随机选择pivot 
int Partition_Random(int A[], int low, int high) 
{ 
  srand(time(NULL)); 
  int i = rand() % (high+1); 
  swap(A[low], A[i]); 
  return Partition(A, low, high); 
} 
 
// 传统快排 
void QuickSort(int A[], int low, int high) 
{ 
  if(low < high) 
  { 
    int pos = Partition(A, low, high); 
    QuickSort(A, low, pos-1); 
    QuickSort(A, pos+1, high); 
  } 
} 
 
// 随机化快速排序 
void QuickSort_Random(int A[], int low, int high) 
{ 
  if(low < high) 
  { 
    int pos = Partition_Random(A, low, high); 
    QuickSort_Random(A, low, pos-1); 
    QuickSort_Random(A, pos+1, high); 
  } 
} 
 
int main() 
{ 
  clock_t t1, t2; 
  // 初始化数组 
  int A[30000]; 
  for(int i=0; i<30000; ++i) 
    A[i] = i+1; 
     
  t1 = clock(); 
  QuickSort(A, 0, 30000-1); 
  t1 = clock() - t1; 
  cout << "Traditional quicksort took "<< t1 << " clicks(about " << ((float)t1)/CLOCKS_PER_SEC << " seconds)." << endl; 
 
  t2 = clock(); 
  QuickSort_Random(A, 0, 30000-1); 
  t2 = clock() - t2; 
  cout << "Randomized quicksort took "<< t2 << " clicks(about " << ((float)t2)/CLOCKS_PER_SEC << " seconds)." << endl; 
 
  return 0; 
}

运行结果如下:

[songlee@localhost ~]$ ./QuickSort  
Traditional quicksort took 1210309 clicks(about 1.21031 seconds). 
Randomized quicksort took 457573 clicks(about 0.457573 seconds). 
[songlee@localhost ~]$ ./QuickSort  
Traditional quicksort took 1208038 clicks(about 1.20804 seconds). 
Randomized quicksort took 644950 clicks(about 0.64495 seconds). 

从运行结果可以看出,对于有序的输入,随机化版本的快速排序的效率会高很多。

问题记录:

我们知道交换两个变量的值有以下三种方法:

int tmp = a; // 方法一 
a = b; 
b = tmp 
 
a = a+b; // 方法二 
b = a-b; 
a = a-b; 
 
a = a^b; // 方法三 
b = a^b; 
a = a^b;

但是你会发现在本程序中,如果swap函数使用后面两种方法会出错。由于方法二和方法三没有使用中间变量,它们交换值的原理是直接对变量的内存单元进行操作。如果两个变量对应的同一内存单元,则经过两次加减或异或操作,内存单元的值已经变为了0,因而不能实现变量值交换。所以当需要交换值的变量可能是同一变量时,必须使用第三变量实现交换,否则会对变量清零。

这篇关于C++快速排序的分析与优化详解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!