ad.cpp

快速排序算法的c实现

#include <stdafx.h>
#include <windows.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 50000 //排序表的最大容量
typedef struct //定义排序表的结构
{int elemword[MAXSIZE]; //数据元素关键字
int length; //表中当前元素的个数
}SqList;
void InitialSqList(SqList&); //初始化排序表
void InitialSqLists(SqList&);//初始化排序表
void QuickSort(SqList&); //快速排序
void QSort(SqList&,int,int); //子序列快速排序
int Partition(SqList&,int,int); //一趟快速排序
void PrintSqList(SqList); //显示表中的所有元素
void main()
{
//-------------------------主程序说明-------------------------------
printf("启动演示程序请按t,启动测试程序请按其它键。\n");
//-----------------------------------------------------------------
char op;
scanf(" %c",&op);
if(op=='t')
{
//-------------------------演示程序说明-------------------------------
printf("本程序将演示快速排序的操作。\n");
//------------------------------------------------------------
SqList L; //声明表L
char j='y';
while(j!='n'&&j!='N')
{
InitialSqList(L); //待排序列初始化
QuickSort(L); //快速排序
PrintSqList(L); //显示排序结果
printf("继续进行下一次排序吗?(Y/N)");
scanf(" %c",&j);
}
}
else
{
SqList L; //声明表L
char j='y'; 
while(j!='n'&&j!='N')
{
InitialSqLists(L); //待排序列初始化
DWORD dwStartTime, dwUsedTime;
dwStartTime = ::GetTickCount();
long clock1;
long clock2;
clock1=clock();
QuickSort(L); //快速排序
clock2=clock();
long difftime=clock2-clock1;
PrintSqList(L); //显示排序结果
dwUsedTime = ::GetTickCount() - dwStartTime;
printf("%d",L.length);
printf("个随机数进行了快速排序!\n");
printf("所花总时间为");
printf("%d",dwUsedTime);//显示所需时间
printf("ms");
printf("\n");
printf("排序所花时间为");
printf("%d",difftime);
printf("ms");
printf("\n");
printf("继续进行下一次测试吗?(Y/N)");
scanf(" %c",&j);
}
printf("程序运行结束!\n按任意键关闭窗口!\n");
getchar();getchar();
}
}
void InitialSqList(SqList &L)
{//演示表初始化
int i;
printf("请输入待排序的记录的个数:");
scanf("%d",&L.length);
printf("请输入待排序的记录的关键字(整型数):\n");
for(i=1;i<=L.length;i++)
scanf("%d",&L.elemword[i]);
}
void InitialSqLists(SqList &L)
{//测试表初始化
int i;
printf("请输入你需要测试的数组的长度(小于50000)。\n");
scanf("%d",&L.length);
for(i=1;i<=L.length;i++)
L.elemword[i]=rand();
}
void QuickSort(SqList &L)
{//对顺序表L做快速排序。
QSort(L,1,L.length);
}
void QSort(SqList &L,int low,int high)
{//对顺序表中的子序列L.r[low..high]作快速排序
int pivotloc;
if(low<high) //长度大于1
{
pivotloc=Partition(L,low,high); //将表分成两个部分
QSort(L,low,pivotloc-1); //对低子表递归排序,pivotloc是标准位置
QSort(L,pivotloc+1,high); //对高子表递归排序
}
}
int Partition(SqList &L,int low,int high)
{//交换顺序表L中子表r[low..high]的记录，标准记录到位，并返回其所在位置，此时
//在它之前(后)的记录均不大(小)于它
int pivotkey;
pivotkey=L.elemword[low]; //用子表的第一个记录作标准记录
while(low<high) //交替扫描
{
while(low<high&&L.elemword[high]>=pivotkey)
--high;
L.elemword[low]=L.elemword[high];//将比标准记录小的记录移到低端
while(low<high&&L.elemword[low]<=pivotkey)
++low;
L.elemword[high]=L.elemword[low]; //将比标准记录大的记录移到高端
}
L.elemword[low]=pivotkey; //标准记录到位
return low; //返回标准记录
}
void PrintSqList(SqList L)
{//显示表中所有元素
int i;
printf("已排好序的序列如下：\n");
for(i=1;i<=L.length;i++)
{printf("%d",L.elemword[i]);
printf("\n");}
}