八种排序方法

//////////////////////////////////////////////////////////////////////////////////////////////
/**//*利用随机函数产生N个随机整数（2000以上），对这些数进行多种方法进行排序。

要求：

至少采用三种方法实现（提示，可采用插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。
并把排序后的结果保存在不同的文件中。

统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。*/
/**/////////////////////////////////////////////////////////////////////////////////////////////////
//distracb:
// 几种排序方法的实现


#include
#include
#include

#define MAXSIZE 100
// const int MAXSIZE = 20 ;

//定义数据结构

typedef int KeyType;
typedef char InfoType;

typedef struct{
KeyType key;
InfoType otherinfo;
}RcdType; //记录类型

typedef struct{
RcdType r[MAXSIZE+1];
int length;
}SqList;

typedef SqList HeapType; //堆采用顺序表存储结构表示

//函数声明部分
//(注意声明部分要加返回类型)
bool LT(KeyType a ,KeyType b); //比较两个关键字大小的函数
void InsertSort(SqList L); //直接插入排序
void BInsertSort(SqList L); //折半插入排序
void BubbleSort(SqList L); //冒泡排序
void QuickSort(SqList L); //快速排序
void ShellSort(SqList L); //希尔排序

/**///////////////////////////////////////////////////////////
bool LT(KeyType a ,KeyType b)
{
if(a <= b) return true;
else return false;
}
/**//*
//直接插入排序
void InsertSort(SqList L)
{
for(int i=2;i<=L.length;i++)
if(LT(L.r[i].key,L.r[i-1].key))
{
L.r[0]=L.r[i]; //复制为哨兵
L.r[i]=L.r[i-1];
for(int j=i-2;LT(L.r[0].key,L.r[j].key);j--)
L.r[j+1]=L.r[j]; //记录后移
L.r[j+1]=L.r[0]; //插入到正确位置
}
printf("after insertsort the recodelist is : ");
for(i=1;i<=L.length;i++)
printf("%d ",L.r[i].key);
}


//折半插入排序
void BInsertSort(SqList L)
{
for(int i=2;i<=L.length;i++)
{
L.r[0]=L.r[i];
L.r[i]=L.r[i-1];
int low=0,high=i-1;
while(low寻找插入位置
{
int m=(low+high)/2;
if(LT(L.r[0].key,L.r[m].key))
high=m-1;
else low=m+1;
}
for(int j=i-1;j>=high+1;j--)
L.r[j+1]=L.r[j]; //记录后移
L.r[high+1]=L.r[0]; //插入记录
}
printf("after Binary insertsort the recodelist is : ");
for(i=1;i<=L.length;i++)
printf("%d ",L.r[i].key);
}


//希尔排序
void ShellInsert(SqList L ,int dk ) //一趟希尔插入排序
{
for(int i=dk+1;i<=L.length;i++)
if(LT(L.r[i].key,L.r[i-dk].key))
{
L.r[0]=L.r[i];
for(int j=i-dk;(j>0) && LT(L.r[0].key,L.r[j].key);j-=dk)
L.r[j+dk]=L.r[j];
L.r[j+dk]=L.r[0];
}
}

int dlta[]={8,4,2,1}; //增量序列dlta[k]=2^(t-k-1) t为排序趟数4
int t=4;
void ShellSort(SqList L ,int dlta[],int t )
{
for(int k=0;kShellInsert( L ,dlta[k] );

printf("after ShellSort the recodelist is : ");
for(int i=1;i<=L.length;i++)
printf("%d ",L.r[i].key);
}


//冒泡排序
void BubbleSort(SqList L)
{
int flag=1;
for(int i=1;i<=L.length && flag!=0;i++)
{
flag=0;
for(int j=1;j<=(L.length-i);j++)
if(LT(L.r[j].key,L.r[j+1].key))
{
RcdType temp = L.r[j];
L.r[j] = L.r[j+1];
L.r[j+1] = temp;
flag=1;
}
}
printf("after BubbleSort the recodelist is : ");
for(i=1;i<=L.length;i++)
printf("%d ",L.r[i].key);
}


//快速排序
int Partition(SqList L,int low ,int high) //一次划分
{
L.r[0] = L.r[low];
KeyType pivotkey = L.r[low].key; //第一个记录作为枢轴记录
while(low{
while((low < high) && LT(pivotkey,L.r[high].key))
--high;
L.r[low] = L.r[high];
while(low++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{
int pivotkey = Partition(L,low,high);
Qsort(L,pivotkey+1 ,high);
Qsort(L,low,pivotkey-1);
}

}

void QuickSort(SqList L)
{
Qsort( L, 1, L.length);
printf("after QuickSort the recodelist is : ");
for(int i=1;i<=L.length;i++)
printf("%d ",L.r[i].key);
}


//简单选择排序
SelectMinKey(SqList,int); //声明

void SelectSort(SqList L)
{
for(int i=1;i{
int j = SelectMinKey(L,i); //在L.r[i....L.length]中选择一个最小的记录
if(i!=j) //交换记录
{
RcdType temp = L.r[j];
L.r[j] = L.r[i];
L.r[i] = temp;
}
}
printf("after SelectSort the recodelist is : ");
for(i=1;i<=L.length;i++)
printf("%d ",L.r[i].key);
}

int SelectMinKey(SqList L,int i) //寻找记录中最小值的位置
{
KeyType k;
int position;
k = L.r[i].key;
for(;i<=L.length;i++)
{
if(LT(L.r[i].key,k))
{
k = L.r[i].key;
position=i;
}
}
return position;
}

//堆排序


void HeapAdjust(HeapType H, int s ,int m) //堆调整函数(筛选)
//已知H.r[s...m]中记录的关键字除H.r[s].key 之外均满足堆的定义，本函数调整H.r[s]的关键字
//使H.r[s....m]成为一个大顶堆（对其中的关键字而言）
{
RcdType rc = H.r[s]; //现在的顶部结点
for(int j=2*s;j<=m;j*=2) //沿key 较大的孩子结点像下筛选
{
if(j为较大记录的下标
if(!LT(rc.key,H.r[j].key)) break; //rc应插入在位置s上
H.r[s]=H.r[j];
s=j;
}
H.r[s]=rc; //插入
}

void HeapSort(HeapType H) //堆排序
{
for(int i=H.length/2; i>0;i--) //把H.r[1...L.length]建成大顶堆
HeapAdjust( H, 1 ,H.length);
for(i=H.length;i>1;i--)
{
RcdType temp = H.r[1]; //将堆顶记录和子序列H.r[1...i]中的最后一个记录交换
H.r[1]=H.r[i];
H.r[i]=temp;
HeapAdjust(H, 1 ,i-1); //重新调整为大顶堆
}
printf("after HeapSort the recodelist is : ");
for(i=1;i<=H.length;i++)
printf("%d ",H.r[i].key);
}

*/
//2-路归并排序
void Merge(RcdType SR[],RcdType TR[],int i,int m,int n) /**//////////////????RcdType &TR[]为什么就提示好多错误？？
//将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]
{
for(int k=i,j=m+1;(i<=m) && (j<=n);++k) //将SR中的记录由小到大的并入到TR
...{
if(LT(SR[i].key,SR[j].key))
TR[k]= SR[i++];
else TR[k]=SR[j++];
}
if(i<=m)
...{
for(;i<=m;i++,k++)
TR[k]=SR[i];
}
if(j<=n)
...{
for(;j<=n;j++,k++)
TR[k]=SR[j];
}
}

