交换排序的基本思想是：两两比较待排序记录的关键字，一旦发现两个记录不满足次序不满足次序要求时进行交换，直到整个序列全部满足要求为止。接下来要介绍的快速排序属于交换排序的一种。
【算法步骤】
快速排序的具体步骤如下：
（1）选择待排序表中的第一个记录作为枢轴，将枢轴记录暂存在r[0]的位置上。附设两个指针low和high,初始时分别指向表的上界和下界（第一趟时，low=1;high=L.length）。
（2）从表的最右侧位置依次向左搜索，找到第一个关键字小于枢轴的关键字pivotkey的记录时，将其移到low处。具体操作是：当low<high时，若high所指记录的关键字大于等于pivotkey,则向左移动指针high；否则将high所指记录与枢轴记录交换。
（3）然后再从表的最左侧位置，依次向右搜索找到第一个关键字大于pivotkey的记录和枢轴记录交换。具体操作是：当low<high时，若low所指记录的关键字小于等于pivotkey，则向右移动指针low;否则将low所指记录与枢轴记录交换。
（4）重复步骤（2）和（3），直至low和high相等为止。此时low或high的位置即为枢轴在此趟排序中的最终位置，原表被分成两个子表。
【代码】
//快排算法
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 20//顺序表的最大长度
typedef struct {
int key;//关键字项
//可添加其他数据项
}RedType;//数据类型
typedef struct{
RedType r[MAXSIZE+1];//r[0]设置为监视哨
int length;//顺序表的长度
}SqList;//顺序表类型
int partition(SqList &L,int low,int high)
{//对顺序表L中的子表r[low...high]进行一趟排序，返回枢轴位置
int pivotkey;//设置枢轴
pivotkey=L.r[low].key ;//将low处的关键字保存在枢轴中
L.r[0]=L.r[low] ;//用子表的第一个记录做枢轴记录
while(low<high)
{
while(low<high&&L.r[high].key>=pivotkey) high--;
//当子表的最后一个关键字大于枢轴记录的关键字时，high向前移动一个位置，继续和枢轴记录的关键字进行比较
L.r[low]=L.r[high];//当high所指向的关键字小于pivotkey时，将high处的关键字放到low处
while(low<high&&L.r[low].key<=pivotkey) low++;
L.r[high]=L.r[low];
}
L.r[low]=L.r[0];
return low;
}
void Qsort(SqList &L,int low,int high)
{
if(low<high)
{
int pivotloc=partition(L,low,high);//将枢轴位置保存到pivotloc中
Qsort(L,low,pivotloc-1);//对左子表进行递归排序
Qsort(L,pivotloc+1,high);//对右子表进行递归排序
}
}
void QuickSort(SqList &L)
{
//对顺序表L做快速排序
Qsort(L,1,L.length) ;
}
int main()
{
SqList L;
printf("输入待排数据的个数为：\n");
scanf("%d",&L.length);
printf("请输入数据：（用空格隔开）\n");
for(int i=1;i<=L.length ;i++)
{
scanf("%d",&L.r[i].key);
}
QuickSort(L) ;
printf("快排算法排序的结果为：\n");
for(int i=1;i<=L.length ;i++)
{
printf("%d ",L.r[i].key);
}
printf("\n");
}【运行结果展示】
?【算法分析】
（1）时间复杂度：平均情况下是O（nlog2^n）
（2）空间复杂度：最好情况是O（log2^n）,最坏情况是O(n).
【算法特点】
（1）记录非顺次的移动导致排序方法是不稳定的。
（2）排序过程中需要定位表是下界和上界，所以适合用于顺序结构，很难用于链式结构。
（3）当n值较大时，在平均情况下快速排序是所有内部排序中速度最快的一种，所以其适合初始记录无序且n值较大的情况。