算法介绍：快速排序其实一种根据需找某个元素的具体位置进行排序的方法。比如所存在如下数组

选择第一个元素5，找到5最终的位置，即5的左边的数都小于或者等于5，右边的数都大于或者等于5.

从"6"开始，可知6大于5，此处停住，从“2”开始2小于5，因此交换6与2的位置，然后接着往下走，将所有小于等于5的都放在左边，大于等于5的都放在右边，等到如下所示的数组：

此时的索引在4的位置，然后交换5和4的位置，这样就保证了左边的都小于5，右边的都大于5。

然后再分别对5的左右两边重复上述过程即可将数组按升序排列。

算法发复杂度分析：假设每次都从中间将数组分开，且算法的运行时间为T(N)，则依据算法的执行过程可知，找到当前元素的位置需要扫面一遍数组即N次，然后再对此元素两边的子数组重复上述操作。为此T(N)=2*T(N/2)+N，解得T(N)=O(NlogN)。

算法实现：

寻找切分点

int sort::partition(int* a, const int low, const int high)
{
?int value = a[low];
?int i=low;
?int j=high+1;
?while (1)
?{
? while(a[++i] < value)
? {
? ?if(i == high) break;
? }
? while(value < a[--j]);
? ?//a[low] == value,因此可以知道j==low时，此判断条件不成立，可知此时i必大于j，从而整个循环结束。
? if(i>=j)
? ?break;
? swap(a,i,j);
?}
?swap(a,low,j);
?return j;
}

快速排序：

void sort::quick_sort(int* a, const int low, const int high)
{
?if(low >= high)
? return;
?int loc = partition(a,low,high);
?quick_sort(a,low,loc-1);
?quick_sort(a,loc+1,high);
}

上述即为快速排序的具体实现。但是对上述算法还有很多的改进之处，比如说对存在大多数重复数据的数组排序，初始切分点的选取等等都可以进行改进。具体的改进如下所示：

对于较小的子数组使用插入排序：

void sort::insert_sort_update(int* a, const int n)
{
?for(int i=1; i?{
? int j=i;
? int temp = a[i];
? for(; j>0 && temp < a[j-1]; j--)
? {
? ?a[j] = a[j-1];
? }
? a[j] = temp;
?}
}
void sort::quick_sort_update_with_insert_sort(int* a, const int low, const int high)
{
?if(high <= low+N)
?{
? insert_sort_for_update(a,low,high);
? return;
?}
?int loc = partition(a,low,high);
?quick_sort_update_with_insert_sort(a,low,loc-1);
?quick_sort_update_with_insert_sort(a,loc+1,high);
}

对于含有大多数重复元素的改进：

void sort::quick_sort_update_with_partition(int* a,const int low, const int high)
{
?if(low>=high)
? return;
?int lt = low;
?int gt = high;
?int value = a[low];
?int i=low+1;
?while(i<=gt)
?{
? if(a[i]? {
? ?swap(a,i,lt);
? ?i++;
? ?lt++;
? }
? else if(a[i] > value)
? {
? ?swap(a,i,gt);
? ?gt--;
? }
? else
? {
? ?i++;
? }
?}
?quick_sort_update_with_partition(a,low,lt-1);
?quick_sort_update_with_partition(a,gt+1,high);
}

上述博文主要介绍了快速排序算法及其改进。欢迎拍砖