void MSort(RcdType SR[],RcdType TR1[],int s,int t)
//将SR[s..t]归并排序为TR1[s..t]
{
RcdType TR2[20]; /**////////////////////////////////////////????????????????????这里应该定义数组多大呢 、？
if(s == t) TR1[s]=SR[s];
else...{
int m=(s+t)/2; //将ＳＲ平分成两部分
MSort(SR,TR2,s,m); //递归地将SR[s..m]归并为有序的TR2[s.m]
MSort(SR,TR2,m+1,t); //递归地将SR[m+1..t]归并为有序的TR2[m+1..t]
Merge(TR2,TR1,s,m,t); //将TR2[s.m] TR2[m+1..t]归并到 TR1[s..m]
}
}

void MerqeSort(SqList L)
{
MSort(L.r,L.r,1,L.length);
printf("after MerqeSort the recodelist is : ");
for(int i=1;i<=L.length;i++)
printf("%d ",L.r[i].key);
}

void menu()
{
printf(" *************************** ");
printf(" 1: Insert Sort ");
printf(" 2: BInsert Sort ");
printf(" 3: Bubble Sort ");
printf(" 4: Quick Sort ");
printf(" 5: Straight Selection Sort ");
printf(" 6: Heap Sort ");
printf(" 7: Merge Sort ");
printf(" 8: Exit ");
printf(" *************************** ");
}

//主函数
void main()
{
SqList L;
srand(10);
for(int i=1;i<=MAXSIZE;i++)
L.r[i].key=rand()+2000;
L.length=MAXSIZE;

menu();
clock_t start, finish;
double duration;
/**//* double duration[8];
int count=0;

start = clock();
InsertSort( L);
finish = clock();
duration[count] = (double)(finish - start) / CLOCKS_PER_SEC;
printf( "InsertSort cost time %f seconds： ", duration[count] );
count++;
system("pause");

start = clock();
BInsertSort( L);
finish = clock();
duration[count] = (double)(finish - start) / CLOCKS_PER_SEC;
printf( "BInsertSort cost time %f seconds： ", duration[count] );
count++;
system("pause");

start = clock();
ShellSort( L ,dlta,4 );
finish = clock();
duration[count]= (double)(finish - start) / CLOCKS_PER_SEC;
printf( "ShellInsert cost time %f seconds： ", duration[count] );
count++;
system("pause");

start = clock();
BubbleSort( L);
finish = clock();
duration[count] = (double)(finish - start) / CLOCKS_PER_SEC;
printf( "BubbleSort cost time %f seconds： ", duration[count] );
count++;
system("pause");

start = clock();
QuickSort( L);
finish = clock();
duration[count] = (double)(finish - start) / CLOCKS_PER_SEC;
printf( "QuickSort cost time %f seconds： ", duration[count] );
count++;
system("pause");

start = clock();
SelectSort(L);
finish = clock();
duration[count] = (double)(finish - start) / CLOCKS_PER_SEC;
printf( "SelectSort cost time %f seconds： ", duration[count] );
count++;
system("pause");

start = clock();
HeapSort( L);
finish = clock();
duration[count] = (double)(finish - start) / CLOCKS_PER_SEC;
printf( "HeapSort cost time %f seconds： ", duration[count] );
count++;
system("pause");
*/
start = clock();
MerqeSort( L);
finish = clock();
// duration[count] = (double)(finish - start) / CLOCKS_PER_SEC;
// printf( "MerqeSort cost time %f seconds： ", duration[count] );
//count++;
duration = (double)(finish - start) / CLOCKS_PER_SEC;
printf( "MerqeSort cost time %f seconds： ", duration );
system("pause");

/**//* printf("compare the cost time here : ");
for(count=0;count<8;count++)
{
printf( "T%d cost time %f seconds： ", count+1,duration[count] );
}
*/
}