快速排序

快速排序(Quick Sort )是由冒泡排序改进而得的。在冒泡排序过程中，只对相邻的两个记录进行比较，因此每次交换两个相邻记录时只能消除一个逆序。 如果能通过两个(不相邻)记录的一次交换，消除多个逆序，则会大大加快排序的速度。快速排序方法中的一次交换可能消除多个逆序。

课本上的例子：

时间复杂度

最好情况：O(n$lo{g}_2$n)
最坏情况：O($n^2$)
平均情况：O(n$lo{g}_2$n)

空间复杂度

O($lo{g}_2$n)

算法特点：

1）记录非顺次的移动导致排序方法是不稳定的。
2）排序过程中需要定位表的下界和上界，所有适合用于顺序结构，很难用于链式。
3）当n较大时，在平均情况下快速排序是所有内部排序方法中速度最快的一种，所以其适合初始记录无序、n较大时的情况。

完整代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 100  //顺序表最大容量，可以自行加大 

typedef struct 
{
	int key;//关键字项 
	char *otherinfo;//其他数据项 
}ElemType;//记录类型 
typedef struct
{
	ElemType Data[MAXSIZE+1];//静态顺序表的数据域，这里Data[0]为空闲或者为哨兵单元 
	int length;//顺序表的长度 
}SqList;//顺序表 

void InitList(SqList &L)//顺序表的初始化 
{
	L.length = 0;//使顺序表长度归0，便是顺序表的初始化 
}

void CreateList(SqList &L)//顺序表的创建 
{
	printf("请输入："); 
	while(1)//建立一个死循环，循环终止条件是按了enter键 
	{
		L.length++;//顺序表长度加一 
		if(L.length>MAXSIZE)//判断是否超出最大容纳量 
		{
			printf("顺序表已满！\n");
			return ;
		}
		scanf("%d",&L.Data[L.length].key);//顺序表数据的输入 
		if(getchar() == '\n')//循环终止条件 
			break;
	}
}

void InputList(SqList L)//顺序表的输出 
{
	int i;//记录次数 
	if(L.length == 0)//判断顺序表是否为空 ，若为空结束该函数 
	{
		printf("顺序表是空的！\n");
		return ;
	}
	printf("打印为：");
	for(i=1;i<=L.length;i++)//利用循环打印顺序表中的数据 
		printf("%d ",L.Data[i].key);	
}

int Partition(SqList &L,int low,int high)//对顺序表L中的子表Data[low…high]进行一趟排序，返回驱轴位置 
{
	L.Data[0] = L.Data[low];//用子表的第一个记录做驱轴记录  
	while(low < high)//当low==high时终止循环 ，从表的两端交替地向中间扫描 
	{
		while(low<high&&L.Data[0].key<=L.Data[high].key)
			high--;
		L.Data[low] = L.Data[high];//将比驱轴记录小的记录移到低端 
		while(low<high&&L.Data[0].key>=L.Data[low].key)
			low++;
		L.Data[high] = L.Data[low];//将比驱轴记录大的记录移到高端 
	}
	L.Data[low] = L.Data[0];//驱轴记录到位 
	return low;//返回驱轴位置 
}
int pivotloc;//递归函数中不宜定义变量，故定义一个全局变量 
void QSort(SqList &L,int low,int high)//调用前置初值：low=1;high=L.length; 
{//对顺序表L中的字序列L.Data[low…high]做快速排序，递归算法 
	if(low < high)//长度大于1，递归终止条件 
	{
		pivotloc = Partition(L,low,high);//将L.Data[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;
	InitList(L);//初始化顺序表 
	CreateList(L);//创建顺序表 
	QuickSort(L);//快速排序 
	InputList(L);//打印排序后结果 
	return 0;
}

（完）