文字描述
快速排序是对起泡排序的一种改进。它的基本思想是，通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
一趟快速排序描述：假设待排序的序列为{L.r[s], L.r[s+1], … , L.r[t]}，首先任意选取一个记录(通常选第一个记录L.r[s])作为枢轴(pivot), 然后按下述原则重新排列其余记录：将所有关键字较它小的记录都安置在它的位置之前，将所有关键字较它大的记录都安置在它的位置之后。由此以该“枢轴”记录最后所落得位置i作分界线，将序列{L.r[s], L.r[s+1], … , L.r[t]}分割成两个子序列{L.r[s], L.r[s+1], …, L.r[i-1]}和{L.r[i+1], L.r[i+2], …, L.r[t]}。至此，完成一趟快速排序。
示意图
算法分析
快速排序的平均时间为knlnn, 其中n为记录个数，k为某个常数。经验证明，在所有同数量级(nlogn)的排序方法中，其平均时间性能最好。但是，若初始记录序列按关键字有序或基本有序时，快速排序将蜕化为起泡排序，其时间复杂度为n*n.
辅助空间为1，但是需要一个栈空间来实现递归。若每趟排序都将记录序列均匀的分割成长度相接近的两个子序列，则栈的最大深度为[log2n]+1；若每趟排序之后，枢轴位置都在最边上，则栈的最大深度为n。
是不稳定的排序方法
代码实现
#include <stdio.h>
#include <stdlib.h> #define DEBUG #define EQ(a, b) ((a) == (b))
#define LT(a, b) ((a) < (b))
#define LQ(a, b) ((a) <= (b)) #define MAXSIZE 20
typedef int KeyType;
typedef char InfoType;
typedef struct{
KeyType key;
InfoType otherinfo;
}RedType; typedef struct{
RedType r[MAXSIZE+];
int length;
}SqList; void PrintList(SqList L){
int i = ;
printf("下标值：");
for(i=; i<=L.length; i++){
printf("[%d] ", i);
}
printf("\n关键字：");
for(i=; i<=L.length; i++){
printf(" %-3d", L.r[i].key);
}
printf("\n其他值：");
for(i=; i<=L.length; i++){
printf(" %-3c", L.r[i].otherinfo);
}
printf("\n\n");
return ;
} /*
*交换顺序表L中子表L.r[low,...,high]的纪录，枢轴记录到位，
*并返回其所在位置，此时在它之前(后)均不大于(小于)它
*/
int Partition(SqList *L, int low, int high)
{
//用字表的第一个记录作枢轴纪录
L->r[] = L->r[low];
//pivotkey表示枢轴记录的关键字值
KeyType pivotkey = L->r[low].key; //从表的两端交替向中间扫描
while(low<high){
//将比枢轴记录小的记录移到低端
while(low<high && L->r[high].key>=pivotkey) --high;
L->r[low] = L->r[high]; //将比枢轴记录大的记录移到高端
while(low<high && L->r[low].key<=pivotkey) ++low;
L->r[high] = L->r[low];
}
//枢轴记录到位
L->r[low] = L->r[];
//返回枢轴位置
return low;
} /*
* 对顺序表L中子表L.r[low,...,high]作快速排序
*/
void QSort(SqList *L, int low, int high)
{ KeyType pivotkey;
if(low<high){
//将L.r[low,...,high]一分为二，低(高)于pivotkey的均不大于(小于)它
pivotkey = Partition(L, low, high);
#ifdef DEBUG
printf("一趟快速排序后(low=%d, high=%d), pivotkey=%d\n",low, high, pivotkey);
PrintList(*L);
#endif
//对低字表递归排序，pivotkey是轴枢位置
QSort(L, low, pivotkey-);
//对高子表递归排序
QSort(L, pivotkey+, high);
}
} /*对顺序表L作快速排序*/
void QuickSort(SqList *L)
{
printf("对顺序表L作快速排序:\n\n");
QSort(L, , L->length);
} int main(int argc, char *argv[])
{
if(argc < ){
return -;
}
SqList L;
int i = ;
for(i=; i<argc; i++){
if(i>MAXSIZE)
break;
L.r[i].key = atoi(argv[i]);
L.r[i].otherinfo = 'a'+i-;
}
L.length = (i-);
L.r[].key = ;
L.r[].otherinfo = '';
printf("输入数据:\n");
PrintList(L);
//对顺序表L进行快速排序
QuickSort(&L); return ;
}
快速排序
运行