C++快速排序的分析與優(yōu)化詳解

更新時間：2014年08月14日 11:04:09 投稿：shichen2014

這篇文章主要介紹了C++快速排序的分析與優(yōu)化,非常經(jīng)典的算法,分析也較為詳盡,需要的朋友可以參考下

相信學過數(shù)據(jù)結(jié)構(gòu)與算法的朋友對于快速排序應該并不陌生，本文就以實例講述了C++快速排序的分析與優(yōu)化，對于C++算法的設計有很好的借鑒價值。具體分析如下：

一、快速排序的介紹

快速排序是一種排序算法，對包含n個數(shù)的輸入數(shù)組，最壞的情況運行時間為Θ(n2)[Θ 讀作theta]。雖然這個最壞情況的運行時間比較差，但快速排序通常是用于排序的最佳的實用選擇。這是因為其平均情況下的性能相當好：期望的運行時間為 Θ(nlgn)，且Θ(nlgn)記號中隱含的常數(shù)因子很小。另外，它還能夠進行就地排序，在虛擬內(nèi)存環(huán)境中也能很好的工作。

和歸并排序一樣，快速排序也是基于分治法（Divide and conquer）：

分解：數(shù)組A[p..r]被劃分成兩個(可能為空)的子數(shù)組A[p..q-1]和A[q+1..r]，使得A[p..q-1]中的每個元素都小于等于A[q]，A[q+1..r]中的每個元素都大于等于A[q]。這樣元素A[q]就位于其最終位置上了。

解決：通過遞歸調(diào)用快速排序，對子數(shù)組A[p..q-1]和A[q+1..r]排序。

合并：因為兩個子數(shù)組是就地排序，不需要合并，整個數(shù)組已有序。

偽代碼如下：

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、最壞情況

快速排序的最壞情況發(fā)生在當數(shù)組已經(jīng)有序或者逆序排好的情況下。這樣的話劃分過程產(chǎn)生的兩個區(qū)域中有一個沒有元素，另一個包含n-1個元素。此時算法的運行時間可以遞歸地表示為：T(n) = T(n-1)+T(0)+Θ(n)，遞歸式的解為T(n)=Θ(n^2)?？梢钥闯?，快速排序算法最壞情況運行時間并不比插入排序的更好。

2、最好情況

如果我們足夠幸運，在每次劃分操作中做到最平衡的劃分，即將數(shù)組劃分為n/2:n/2。此時得到的遞歸式為T(n) = 2T(n/2)+Θ(n)，根據(jù)主定理的情況二可得T(n)=Θ(nlgn)。

3、平均情況

假設一：快排中的劃分點非常偏斜，比如每次都將數(shù)組劃分為1/10 : 9/10的兩個子區(qū)域，這種情況下運行時間是多少呢？運行時間遞歸式為T(n) = T(n/10)+T(9n/10)+Θ(n)，使用遞歸樹解得T(n)=Θ(nlgn)?？梢钥闯觯攧澐贮c非常偏斜的時候，運行時間仍然是Θ(nlgn)。

假設二：Partition所產(chǎn)生的劃分既有“好的”，也有“差的”，它們交替出現(xiàn)。這種平均情況下運行時間又是多少呢？這時的遞歸式為（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)

可以看出，當好、差劃分交替出現(xiàn)時，快排的運行時間就如全是好的劃分一樣，仍然是Θ(nlgn) 。

三、快排的優(yōu)化

經(jīng)過上面的分析可以知道，在輸入有序或逆序時快速排序很慢，在其余情況則表現(xiàn)良好。如果輸入本身已被排序，那么就糟了。那么我們?nèi)绾未_保對于所有輸入，它均能夠獲得較好的平均情況性能呢？前面的快速排序我們默認使用數(shù)組中第一個元素作為主元。假設隨機選擇數(shù)組中的元素作為主元，則快排的運行時間將不依賴于輸入序列的順序。我們把隨機選擇主元的快速排序叫做Randomized Quicksort。

在隨機化的快速排序中，我們不是始終選擇第一個元素作為主元，而是從數(shù)組A[p…r]中隨機選擇一個元素，然后將其與第一個元素交換。由于主元元素是隨機選擇的，我們期望在平均情況下，對輸入數(shù)組的劃分能夠比較對稱。

偽代碼如下：

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萬個元素的有序序列分別進行傳統(tǒng)的快速排序和隨機化的快速排序，并比較它們的運行時間：

/************************************************************************* 
  > 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; 
} 
 
// 傳統(tǒng)劃分操作 
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); 
} 
 
// 傳統(tǒng)快排 
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; 
  // 初始化數(shù)組 
  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; 
}

運行結(jié)果如下：

[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).

從運行結(jié)果可以看出，對于有序的輸入，隨機化版本的快速排序的效率會高很多。

問題記錄：

我們知道交換兩個變量的值有以下三種方法：

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;

但是你會發(fā)現(xiàn)在本程序中，如果swap函數(shù)使用后面兩種方法會出錯。由于方法二和方法三沒有使用中間變量，它們交換值的原理是直接對變量的內(nèi)存單元進行操作。如果兩個變量對應的同一內(nèi)存單元，則經(jīng)過兩次加減或異或操作，內(nèi)存單元的值已經(jīng)變?yōu)榱?，因而不能實現(xiàn)變量值交換。所以當需要交換值的變量可能是同一變量時，必須使用第三變量實現(xiàn)交換，否則會對變量清零。

您可能感興趣的文章: