原文链接：http://www.cnblogs.com/Anker/archive/2013/01/24/2875234.html
本章介绍了快速排序及其算法分析，快速排序采用的是分治算法思想，对包含n个数的输入数组，最坏情况下运行时间为θ(n^2)，但是平均性能相当好，期望的运行时间为θ(nlgn)。另外快速排序能够就地排序（我理解是不需要引入额外的辅助空间，每次划分能确定一个元素的具体位置），在虚拟环境中能很好的工作。
1、快速排序的描述
快速排序算法采用的分治算法，因此对一个子数组A[p…r]进行快速排序的三个步骤为：
（1）分解：数组A[p...r]被划分为两个（可能为空）子数组A[p...q-1]和A[q+1...r]，给定一个枢轴，使得A[p...q-1]中的每个元素小于等于A[q]，A[q+1...r]中的每个元素大于等于A[q]，q下标是在划分过程中计算得出的。
（2）解决：通过递归调用快速排序，对子数组A[p...q-1]和A[q+1...r]进行排序。
（3）合并：因为两个子数组是就地排序，不需要合并操作，整个数组A[p…r]排序完成。
快速排序关键过程是对数组进行划分，划分过程需要选择一个主元素（pivot element）作为参照，围绕着这个主元素进划分子数组。举个列说明如何划分数组，现有子数组A={24，15，27，5，43，87，34}，以最后一个元素为主元素进行划分，划分过程如图所示：
书中给出了划分过程的伪代码：
PARTITION(A,p,r) x = A[r] //将最后一个元素作为主元素 i = p-1 for j=p to r-1 //从第一个元素开始到倒数第二个元素结束，比较确定主元的位置 if A[j] <= x i = i+1 exchange A[i] <-> A[j] exchange A[i+1]<->A[r] //最终确定主元的位置 return i+1 //返回主元的位置
根据划分过程的为代码，书中又给出了快速排序的伪代码：
QUICKSORT(A,p,r) 2 if p<r 3 q = PARTITION(A,p,r) //确定划分位置 4 QUICKSORT(A,p,q-1) //子数组A[p...q-1] 5 QUICKSORT(Q,q+1,r) //子数组A[q+1...r]
完整c++代码：
1 #include<iostream> 2 using namespace std; 3 4 void display (int a[], int n); 5 void swap (int& n, int& m); 6 int partition (int a[], int p, int r); 7 void quick_sort (int a[], int p, int r); 8 9 int main() 10 { 11 int a[100]; 12 int n; 13 while (cin >> n) 14 { 15 for (int i = 0; i < n; i++) 16 cin >> a[i]; 17 quick_sort (a, 0, n - 1); 18 display (a, n); 19 } 20 return 0; 21 } 22 23 void display (int a[], int n) 24 { 25 for (int i = 0; i < n; i++) 26 cout << a[i] << " "; 27 cout << endl; 28 } 29 30 void swap (int& n, int& m) 31 { 32 int temp; 33 temp = n; 34 n = m; 35 m = temp; 36 } 37 38 int partition (int a[], int p, int r) 39 { 40 int i = p - 1; 41 for (int j = p; j < r; j++) 42 { 43 if (a[j] < a[r]) 44 { 45 swap (a[++i], a[j]); 46 } 47 } 48 swap (a[++i], a[r]); 49 return i; 50 } 51 52 void quick_sort (int a[], int p, int r) 53 { 54 if (p < r) 55 { 56 int q = partition (a, p, r); 57 quick_sort (a, p, q - 1); 58 quick_sort (a, q + 1, r); 59 } 60 }
原文：http://www.cnblogs.com/hixin/p/4357477.html