【背景】
快速排序（Quicksort）是对冒泡排序的一种改进。
【源码运行环境】
操作系统：Windows 10
编译环境：Dev C++(基于C99标准)
【基本思想】
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
【动态图解】
【源码实现】
/*
*方法名：swap
*作用：交换数组两个位置的元素
*参数：待查找数组 array; 起始位置 i ; 结束位置 j;
*返回值：void
*Author: WellLee
*最后一次修改时间：2018年12月6日 22:18:55
*/
void swap(int array[], int i, int j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
/*
*方法名：Partition
*作用：分区扫描操作 （双向）
*参数：待查找数组 array; 起始位置 low ; 结束位置 high;
*返回值：void
*Author: WellLee
*最后一次修改时间：2018年12月6日 23:41:35
*/
int Partition(int array[], int low, int high)
{
int pivotkey;
pivotkey = array[low];
while(low < high)
{
while(low < high && array[high] >= pivotkey){
high--;
}
swap(array, low, high);
while(low < high && array[low] <= pivotkey){
low++;
}
swap(array, low, high);
}
return low;
}
/*
*方法名：Qsort
*作用：快速排序递归部分（分治思想）
*参数：待查找数组 array; 起始位置 low ; 结束位置 high;
*返回值：void
*Author: WellLee
*最后一次修改时间：2018年12月6日 23:42:11
*/
void Qsort(int array[], int low ,int high)
{
int pivot;
if(low < high)
{
pivot = Partition(array, low, high);
Qsort(array, low, pivot - 1);
Qsort(array, pivot + 1, high);
}
}
/*
*方法名：QuickSort
*作用：快速排序主函数
*参数：待查找数组 array; 数组长度length;
*返回值：void
*Author: WellLee
*最后一次修改时间：2018年12月6日 23:42:44
*/
void QuickSort(int array[], int length)
{
Qsort(array, 1 ,length);
}
【分析】
快速排序具有如下特点：
弱势：当序列已经就绪，并每次划分元素选取为最左边或者最右边的值，一次递归划分仅去除一个元素，既是划分元素本身,程序将递归调用n次，而算法也演变为插入排序，比较次数达到\( \frac{n(n+1)}{2} \)次；
优势：快速排序满足分治递推式：\(C_n=2C_{n/2} + n\)，最终化解为\(C_n=n \lg n\)；但此种情况需要划分点在序列的中间位置；
性质：算法不稳定，任何相等的元素有可能在交换的过程中被重排成不同的序列。快速排序中关键点是划分元素的选取。这个实现方式与上一个实现最大的差距就在于对等于划分元素值的处理上，还有就是本实现的遍历方式是两边向中间，而并不是只有一边到另外一边；
时间：当每次划分大约都将序列二分划分，运行时间为\(n \log n \) ，平均比较次数为\(2n \lg n \)；最坏情况下，快速排序使用\( \frac{n(n+1)}{2} \)次比较；系统堆栈耗用的大小与\(\log n\)成比例，退化的情况下与n成比例；
【参考文献】
-
《大话数据结构》.程杰.清华大学出版社
-
笔试算法题（54）：快速排序实现之单向扫描、双向扫描（single-direction scanning, bidirectional scanning of Quick Sort)