//
// distracb:
// 幾種排序方法的實作
#include < stdio.h >
#include < time.h >
#include < stdlib.h >
#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;
}
// 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;
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");
}