(一)概述
快速排序(Quick Sort)是一种有效的排序算法。虽然算法在最坏的情况下运行时间为O(n^2)，但由于平均运行时间为O(nlogn)，并且在内存使用、程序实现复杂性上表现优秀，尤其是对快速排序算法进行随机化的可能，使得快速排序在一般情况下是最实用的排序方法之一。
快速排序被认为是当前最优秀的内部排序方法。
(二)实现
快速排序的实现基于分治法，具体分为三个步骤。假设待排序的序列为L[m..n]。
分解：序列L[m .. n]被划分成两个可能为空的子序列L[m .. pivot-1]和L[pivot+1 .. n]，使L[m .. pivot-1]的每个元素均小于或等于L[pivot]，同时L[pivot+1.. n]的每个元素均大于L[pivot]。其中L[pivot]称为这一趟分割中的主元（也称为枢轴、支点）。
解决：通过递归调用快速排序，对子序列L[m .. pivot-1]和L[pivot+1 .. r]排序。
合并：由于两个子序列是就地排序的，所以对它们的合并不需要操作，整个序列L[m .. n]已排好序。
(三)性质
内部排序
快速排序是一种内部排序方法。也就是说快速排序的排序对象是读入内存的数据。
比较排序
快速排序确定元素位置的方法基于元素之间关键字大小的比较。
所有基于比较方法的排序方法的时间下界不会低于O(nlgn)。这个结论的具体证明，请参考有关算法的书籍，例如《算法导论》（第一版）第8章（第二版在第七章QuickSort)。
在理想情况下，能严格地达到O(nlgn)的下界。一般情况下，快速排序与随机化快速排序的平均情况性能都达到了O(nlgn)。
不稳定性
快速排序是一种不稳定的排序方法。简单地说，元素a1, a2的关键字有a1.key=a2.key，则不稳定的排序方法不能保证a1, a2在排序后维持原来的位置先后关系。
原地排序
在排序的具体操作过程中，除去程序运行实现的空间消费（例如递归栈），快速排序算法只需消耗确定数量的空间（即S(1)，常数级空间）。
这个性质的意义，在于在内存空间受到限制的系统（例如MCU）中，快速排序也能够很好地工作。
(四)时空复杂度
快速排序每次将待排序数组分为两个部分，在理想状况下，每一次都将待排序数组划分成等长两个部分，则需要logn次划分。
而在最坏情况下，即数组已经有序或大致有序的情况下，每次划分只能减少一个元素，快速排序将不幸退化为冒泡排序，所以快速排序时间复杂度下界为O(nlogn)，最坏情况为O(n^2)。在实际应用中，快速排序的平均时间复杂度为O(nlogn)。
快速排序在对序列的操作过程中只需花费常数级的空间。空间复杂度S(1)。
但需要注意递归栈上需要花费最少logn最多n的空间。
(五)随机化算法
快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下，每次划分将得到最坏的结果。一种比较常见的优化方法是随机化算法，即随机选取一个元素作为主元。这种情况下虽然最坏情况仍然是O(n^2)，但最坏情况不再依赖于输入数据，而是由于随机函数取值不佳。实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。一位前辈做出了一个精辟的总结：“随机化快速排序可以满足一个人一辈子的人品需求。” 随机化快速排序的唯一缺点在于，一旦输入数据中有很多的相同数据，随机化的效果将直接减弱。对于极限情况，即对于n个相同的数排序，随机化快速排序的时间复杂度将毫无疑问的降低到O(n^2)。
(六)减少递归栈使用的优化
快速排序的实现需要消耗递归栈的空间，而大多数情况下都会通过使用系统递归栈来完成递归求解。在元素数量较大时，对系统栈的频繁存取会影响到排序的效率。
一种常见的办法是设置一个阈值，在每次递归求解中，如果元素总数不足这个阈值，则放弃快速排序，调用一个简单的排序过程完成该子序列的排序。这样的方法减少了对系统递归栈的频繁存取，节省了时间的消费。
一般的经验表明，阈值取一个较小的值，排序算法采用选择、插入等紧凑、简洁的排序。一个可以参考的具体方案：阈值T=10，排序算法用选择排序。
阈值不要太大，否则省下的存取系统栈的时间，将会被简单排序算法较多的时间花费所抵消。
另一个可以参考的方法，是自行建栈模拟递归过程。但实际经验表明，收效明显不如设置阈值。
(七)C例程
以下是C语言权威《The C Programming Language》中的例程，在这个例程中，对于数组v的left到right号元素以递增顺序排序。
//Qsort.c by Tydus.
#include <stdio.h>
intarr[] = {14,10,11,5,6,15,0,15,16,14,0,8,17,15,7,19,17,1,18,7};
/* swap函数：交换v[k]与v[j]的值 */
inline void swap(int v[], int k, int j)
{
int temp;
temp = v[k];
v[k] = v[j];
v[j] = temp;
}
voidqsort(int v[], int left, int right)
{
int j, last;
if (left >= right) /* 若数组包含的元素个数少于两个 */
return; /* 则不执行任何操作 */
swap(v, left, (left + right)/2); /* 将划分子集的元素移动到V[0] */
last=left; /* 用last记录中比关键字小间的最右位置*/
for (j = left+1; j <= right; j++) /* 划分子集 */
{
if (v[j] < v[left])
{
swap(v, last++, j);
}
}
/*小小。。。。关键字大大大大*/
qsort(v, left, last-1);
qsort(v, last+1, right);
}
void main()
{
int j;
qsort(arr, 0, 19);
for(j=0; j<=19; j++)
{
printf("%d ", arr[j]);
}
printf("\n");
}
(八)消除递归的快速排序
传统的快速排序是递归的，这就会受到递归栈深度的限制。比如在一台普通的PC上，当待排序元素达到10^6以上时，传统的递归快排会导致栈溢出异常，或者一个莫名其妙的错误结果。所以，对于巨大的数据规模，将快速排序消除递归是十分必要的。而消除递归，又将带来巨大的性能提升，把系统级的消耗降到最低。
消除递归的方法，就是模拟栈操作。但是从代码可以看出，这种模拟的消耗几乎可以忽略不计。因此消除递归的快排的效率是有保障的。
（虽然下面的代码没有使用随机化，但经过测试，它是目前所有快排编写方法中，效率最高，速度最快的！） ////////////////////////////////////////////////////////////////////////////////
#define MAXARRAY 10000
#define PUSH(A,B) {sl[sp]=A;sr[sp]=B;sp++;}
#define POP(A,B) {sp--;A=sl[sp];B=sr[sp];}
void quicksort(int a[],intl,int r){
staticintsl[MAXARRAY], sr[MAXARRAY], sp;
inti,j,p,t;
sp=0;
PUSH(l,r);
while(sp){
POP(l,r);
i=l;j=r;p=a[(i+j)/2];
while(i<=j){
while(a[i]<p)i++;
while(a[j]>p)j--;
if(i<=j){
t=a[i];a[i]=a[j];a[j]=t;
i++;j--;
}
}
if(l<j)PUSH(l,j);
if(i<r)PUSH(i,r);
}
}
//////////////////////////////////////////////////////////////////////////////////
(十二)C语言随机化快排模块化代码
#include "stdio.h"
#include "stdlib.h"
#include "time.h"
Location(int *a,intlow,int high)
{
intkey,temp,x;
srand((unsigned)time(0));
x=rand()%(high-low+1)+low;
key=a[x];
while(low<high)
{
while(x<high&&key<=a[high])high--;
temp=a[high];
a[high]=key;
a[x]=temp;
x=high;
while(low<x&&key>=a[low])low++;
temp=a[low];
a[low]=key;
a[x]=temp;
x=low;
}
return low;
}
Qsort(int *a,intlow,int high)
{
intlocat,i;
if(low>=high)return 0;
locat=Location(a,low,high);
Qsort(a,low,locat-1);
Qsort(a,locat+1,high);
}
(十三)快速排序的JAVA实现
importjava.util.Arrays;
public class QuickSort {
public static void quickSort(int[] array) {
quickSort(array, 0, array.length - 1);
}
private static void quickSort(int[] array, int low, int high) { if (low < high) {
int p = partition(array, low, high);
quickSort(array, low, p - 1);
quickSort(array, p + 1, high);
}
}
private static int partition(int[] array, int low, int high) { int s = array[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (array[j] < s) {
i++;
swap(array, i, j);
}
}
swap(array, ++i, high);
return i;
}
private static void swap(int[] array, int i, int j) { int temp;
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
/**
* @paramargs
*/ public static void main(String[] args) { int[] arr ={12,3,5,4,78,67,1,33,1,1,1}; quickSort(arr); System.out.println(Arrays.toString(arr)); } }
第二篇：C语言基本排序算法
（1）“冒泡法”
冒泡法大家都较熟悉。其原理为从a[0]开始，依次将其和后面的元素比较,若a[0]>a[i]，则交换它们，一直比较到a[n]。同理对a[1],a[2],...a[n-1]处理，即完成排序。下面列出其代码：
void bubble(int *a,int n) /*定义两个参数：数组首地址与数组大小*/
{
int i,j,temp;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++) /*注意循环的上下限*/
if(a[i]>a[j]) {
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
C语言数组排序小结（for beginner)
很多朋友是以谭浩强老师编的《c语言教程》作为学习C语言的入门教程的。书中涉及排序问题一般都以“冒泡法”和“选择法”实现。为了扩大视野，增加学习编程的兴趣，我参阅了有关书籍，整理了几种排序法，写出来同大家共勉。（高手们不要笑，这篇文章是写给出学者的，而且我自己也是只菜鸟，虽然内容陈旧，但值得初学者一看）。
让我们先定义一个整型数组a[n],下面用五种方法对其从小到大排序。
（1）“冒泡法”
冒泡法大家都较熟悉。其原理为从a[0]开始，依次将其和后面的元素比较,若a[0]>a[i]，则交换它们，一直比较到a[n]。同理对a[1],a[2],...a[n-1]处理，即完成排序。下面列出其代码：
void bubble(int *a,int n) /*定义两个参数：数组首地址与数组大小*/
{
int i,j,temp;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++) /*注意循环的上下限*/
if(a[i]>a[j]) {
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
冒泡法原理简单，但其缺点是交换次数多，效率低。
下面介绍一种源自冒泡法但更有效率的方法“选择法”。
（2）“选择法”
选择法循环过程与冒泡法一致，它还定义了记号k=i,然后依次把a[k]同后面元素比较，若a[k]>a[j],则使k=j.最后看看k=i是否还成立，不成立则交换a[k],a[i],这样就比冒泡法省下许
多无用的交换，提高了效率。
void choise(int *a,int n)
{
int i,j,k,temp;
for(i=0;i<n-1;i++) {
k=i; /*给记号赋值*/
for(j=i+1;j<n;j++)
if(a[k]>a[j]) k=j; /*是k总是指向最小元素*/
if(i!=k) { /*当k!=i是才交换，否则a[i]即为最小*/
temp=a[i];
a[i]=a[k];
a[k]=temp;
}
}
}
选择法比冒泡法效率更高，但说到高效率，非“快速法”莫属，现在就让我们来了解它。
（3）“快速法”
快速法定义了三个参数，（数组首地址*a,要排序数组起始元素下标i,要排序数组结束元素下标j). 它首先选一个数组元素（一般为a[(i+j)/2],即中间元素）作为参照，把比它小的元素放到它的左边，比它大的放在右边。然后运用递归，在将它左，右两个子数组排序，最后完成整个数组的排序。下面分析其代码：
void quick(int *a,int i,int j)
{
int m,n,temp;
int k;
m=i;
n=j;
k=a[(i+j)/2]; /*选取的参照*/
do {
while(a[m]<k&&m<j) m++; /* 从左到右找比k大的元素*/
while(a[n]>k&&n>i) n--; /* 从右到左找比k小的元素*/
if(m<=n) { /*若找到且满足条件，则交换*/
temp=a[m];
a[m]=a[n];
a[n]=temp;
m++;
n--;
}
}while(m<=n);
if(m<j) quick(a,m,j); /*运用递归*/
if(n>i) quick(a,i,n);
}
（4）“插入法”
插入法是一种比较直观的排序方法。它首先把数组头两个元素排好序，再依次把后面的元素插入适当的位置。把数组元素插完也就完成了排序。
void insert(int *a,int n)
{
int i,j,temp;
for(i=1;i<n;i++) {
temp=a[i]; /*temp为要插入的元素*/
j=i-1;
while(j>=0&&temp<a[j]) { /*从a[i-1]开始找比a[i]小的数，同时把数组元素向后移*/ a[j+1]=a[j];
j--;
}
a[j+1]=temp; /*插入*/
}
}
（5）“shell法”
shell法是一个叫 shell 的美国人与19xx年发明的。它首先把相距k(k>=1)的那几个元素排好序，再缩小k值（一般取其一半），再排序，直到k=1时完成排序。下面让我们来分析其代码：
void shell(int *a,int n)
{
int i,j,k,x;
k=n/2; /*间距值*/
while(k>=1) {
for(i=k;i<n;i++) {
x=a[i];
j=i-k;
while(j>=0&&x<a[j]) {
a[j+k]=a[j];
j-=k;
}
a[j+k]=x;
}
k/=2; /*缩小间距值*/
}
}
上面我们已经对几种排序法作了介绍，现在让我们写个主函数检验一下。
#include<stdio.h>
/*别偷懒，下面的"..."代表函数体，自己加上去哦！*/
void bubble(int *a,int n)
{
...
}
void choise(int *a,int n)
{
...
}
void quick(int *a,int i,int j)
{
...
}
void insert(int *a,int n)
{
...
}
void shell(int *a,int n)
{
...
}
/*为了打印方便，我们写一个print吧。*/
void print(int *a,int n)
{
int i;
for(i=0;i<n;i++)
printf("%5d",a[i]);
printf("\n");
}
main()
{ /*为了公平，我们给每个函数定义一个相同数组*/
int a1[]={13,0,5,8,1,7,21,50,9,2};
int a2[]={13,0,5,8,1,7,21,50,9,2};
int a3[]={13,0,5,8,1,7,21,50,9,2};
int a4[]={13,0,5,8,1,7,21,50,9,2};
int a5[]={13,0,5,8,1,7,21,50,9,2};
printf("the original list:");
print(a1,10);
printf("according to bubble:"); bubble(a1,10);
print(a1,10);
printf("according to choise:"); choise(a2,10);
print(a2,10);
printf("according to quick:"); quick(a3,0,9);
print(a3,10);
printf("according to insert:"); insert(a4,10);
print(a4,10);
printf("according to shell:"); shell(a5,10);
print(a5,10);
}