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) 

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) 

/************************************************************************* 
  > 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; 
}

[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;