#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");}
}