快速排序
快速排序描述
快速排序之所以能实现“快速”，只要是因为采用分治的策略，分而治之，往往是比线性扫描更加优异的思想。
快速排序可以描述如下：
从要进行排序的序列中找一个元素作为基准的元素V，通过与其他元素进行对比，找到该基准元素所处的位置，然后以该位置为基准将序列分成两个子序列并重复上述的操作。
如：
对序列A={8,4,7,13 ,9,11,5}进行排序，选择第一个元素8为基准元素。
第一步：
通过移动其他元素，寻找基准元素V所属位置
从序列的前后两端开始，先从后往前找出比V小的元素，然后从前往后找出比V大的元素，再交换两者的位置，重复以上操作，直至找不到这样位置。
（1）基准元素为8，将8“拿出来”，8的位置就空了，然后从后往前找到比8小的元素5填补原本8的位置；
（2）从前往后找出比8大的元素13，填补当前的空位置，空位置变为元素13原始的位置；
（3）从后往前找出比8小的元素6，填补当前的空位置，空位置变为元素6原始的位置；
（4）从前往后找出比8大的元素9，填补到当前的空位置，空位置变为9原始的位置；
（5）由于所有元素都以及遍历完毕，所以剩余的空位置就是基准元素所属的位置，将基准元素8填补到空位中。
第二步：
以基准元素为基准，将序列进行分割成两个序列，基准元素以前的元素是一个序列，以后的元素是令一个序列，对两个序列重复上述1中的工作，直到所有的序列不能进行分割为止
上述的序列分割成两个序列，分别为：
和
对两个子序列进行第一步所示的工作，当所有的子序列都不能再分时，排序结束。
快速排序的过程与程序的设计
以一个实例模拟快速排序的过程：
设数组A为将要进行排序的数组，A={8,7,13,11,9,6,7,15,10,5}
快排的过程如下：
其中红色字体表示每一段子序列进行排序时所选择的基准元素，蓝色填充色的方块表示已经找到基准元素所处的位置。
从上图可以看出，每一个进行排序的序列都要经历三个过程：一是选择则基准元素（上述都选择第一个元素为基准元素），二是对基准元素进行寻址，三是将序列划分成两个子序列并重复上述的工作。
程序设计：
第一步：
选择基准元素value，最简单的方式是选择序列的以一个元素作为基准元素；
第二步：
对基准元素进行寻址，这一步的重点是序列的两头同时往中间寻找元素，从前往后寻找比基准元素小的元素，从后向前寻找比基准元素大的元素，每当找到一个元素将该元素填入空位置，则空位置修改为该元素的原始位置；
令End表示从后向前寻找元素的下标，start表示从前向后寻找元素的下标
（1）由于基准元素的位置是空的，首先先从后往前进行寻找:
While(end>start AND A[end]>= value){
end--;
}
A[start]=A[end];
由于从后寻找比基准元素小的元素，如果end位置的元素>=value，end往前移动一格，直到找到元素<基准元素。
start为初始的空位置，对start位置赋值，空位置变为end
（2）当前end的位置是空的，从前往后寻找比value值大的元素填补到end的位置上
While(end>start AND A[start]<=value){
end++;
}
A[end]=A[start]; //start为初始的空位置，对start位置赋值，空位置变为end
由于从前往后寻找比基准元素大的元素，如果start位置的元素<=value，start往后移动一格，直到找到元素>基准元素。
start为初始的空位置，对start位置赋值，空位置变为end
（3）重复以上操作，直到start=end为止，此时空位置就是基准元素value的位置。
第三步：
分割成两个子序列重复上述第一步和第二步。
C++版代码实现
1 #include "stdafx.h" 2 #include <iostream> 3 using namespace std; 4 5 void QuickSort(int *values,int startIndex,int endIndex){ 6 int value = *(values+startIndex); 7 int end=endIndex; 8 int start=startIndex; 9 while(end>start){ 10 while(end>start&&*(values+end)>value){ 11 end--; 12 } 13 *(values+start)=*(values+end); 14 while(end>start&&*(values+start)<=value){ 15 start++; 16 } 17 *(values+end)=*(values+start); 18 } 19 *(values+end)=value; 20 if(startIndex<end-1){ 21 QuickSort(values,startIndex,end-1); 22 } 23 if(end+1<endIndex){ 24 QuickSort(values,end+1,endIndex); 25 } 26 } 27 28 int main(int argc, _TCHAR* argv[]) 29 { 30 int values[]={8,7,13,11,9,6,7,15,10,5,4}; 31 QuickSort(values,0,10); 32 for(int i=0;i<11;i++){ 33 cout<<*(values+i)<<endl; 34 } 35 return 0; 36 }
原文：http://www.cnblogs.com/yonghao/p/5061442.html