C語言是一門計算機高階語言，被許多IT行業的工作者們熟練地運用著。在C語言中，排序的演算法有好幾種，下來我會舉一個例子：C語言各種排序均包含，以及它的word程式設計報告。
工具/原料
熟知C語言的排序概念
對C語言有一定的瞭解
方法/步驟
源程式：（程式結果可以執行出來）
#include "stdio.h"
#include "stdlib.h"
#include "time.h"//計時
#define ERROR 0
#define OK 1
#define OVERFLOW -2
#define MAXSIZE 100000 //使用者自己規定排序的數字的長度
typedef int Status;
typedef struct
{
int *r; // r[0]閒置
int length; //順序表的總長度
}Sqlist;
//構造一個空線性表
Status InitSqlist(Sqlist &L)
{
L.r=(int *)malloc(MAXSIZE*sizeof(int)); //分配儲存空間
if(!L.r)
{
printf("儲存分配失敗！");
exit(0);
} //儲存分配失敗
L.length=0;//初始長度為0
return OK;
}
//輸入隨機數並顯示在介面上
Status ScanfSqlist(int &N,Sqlist &L)
{
int i;
printf("請輸入要排序的元素個數N: ");
scanf("%d",&N);
for(i=1;i<=N;i++)
L.r[i]=rand(); //隨機產生樣本整數
printf("\n\n");
printf(" 隨機產生了%d個隨機數，它們是：\n",N);
for(i=1;i<=N;i++)
{
printf("%7.2d ",L.r[i]);
}
printf("\n");
L.length=N; //儲存線性表的長度
return OK;
}
//輸出排序之後的資料
Status PrintfSqlist(int N,Sqlist L)
{
int i;
printf("資料個數：");//輸出資料個數
printf("%d\n",L.length);
printf("排序後的資料：(從左向右依次增大)\n");//輸出資料
for(i=1;i<=N;i++)
printf("%7.2d ",L.r[i]);
printf("\n");
return OK;
}
//***************************************************************
// 直接插入排序
//***************************************************************
Status InsertSort(Sqlist &L) //參考書P265演算法10.1
{
int i,j;
if(L.length==0)
{
printf("要排序的資料為空！");
return ERROR;
}
for(i=2;i<=L.length;i++)
{
if(L.r[i]
{
L.r[0]=L.r[i]; //複製為監視哨
L.r[i]=L.r[i-1];
for(j=i-2;L.r[0]
{
L.r[j+1]=L.r[j]; //記錄後移
}
L.r[j+1]=L.r[0]; //插入到正確位置
}
}
return OK;
}
//***************************************************************
// 折半插入排序
//***************************************************************
Status BInsertSort(Sqlist &L) //參考書P267演算法10.2
{
int i,j,mid,low,high;
if(L.length==0)
{
printf("要排序的資料為空！");
return ERROR;
}
for(i=2;i<=L.length;i++)
{
L.r[0]=L.r[i]; //將L.r[i]暫存在L.r[0]
low=1;
high=i-1;
while(low<=high) //在r[low..high]中折半查詢有序插入的位置
{
mid=(low+high)/2;
if(L.r[0]
{
high=mid-1;
}
else
{
low=mid+1; //插入點在高半區
}
}//while
for(j=i-1;j>=high+1;j--) //插入點後的資料後移
{
L.r[j+1]=L.r[j];
}
L.r[high+1]=L.r[0]; //將資料插入
}//for
return OK;
}
/********************************************************************************
希爾排序
*********************************************************************************/
//參考書P272演算法10.4及10.5
Status ShellInsert(Sqlist &L,int dk) //希爾插入排序
{
int i,j; //前後位置的增量是dk
for(i=dk+1;i<=L.length;i++) //r[0]只是暫存單元，不是哨兵，
{
if(L.r[i]
{
L.r[0]=L.r[i]; //暫存L.r[0]
for(j=i-dk;j>0 && L.r[0]
{
L.r[j+dk]=L.r[j]; //記錄後移,查詢插入位置
}
L.r[j+dk]=L.r[0]; //插入
}
}
return OK;
}
Status ShellSort(Sqlist &L,int dlta[5],int t) //希爾排序
{
int i;
if(L.length==0)
{
printf("要排序的資料為空！");
return ERROR;
}
for(i=0;i
{
ShellInsert(L,dlta[i]); //一趟增量為dlta[k]的插入排序
}
return OK;
}
//**************************************************************
// 起泡排序
//**************************************************************
Status BubbleSort(Sqlist &L)
{
int i,j,t;
if(L.length==0)
{
printf("要排序的資料為空！");
return ERROR;
}
for(i=1;i<=L.length-1;i++)
{
for(j=1;j<=L.length-i;j++)
{
if(L.r[j]>L.r[j+1]) //前面的資料>後面資料時
{
t=L.r[j+1];
L.r[j+1]=L.r[j];
L.r[j]=t; //將元素交換
}
}
}
return OK;
}
//****************************************************
// 快速排序
//****************************************************
int Partition(Sqlist &L, int low, int high) //交換順序表中子表L.r[low..high]的記錄，使得樞軸記錄到位，並返回其所在位置，此時在它之前（後）的記錄均不大於它
{
int pivotkey; //記錄關鍵字
L.r[0]=L.r[low]; //用子表的第一個紀錄作樞軸紀錄
pivotkey=L.r[low]; //用樞軸紀錄關鍵字
while (low
{
while(low
{
high--;
}
L.r[low]= L.r[high]; //將比樞軸記錄小的記錄移到低端
while(low
{
low++;
}
L.r[high]=L.r[low]; //將比樞軸記錄大的數移到高階
}
L.r[low]=L.r[0]; //樞軸記錄到位
return low;
}//Partition函式
void Qsort (Sqlist &L,int low, int high)
{
int pivotloc;
if (low
{
pivotloc=Partition(L, low ,high);
Qsort(L,low,pivotloc-1); //對低子表遞迴排序，pivotloc是樞軸位置
Qsort(L,pivotloc+1,high); //對高子表遞迴排序
}
}//Qsort函式
Status QuickSort (Sqlist &L)
{
if(L.length==0)
{
printf("要排序的資料為空！");
return ERROR;
}
Qsort(L,1,L.length);
return OK;
}//QuickSort
//**********************************************
// 選擇排序
//**********************************************
Status ChooseSort(Sqlist &L)
{
int i,j,k,t;
if(L.length==0)
{
printf("沒有資料！");
return ERROR;
}
for(i=1;i<=L.length;i++) //排序的趟數
{
k=i;
for(j=i+1;j<=L.length;j++) //比較第i個元素以及其後的資料中最小的
{
if(L.r[j]
k=j;
}
if(i!=j) //將最小資料賦值給L.r[i]
{
t=L.r[i];
L.r[i]=L.r[k];
L.r[k]=t;
}
}
return OK;
}
//****************************************
// 堆排序
//****************************************
Status HeapAdjust(Sqlist &L,int s,int m) //調整L.r[s]的關鍵字,使L.r[s~m]成大頂堆
{
int i;
L.r[0]=L.r[s];
for(i=2*s;i+1<=m;i*=2) //沿資料較大的孩子結點向下篩選
{
if(i
i++;
if(L.r[0]>=L.r[i]) //L.r[0]插入在S位置上
break;
L.r[s]=L.r[i];
s=i;
}
L.r[s]=L.r[0]; //插入新資料
return OK;
}
Status HeapSort(Sqlist &L) //堆排序
{
int i,t;
if(L.length==0)
{
printf("沒有資料！");
return ERROR;
}
for(i=L.length/2;i>0;i--)
HeapAdjust(L,i,L.length);
for(i=L.length;i>1;i--)
{
t=L.r[1]; //將堆頂記錄和當前未經排序的子序列L.r[1..i]中最後一個記錄互換
L.r[1]=L.r[i];
L.r[i]=t;
HeapAdjust(L,1,i-1); //將L.r[1..i-1]重新調整為大頂堆
}
return OK;
}
//**************************************************
// 基數排序
//**************************************************
typedef struct node{
int key;
node *next;
}RecType;
Status RadixSort(Sqlist L)
{
int t,i,j,k,d,n=1,m;
RecType *p,*s,*q,*head[10],*tail[10]; //定義各鏈隊的首尾指標
for(i=1;i<=L.length;i++) //將順序錶轉化為連結串列
{
s=(RecType*)malloc(sizeof(RecType));
s->key=L.r[i];
if(i==1) //當為第一個元素時
{
q=s;
p=s;
t++;
}
else
{
q->next=s; //將連結串列連線起來
q=s;
t++;
}
q->next=NULL;
}
d=1;
while(n>0) //將每個元素分配至各個鏈隊
{
for(j=0;j<10;j++) //初始化各鏈隊首、尾指標
{
head[j] = NULL;
tail[j] = NULL;
}
while(p!=NULL) //對於原連結串列中的每個結點迴圈
{
k=p->key/d;
k=k%10;
if(head[k]==NULL) //進行分配
{
head[k]=p;
tail[k]=p;
}
else
{
tail[k]->next=p;
tail[k]=p;
}
p=p->next; //取下一個待排序的元素
}
p=NULL; //用於收集第一個元素時的判斷
for(j=0;j<10;j++) //對每一個鏈隊迴圈， 蒐集每一個元素
{
if(head[j]!=NULL) //進行蒐集
{
if(p==NULL)
{
p=head[j];
q=tail[j];
}
else
{
q->next=head[j];
q=tail[j];
}
}
}
q->next=NULL; //最後一個結點的next置為空
d=d*10;
n=0;
m=1;
while(m<=L.length) //判斷當L中的元素都除d後是不是都為零了
{
if((L.r[m]/d)!=0)
{
n++;
m++;
}
else
m++;
}
}
i=1;
while(p!=NULL) //將連結串列轉換為順序表
{
L.r[i]=p->key;
i++;
p=p->next;
}
return OK;
}
//**************************************
// 主函式
//**************************************
void main()
{
Sqlist L;
Sqlist L0;
InitSqlist(L); //初始化L
InitSqlist(L0);
int m,i;
char choice='z';
clock_t start, finish; //定義clock_t用於計時
double duration;
//向L中輸入元素
printf("\n *********************************************************************** \n");
printf(" \n");
printf(" 排序演算法的比較系統 \n");
printf(" \n");
printf(" *********************************************************************** \n");
printf(" 以下是各個排序演算法的代號：\n\n");
printf(" 1、直接插入排序 \n");
printf(" 2、折半插入排序 \n");
printf(" 3、起泡排序 \n");
printf(" 4、快速排序\n");
printf(" 5、選擇排序\n");
printf(" 6、堆排序\n");
printf(" 7、基數排序\n");
printf(" 8、退出該系統\n\n");
ScanfSqlist(m,L0);
printf("\n");
printf(" 1、直接插入排序 \n");
printf(" 2、折半插入排序 \n");
printf(" 3、起泡排序 \n");
printf(" 4、快速排序\n");
printf(" 5、選擇排序\n");
printf(" 6、堆排序\n");
printf(" 7、基數排序\n");
printf(" 8、退出該系統\n\n");
printf("\n請選擇排序的方式,數字1-7: ");
scanf("%d",&choice); //選擇排序方式賦值choice，用於後面的函式選擇
while(choice<1 choice>8)
{
printf("輸入方式有誤。\n請輸入1-7選擇排序方式，或者選擇8退出系統");
scanf("%d",&choice);
}
while(choice!=8)
{
for(i=1;i<=L0.length;i++)
L.r[i]=L0.r[i];
L.length=L0.length;
switch(choice)
{
case 1://直接插入排序
start = clock();
InsertSort(L);
finish = clock();
break;
case 2://折半插入排序
start = clock();
BInsertSort(L);
finish = clock();
break;
case 3://起泡排序
start = clock();
BubbleSort(L);
finish = clock();
break;
case 4://快速排序
start = clock();
QuickSort(L);
finish = clock();
break;
case 5://選擇排序
start = clock();
ChooseSort(L);
finish = clock();
break;
case 6://堆排序
start = clock();
HeapSort(L);
finish = clock();
break;
case 7://基數排序
start = clock();
RadixSort(L);
finish = clock();
break;
case 8://直接退出
break;
}
PrintfSqlist(m,L); //輸出資料和L的長度
duration = (double)(finish - start) / CLOCKS_PER_SEC; //輸出算術時間
printf("\n本次排序運算所用的時間是：%lf seconds\n",duration);
printf(" 本次排序結束。\n");
printf(" ___________________________________________________________________\n");
printf(" 繼續本系統嗎？\n\n");
printf(" 以下是各個排序演算法的代號：\n");
printf(" 1、直接插入排序\n");
printf(" 2、折半插入排序\n");
printf(" 3、起泡排序\n");
printf(" 4、快速排序\n");
printf(" 5、選擇排序\n");
printf(" 6、堆排序\n");
printf(" 7、基數排序\n");
printf(" 8、退出該系統\n");
printf("\n請請輸入1-7選擇排序方式，或者選擇8退出系統:");
scanf("%d",&choice);
while(choice<1 choice>8)
{
printf("輸入方式有誤。\n請輸入1-7選擇排序方式，或者選擇8退出系統");
scanf("%d",&choice);
}
}
}
一、實驗目標：
（1） 幾種排序演算法在平均情況下哪一個更快。
（2） 加深對時間複雜度概念的理解。
實驗任務：
（1）實現幾種排序演算法（selectionsort, insertionsort,bottomupsort,quicksort, 堆排序）。對於快速分類，SPLIT
中的劃分元素採用三者A(low)，A(high)，A((low+high)/2)中其值居中者。
（2）隨機產生20組資料（比如n=5000i，1≤i≤20）。資料均屬於範圍（0，105）內的整數。對於同一組資料，
執行以上幾種排序演算法，並記錄各自的執行時間（以毫秒為單位）。
（3）根據實驗資料及其結果來比較這幾種分類演算法的平均時間和比較次數，並得出結論。 實驗裝置及環境：
PC；C/C++等程式語言。
二、實驗主要步驟：
(1) 明確實驗目標和具體任務；
(2) 理解實驗所涉及的幾個分類演算法；
(3) 編寫程式實現上述分類演算法；
(4) 設計實驗資料並執行程式、記錄執行的結果；
(5) 根據實驗資料及其結果得出結論；
(6) 實驗後的心得體會。
三、程式所用到的排序方法
(" 1、直接插入排序\n");
printf(" 2、折半插入排序\n");
printf(" 3、起泡排序\n");
printf(" 4、快速排序\n");
printf(" 5、選擇排序\n");
printf(" 6、堆排序\n");
printf(" 7、基數排序\n");
printf(" 8、退出該系統\n");
四、原始碼
#include "stdio.h"
#include "stdlib.h"
#include "time.h"//計時
printf(" 本次排序結束。\n");
printf(" ___________________________________________________________________\n");
printf(" 繼續本系統嗎？\n\n");
printf(" 以下是各個排序演算法的代號：\n");
printf(" 1、直接插入排序\n");
printf(" 2、折半插入排序\n");
printf(" 3、起泡排序\n");
printf(" 4、快速排序\n");
printf(" 5、選擇排序\n");
printf(" 6、堆排序\n");
printf(" 7、基數排序\n");
printf(" 8、退出該系統\n");
printf("\n請請輸入1-7選擇排序方式，或者選擇8退出系統:");
scanf("%d",&choice);
while(choice<1 choice>8)
{
printf("輸入方式有誤。\n請輸入1-7選擇排序方式，或者選擇8退出系統");
scanf("%d",&choice);
}
}
}
五、實驗結果分析及結論：
實驗結果表明,選擇排序用時普遍比其它演算法大,自頂向上合併排序時間普遍較少,尤其是當資料量變得很大的時候,選擇排序的速度變得遠遠不及自頂向上合併排序演算法,大出好幾百倍.另外,插入排序在當資料量變大時花費的時間也變得很長.快速排序和堆排序處於不確定的情況,不穩定性表現比較明顯.但是還是一種比較快的C語言演算法.
六、實驗自我評價及心得體會：
通過本實驗,我發現以前經常使用的氣泡排序,選擇排序等排序方法在遇到大量的資料的時候顯示出來的嚴重的不足而自底向上合併排序卻顯示出了其優越性,儘管合併排序的演算法比較難,但它在時間上節省讓人發現一切都是值得的.
注意事項
認真
堅持