實現以下常用的內部排序演算法並進行效能比較：起泡排序、直接插入排序、簡單選擇排序、快速排序、希爾排序、堆排序。
基本要求：
待排序表的表長不少於100；其中的資料要用偽隨機數產生程式產生；至少要用5組不同的輸入資料作比較；比較的指標為有關鍵字參加的比較次數和關鍵字移動次數（關鍵字交換計為3次移動）。
三．原始碼
#include
#include
#include
#define MAXNUM 10000
long cn[MAXNUM],mn[MAXNUM];
typedef struct
{
int key;
}datatype;
void D_InsertSort(datatype R[],long n)//直接排序
{
long i ,j;
for(i=2;i<=n;i++)
{
cn[0]++;
if(R[i].key
{
R[0]=R[i];mn[0]++;
for(j=i-1;R[0].key
R[j+1]=R[j];
R[j+1]=R[0];
mn[0]+=2;
}
}
}
void Select_Sort(datatype R[],long n)//簡單選擇排序
{
long i,j,k;
for(i=1;i
{
k=i;
for(j=i+1;j<=n;j++)
{
cn[1]++;
if(R[j].key
k=j;
} if(i=k)
{
R[0]=R[k];
R[k]=R[i];
R[i]=R[0];
mn[1]+=3;
}
}
}
void Bubble_Sort(datatype R[],long n)//氣泡排序
{
long i,j;
for(i=1;i
{
for(j=1;j<=n-i;j++)
{
cn[2]++;
if(R[j].key
{
R[0]=R[j];
R[j]=R[j+1];
R[j+1]=R[0];
mn[2]+=3;
}
}
}
}
void HeapAdjust(datatype R[], long s, long t)//堆調整
{
datatype rc;
long i,j;
rc=R[s];
i=s;
for(j=2*i;j<=t;j=2*j)
{
cn[3]++;
if(j
j=j+1;
if(rc.key>R[j].key)
break;
R[i]=R[j];
mn[3]++;
i=j;
}
R[i]=rc;
}
void HeapSort(datatype R[], long n)//堆排序
{
long i;
for(i=n/2;i>0;i--)
HeapAdjust(R,i,n);
for(i=n;i>1;i--)
{
R[0]=R[1];
R[1]=R[i];
R[i]=R[0];
mn[3]+=3;
HeapAdjust(R,1,i-1);
}
}
void Merge(datatype R[],datatype R1[], long s, long m, long t)
{
long i ,j ,k;
i=s;j=m+1;k=s;
while(i<=m&&j<=t)
{
cn[4]++;
if(R[i].key
{
R1[k++]=R[i++];
mn[4]++;
}
else
{
R1[k++]=R[j++];
mn[4]++;
}
}
while(i<=m)
{
R1[k++]=R[i++];
mn[4]++;
}
while(j<=t)
{
R1[k++]=R[j++];
mn[4]++;
}
}
void MSort(datatype R[],datatype R1[], long s,long t)
{
long m; if(s==t)
{
R1[s]=R[s];
mn[4]++;
}
else
{
m=(s+t)/2;
MSort(R,R1,s,m);
MSort(R,R1,m+1,t);
Merge(R1,R,s,m,t);
}
}
void MergeSort(datatype R[],datatype R1[],long n)//歸併排序
{
MSort(R,R1,1,n);
}
long Partition(datatype R[], long low, long high)
{
R[0]=R[low];
mn[5]++;
while(low
{
while(low
{
cn[5]++;high--;
}
if(low
{
R[low]=R[high];
low++;
mn[5]++;
}
while(low
{
cn[5]++;
low++;
}
if(low
{
R[high]=R[low];
high--;
mn[5]++;
}
}
R[low]=R[0];
mn[5]++;
return low;
}
void Quick_Sort(datatype R[],long s, long t)//快速排序
{
long i;
if(s
{
i=Partition(R,s,t);
Quick_Sort(R,s,i-1);
Quick_Sort(R,i+1,t);
}
}
void prin(datatype R[], long n)
{
long i;
printf("排序結果為：\n");
for(i=1;i<=n;i++)
{
printf("%d ",R[i]);
}
printf("\n");
}
void suiji()
{
long i,n;
datatype
R[MAXNUM]={0};////定義結構陣列
printf("請輸入你要輸入的d個數\n");
scanf("%d",&n);
if(n>500000)
{
printf("超出範圍重新輸入\n");
scanf("%d ",&n);
}
for(i=1;i<=n;i++)
R[i].key=rand()%100;
printf("排序前的元素順序\n");
for(i=1;i
{
printf("%d ",R[i].key);
}
printf("\n");
D_InsertSort(R,n);//直接排序
Select_Sort(R,n);//簡單選擇排序
Bubble_Sort(R,n);//氣泡排序
HeapSort(R,n); //堆排序
datatype R2[MAXNUM]={0};
MergeSort(R,R2,n);
Quick_Sort(R,0,n);//快速排序
prin(R,n);
}
int main()
{
suiji();
printf(" 比較結果 \n");
printf(" 排序方式 比較次數 移動次數\n");
printf(" 直接 %d %d \n",cn[0],mn[0]);
printf(" 簡單選擇排序 %d %d \n",cn[1],mn[1]);
printf(" 冒泡 %d %d \n",cn[2],mn[2]);
printf(" 堆排序 %d %d \n",cn[3],mn[3]);
printf(" 快速排序 %d %d \n",cn[5],mn[5]);
return 0;
}