1.背景：
快速排序（Quicksort）是对冒泡排序的一种改进。由C.
A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
同其他排序方法相比，快速排序是目前被认为是最好的一种内部排序方法，但快排算法比较多，而且不同快排算法在处理不同类型序列时，其性能也会有较大差异，因此，笔者将通过实例就各种快排算法性能进行比较，并从中找出性能较好的算法,从而让快速排序真正地"快起来"（当然也可能有更好地算法）。
2. 快速排序的C实现代码：
/*****************RedType.h*****************/
#ifndef RED_TYPE
#define RED_TYPE
#include <stdio.h>
typedef int KeyType;//定义关键字类型为整型
typedef int infoType;//定义定义其他数据项的类型为整型
typedef struct RedType
{//记录的类型
KeyType key;//关键字
infoType otherinfo;//其他数据项
}RedType;
//对两个数值型关键字的比较约定为如下的宏定义。
#define EQ(a,b) ((a) == (b))
#define LT(a,b) ((a) < (b))
#define LE(a,b) ((a) <= (b))
//基本操作函数
void InputFromFile(FILE *f,RedType &c);
#endif
/*****************RedType.cpp*******************/
#include "RedType.h"
void InputFromFile(FILE *f,RedType &c)
{//从文件输入记录的函数
fscanf(f,"%d%d",&c.key,&c.otherinfo);
}
/*****************Sq_QuitSort.h*****************/
#ifndef SQ_QUITSORT_H
#define SQ_QUITSORT_H
#include "RedType.h"
#define MAX_SIZE 20 //一个用作示例的小顺序表的最大长度
typedef struct SqList
{//顺序表类型
RedType r[MAX_SIZE];//r[0]闲置或用作哨兵单元
int length;//顺序表长度
}SqList;
//函数声明
void PrintL(SqList &L);
void PrintL(SqList &L);
int Parition1(SqList &L,int low,int high);
int Parition2(SqList &L,int low,int high);
int Parition3(SqList &L,int low,int high);
int Parition4(SqList &L,int low,int high);
void Qsort(SqList &L,int low ,int high);
void QuikSort(SqList &L);
#endif
/*****************Sq_QuitSort.cpp*****************/
#include "Sq_QuitSort.h"
#include <stdio.h>
typedef int Status;//状态类型
#define TRUE 1
#define FALSE 0
void PrintL(SqList &L)
{//输出顺序表L
int i;
for (i = 1; i <= L.length; ++i)
{
printf("(%d,%d) ",L.r[i].key,L.r[i].otherinfo);
}
printf("\n");
}
int Parition1(SqList &L,int low,int high)
{//交换顺序表L中子表L.r[low...high]的记录，使枢轴记录到位
//函数返回交换后枢轴的位置，其前的记录小于枢轴关键字，其后则大于
KeyType pivotkey;//枢轴关键字
pivotkey = L.r[low].key;//用子表的第一个关键字作枢轴的关键字
while (low < high)
{//从表的两端交替地向中间扫描
while (low < high && L.r[high].key >= pivotkey)
{//高端关键字大于等于枢轴关键字
--high;//高端向低移，继续比较
}
L.r[0] = L.r[low];//将比枢轴小的关键词记录交换到低端，枢轴到高端
L.r[low] = L.r[high];
L.r[high] = L.r[0];
while (low < high && L.r[low].key <= pivotkey)
{//低端关键词小于等于枢轴关键字
++low;//低端向高移，继续比较
}
L.r[0] = L.r[low];//将比枢轴大的关键词记录交换到高端，枢轴到低端
L.r[low] = L.r[high];
L.r[high] = L.r[0];
}
return low;//返回枢轴位置
}
int Parition2(SqList &L,int low,int high)
{//【改进算法1】交换顺序表L中子表L.r[low...high]的记录，使枢轴记录到位
//函数返回交换后枢轴的位置，其前的记录小于枢轴关键字，其后则大于
KeyType pivotkey;//枢轴关键字
pivotkey = L.r[low].key;//用子表的第一个关键字作枢轴的关键字
L.r[0] = L.r[low];//将枢轴记录保存到[0]，改进处
while (low < high)
{//从表的两端交替地向中间扫描
while (low < high && L.r[high].key >= pivotkey)
{//高端关键字大于等于枢轴关键字
--high;//高端向低移，继续比较
}
L.r[low] = L.r[high];//将比枢轴关键字小的记录移动到低端，枢轴在[0]处不动，改进处
while (low < high && L.r[low].key <= pivotkey)
{//低端关键词小于等于枢轴关键字
++low;//低端向高移，继续比较
}
L.r[high] = L.r[low];//将比枢轴关键字大的记录移动到高端，枢轴在[0]处不动，改进处
}
L.r[low] = L.r[0];//将枢轴记录移动到位，改进处
return low;//返回枢轴位置
}
void SwapMid(SqList &L,int low,int high)
{//将顺序表L中记录L.r[low],L.r[(low + high)/2],L.r[high]的关键字为中值的记录和第一个记录L.r[low]互换
int i,j,mid,m = (low + high)/2;
SqList t;//存储以上三个记录的临时顺序表，用来对三个记录排序以便找出中值
t.length = 3;
t.r[1] = L.r[low];
t.r[2] = L.r[m];
t.r[3] = L.r[high];
Status change = TRUE;//调整的标志,初值为TRUE
for (i = t.length - 1; i >= 1 && change; --i)
{
change = FALSE;//本次循环未调整的标志
for (j = 1; j <= t.length - 1; ++j)
{
if (LT(t.r[j + 1].key,t.r[j].key))//前面记录的关键字大于后面记录的关键字
{//两记录互换
t.r[0] = t.r[j];
t.r[j] = t.r[j + 1];
t.r[j + 1] = t.r[0];
change = TRUE;//已调整的标志
}
}
}
if (EQ(t.r[2].key,L.r[high].key))
{//中值为L.r[high].key
mid = high;
}
else if (EQ(t.r[2].key,L.r[m].key))
{//中值为L.r[m].key
mid = m;
}
else
{//中值为L.r[low].key
mid = low;
}
if (mid != low)
{//中值记录和第一个记录互换
L.r[0] = L.r[mid];
L.r[mid] = L.r[low];
L.r[low] = L.r[0];
}
}
int Parition3(SqList &L,int low,int high)
{//【改进算法2】交换顺序表L中子表L.r[low...high]的记录，使枢轴记录到位
//函数返回交换后枢轴的位置，其前的记录小于枢轴关键字，其后则大于
KeyType pivotkey;//枢轴关键字
SwapMid(L,low,high);//记录L.r[low],L.r[(low + high)/2],L.r[high]的关键字为中值的记录和L.r[low]互换,改进处
pivotkey = L.r[low].key;//用子表的第一个关键字作枢轴的关键字
L.r[0] = L.r[low];//将枢轴记录保存到[0]
while (low < high)
{//从表的两端交替地向中间扫描
while (low < high && L.r[high].key >= pivotkey)
{//高端关键字大于等于枢轴关键字
--high;//高端向低移，继续比较
}
L.r[low] = L.r[high];//将比枢轴关键字小的记录移动到低端，枢轴在[0]处不动
while (low < high && L.r[low].key <= pivotkey)
{//低端关键词小于等于枢轴关键字
++low;//低端向高移，继续比较
}
L.r[high] = L.r[low];//将比枢轴关键字大的记录移动到高端，枢轴在[0]处不动
}
L.r[low] = L.r[0];//将枢轴记录移动到位
return low;//返回枢轴位置
}
int Parition4(SqList &L,int low,int high)
{//【改进算法2】交换顺序表L中子表L.r[low...high]的记录，使枢轴记录到位
//函数返回交换后枢轴的位置，其前的记录小于枢轴关键字，其后则大于
KeyType pivotkey;//枢轴关键字
RedType t;
SwapMid(L,low,high);//记录L.r[low],L.r[(low + high)/2],L.r[high]的关键字为中值的记录和L.r[low]互换
pivotkey = L.r[low].key;//用子表的第一个关键字作枢轴的关键字
L.r[0] = L.r[low];//将枢轴记录保存到[0]
while (low < high)
{//从表的两端交替地向中间扫描
while (low < high && L.r[high].key >= pivotkey)
{//高端关键字大于等于枢轴关键字
if (LT(L.r[high].key,L.r[high - 1].key))
{//在相邻两记录处于“逆序时”进行互换，改进处
t = L.r[high];
L.r[high] = L.r[high - 1];
L.r[high - 1] = t;
}
--high;
}
L.r[low] = L.r[high];//将比枢轴关键字小的记录移动到低端，枢轴在[0]处不动
while (low < high && L.r[low].key <= pivotkey)
{//低端关键词小于等于枢轴关键字
if (LT(L.r[low + 1].key,L.r[low].key))
{//在相邻两记录处于“逆序时”进行互换，改进处
t = L.r[low];
L.r[low] = L.r[low + 1];
L.r[low + 1] = t;
}
++low;//低端向高移，继续比较
}
L.r[high] = L.r[low];//将比枢轴关键字大的记录移动到高端，枢轴在[0]处不动
}
L.r[low] = L.r[0];//将枢轴记录移动到位
return low;//返回枢轴位置
}
void Qsort(SqList &L,int low ,int high)
{//对顺序表L中的子序列L.r[low..high]作快速排序
static int c = 1;//统计趟数
int pivotloc;//枢轴位置
if (low < high)
{//子序列长度大于1
pivotloc = Parition4(L,low,high);//将L.r[low..high]按关键字一分为二，pivotlc是枢轴位置
printf("第%d趟排序后 顺序表L:\n",c++);
PrintL(L);
Qsort(L,low,pivotloc - 1);//对关键字小于枢轴关键字的低子表递归快速排序
Qsort(L,pivotloc + 1,high);//对关键字大于枢轴关键字的高子表递归快速排序
}
}
void QuikSort(SqList &L)
{//对整个顺序表L作快速排序
Qsort(L,1,L.length);
}
//
/*****************main.cpp*****************/
#include "Sq_QuitSort.h"
#include <stdio.h>
int main(void)
{
FILE *f;
SqList m;
int i;
f=fopen("1.txt","r");
fscanf(f,"%d",&m.length);
for(i=1;i<=m.length;i++)
{
InputFromFile(f,m.r[i]);
}
fclose(f);
printf("排序前：\n");
PrintL(m);
QuikSort(m);
printf("快速排序后：\n");
PrintL(m);
return 0;
}
//排序前按乱序
//(20,1) (17,2) (65,3) (97,4) (76,5) (13,6) (27,7) (49,8) (49,9)
//P1,P2处理乱序
//第1趟排序后 顺序表L:
//(13,6) (17,2) (20,1) (97,4) (76,5) (65,3) (27,7) (49,8) (49,9)
//第2趟排序后 顺序表L:
//(13,6) (17,2) (20,1) (97,4) (76,5) (65,3) (27,7) (49,8) (49,9)
//第3趟排序后 顺序表L:
//(13,6) (17,2) (20,1) (49,9) (76,5) (65,3) (27,7) (49,8) (97,4)
//第4趟排序后 顺序表L:
//(13,6) (17,2) (20,1) (27,7) (49,9) (65,3) (76,5) (49,8) (97,4)
//第5趟排序后 顺序表L:
//(13,6) (17,2) (20,1) (27,7) (49,9) (49,8) (65,3) (76,5) (97,4) #第5趟排好 共5趟
//P3处理乱序
//第1趟排序后 顺序表L:
//(20,1) (17,2) (27,7) (13,6) (49,9) (76,5) (97,4) (49,8) (65,3)
//第2趟排序后 顺序表L:
//(13,6) (17,2) (27,7) (20,1) (49,9) (76,5) (97,4) (49,8) (65,3)
//第3趟排序后 顺序表L:
//(13,6) (17,2) (20,1) (27,7) (49,9) (76,5) (97,4) (49,8) (65,3)
//第4趟排序后 顺序表L:
//(13,6) (17,2) (20,1) (27,7) (49,9) (65,3) (49,8) (76,5) (97,4)
//第5趟排序后 顺序表L:
//(13,6) (17,2) (20,1) (27,7) (49,9) (49,8) (65,3) (76,5) (97,4) #第5趟排好 共5趟
//P4处理乱序
//第1趟排序后 顺序表L:
//(17,2) (20,1) (27,7) (13,6) (49,9) (76,5) (97,4) (49,8) (65,3)
//第2趟排序后 顺序表L:
//(13,6) (17,2) (20,1) (27,7) (49,9) (76,5) (97,4) (49,8) (65,3)
//第3趟排序后 顺序表L:
//(13,6) (17,2) (20,1) (27,7) (49,9) (76,5) (97,4) (49,8) (65,3)
//第4趟排序后 顺序表L:
//(13,6) (17,2) (20,1) (27,7) (49,9) (65,3) (49,8) (76,5) (97,4)
//第5趟排序后 顺序表L:
//(13,6) (17,2) (20,1) (27,7) (49,9) (49,8) (65,3) (76,5) (97,4) #第5趟排好 共5趟
//排序前逆序：
//(9,1) (8,2) (7,3) (6,4) (5,5) (4,6) (3,7) (2,8) (1,9)
//P1 P2处理按逆序：
//第1趟排序后 顺序表L:
//(1,9) (8,2) (7,3) (6,4) (5,5) (4,6) (3,7) (2,8) (9,1)
//第2趟排序后 顺序表L:
//(1,9) (8,2) (7,3) (6,4) (5,5) (4,6) (3,7) (2,8) (9,1)
//第3趟排序后 顺序表L:
//(1,9) (2,8) (7,3) (6,4) (5,5) (4,6) (3,7) (8,2) (9,1)
//第4趟排序后 顺序表L:
//(1,9) (2,8) (7,3) (6,4) (5,5) (4,6) (3,7) (8,2) (9,1)
//第5趟排序后 顺序表L:
//(1,9) (2,8) (3,7) (6,4) (5,5) (4,6) (7,3) (8,2) (9,1)
//第6趟排序后 顺序表L:
//(1,9) (2,8) (3,7) (6,4) (5,5) (4,6) (7,3) (8,2) (9,1)
//第7趟排序后 顺序表L:
//(1,9) (2,8) (3,7) (4,6) (5,5) (6,4) (7,3) (8,2) (9,1) # 第7趟排好
//第8趟排序后 顺序表L:
//(1,9) (2,8) (3,7) (4,6) (5,5) (6,4) (7,3) (8,2) (9,1) 共8趟
//请按任意键继续. . .
//P3处理逆序：
//第1趟排序后 顺序表L:
//(1,9) (2,8) (3,7) (4,6) (5,5) (9,1) (6,4) (7,3) (8,2)
//第2趟排序后 顺序表L:
//(1,9) (2,8) (3,7) (4,6) (5,5) (9,1) (6,4) (7,3) (8,2)
//第3趟排序后 顺序表L:
//(1,9) (2,8) (3,7) (4,6) (5,5) (9,1) (6,4) (7,3) (8,2)
//第4趟排序后 顺序表L:
//(1,9) (2,8) (3,7) (4,6) (5,5) (7,3) (6,4) (8,2) (9,1)
//第5趟排序后 顺序表L:
//(1,9) (2,8) (3,7) (4,6) (5,5) (6,4) (7,3) (8,2) (9,1) # 第5趟排好 共5趟
//请按任意键继续. . .
//P3处理逆序：
//第1趟排序后 顺序表L:
//(1,9) (2,8) (3,7) (4,6) (5,5) (9,1) (6,4) (7,3) (8,2)
//第2趟排序后 顺序表L:
//(1,9) (2,8) (3,7) (4,6) (5,5) (9,1) (6,4) (7,3) (8,2)
//第3趟排序后 顺序表L:
//(1,9) (2,8) (3,7) (4,6) (5,5) (9,1) (6,4) (7,3) (8,2)
//第4趟排序后 顺序表L:
//(1,9) (2,8) (3,7) (4,6) (5,5) (6,4) (7,3) (8,2) (9,1) #第4趟排好 共5趟
//第5趟排序后 顺序表L:
//(1,9) (2,8) (3,7) (4,6) (5,5) (6,4) (7,3) (8,2) (9,1)
//请按任意键继续. . .
//排序前按顺序：
//(1,1) (2,2) (3,3) (4,4) (5,5) (6,6) (7,7) (8,8) (9,9)
//P1 P2处理顺序：
//第1趟排序后 顺序表L:
//(1,1) (2,2) (3,3) (4,4) (5,5) (6,6) (7,7) (8,8) (9,9)
//第2趟排序后 顺序表L:
//(1,1) (2,2) (3,3) (4,4) (5,5) (6,6) (7,7) (8,8) (9,9)
//第3趟排序后 顺序表L:
//(1,1) (2,2) (3,3) (4,4) (5,5) (6,6) (7,7) (8,8) (9,9)
//第4趟排序后 顺序表L:
//(1,1) (2,2) (3,3) (4,4) (5,5) (6,6) (7,7) (8,8) (9,9)
//第5趟排序后 顺序表L:
//(1,1) (2,2) (3,3) (4,4) (5,5) (6,6) (7,7) (8,8) (9,9)
//第6趟排序后 顺序表L:
//(1,1) (2,2) (3,3) (4,4) (5,5) (6,6) (7,7) (8,8) (9,9)
//第7趟排序后 顺序表L:
//(1,1) (2,2) (3,3) (4,4) (5,5) (6,6) (7,7) (8,8) (9,9)
//第8趟排序后 顺序表L:
//(1,1) (2,2) (3,3) (4,4) (5,5) (6,6) (7,7) (8,8) (9,9) 共8趟
//P3处理顺序：
//第1趟排序后 顺序表L:
//(1,1) (2,2) (3,3) (4,4) (5,5) (6,6) (7,7) (8,8) (9,9)
//第2趟排序后 顺序表L:
//(1,1) (2,2) (3,3) (4,4) (5,5) (6,6) (7,7) (8,8) (9,9)
//第3趟排序后 顺序表L:
//(1,1) (2,2) (3,3) (4,4) (5,5) (6,6) (7,7) (8,8) (9,9)
//第4趟排序后 顺序表L:
//(1,1) (2,2) (3,3) (4,4) (5,5) (6,6) (7,7) (8,8) (9,9)
//第5趟排序后 顺序表L:
//(1,1) (2,2) (3,3) (4,4) (5,5) (6,6) (7,7) (8,8) (9,9) 共5趟
//P4处理顺序：
//第1趟排序后 顺序表L:
//(1,1) (2,2) (3,3) (1,1) (5,5) (6,6) (7,7) (8,8) (9,9)
//第2趟排序后 顺序表L:
//(1,1) (1,1) (2,2) (3,3) (5,5) (6,6) (7,7) (8,8) (9,9)
//第3趟排序后 顺序表L:
//(1,1) (1,1) (2,2) (3,3) (5,5) (6,6) (7,7) (8,8) (9,9)
//第4趟排序后 顺序表L:
//(1,1) (1,1) (2,2) (3,3) (5,5) (6,6) (7,7) (8,8) (9,9)
//第5趟排序后 顺序表L:
//(1,1) (1,1) (2,2) (3,3) (5,5) (6,6) (7,7) (8,8) (9,9) 共5趟
//排序性能分析：
//当序列按乱序排列时，P1,P2,P3的平均性能相差不大
//当序列按逆序排列时,平均性能P4 > P3 > P1,P2
//当序列按顺序排列时,平均性能P4 = P3 > P1,P2
//P1,P2处理乱序序列时的性能优于处理顺序和逆序序列时的性能
//综上所述，P4算法平均排序性能最好