快速排序（Quick Sort）的基本思想是通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对着两部分记录继续进行排序，以达到整个序列有序，具体步骤为
- 设立枢轴，将比枢轴小的记录移到低端，比枢轴大的记录移到高端，直到low=high停止
- 分别对枢轴低高端部分再次快速排序（即重复第1步）
- 重复第1、2步，直到low=high停止
C语言实现（编译器Dev-c++5.4.0，源代码后缀.cpp）
原创文章，转载请注明来自钢铁侠Mac博客http://www.cnblogs.com/gangtiexia
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 6
#define OK 1
#define ERROR 0 typedef int Status;
typedef int KeyType;
typedef char InfoType;//要malloc() typedef struct{
KeyType score;
InfoType name[];
}RedType;//记录类型 typedef struct{
RedType r[MAXSIZE+];
int length;
}SqList;
/*
Name: 初始化
Copyright:
Author: leo
Date: 10-12-15 16:54
Description: 初始化顺序表
*/ Status initSqList(SqList &l){
l.length=MAXSIZE;
printf("%d",l.length);
for(int i=;i<=l.length;i++){
printf("请输入第%d个同学的名字和分数",i);
gets(l.r[i].name);
scanf("%d",&(l.r[i].score));
getchar();
printf("\n");
} return OK;
}
/*
Name: 部分排序
Copyright: http://www.cnblogs.com/gangtiexia
Author: 钢铁侠
Date: 10-12-15 17:00
Description: 反复按照枢轴进行快速排序：将比枢轴大的放在一边，比枢轴小的放在另一边
*/ int partition(SqList &l,int low,int high){
l.r[]=l.r[low];//枢轴
while(low<high){
while(low<high&&l.r[high].score>l.r[].score) high--;
l.r[low]=l.r[high];
while(low<high&&l.r[low].score<l.r[].score) {
printf("\nhigh为%d\n",high);
low++;}
l.r[high]=l.r[low];
}
l.r[low]=l.r[];
return low;
} /*
Name: 启动递归快速排序
Copyright: http://www.cnblogs.com/gangtiexia
Author: 钢铁侠
Date: 11-12-15 14:37
Description: 启动递归快速排序，并进行第一个大部分（所有记录）的快速排序
*/ Status QuickSort(SqList &l,int low,int high){
int pivotloc;
if(low<high){
pivotloc=partition(l,low,high);
QuickSort(l,low,pivotloc-);
QuickSort(l,pivotloc+,high);
}
return OK;
} Status Traverse(SqList &l){
for(int i=;i<=MAXSIZE;i++)
{
printf("%s的分数为%d \n",l.r[i].name,l.r[i].score);
}
} int main(){ SqList L;
initSqList(L);
printf("L.length为%d",L.length);
QuickSort(L,,L.length);
Traverse(L);
return ;
}