排序演算法設計和比較

一、【實驗內容與要求】

問題描述：利用直接插入排序、氣泡排序、快速排序對數列進行排序。

基本要求：

（1）能隨機生成30個值為0到100的數。

（2）用於排序的輸入數列可以是要求（1）中隨機生成的，也可以是鍵盤輸入。

（3）輸出結果為利用三種方法排序後的結果，並能顯示三種演算法時間、空間效能引數值。

【測試資料】

由隨機自行生成若干個數，進行排序。

（包括程式的結構，資料結構，輸入/輸出設計，符號名說明等）

1）符號說明：

m1，m2，m3 代表三種排序法的迴圈次數

a,b,c 分別用來儲存三次排序的資料

temp中間變數

n參與排序的數字個數

maopao（a，n）冒泡程式排序

zhicha（b，n）直接插入排序

quick(a,h,l) 快速排序法

h分塊排序的上限

l分塊排序的下限

2）程式說明（結構，輸入輸出）

這個程式整個流程比較自然，一脈相傳，即先輸入要排序的個數，然後選擇要輸入的方式，將產生的數傳到陣列中，然後依次地用冒泡子程式，直接插入的程式，快速排序的方法，依次排序，並將排好的數輸出，以及演算法的時間複雜率。

3）程式流程圖

#include""

int m1=0;全域性變數定義冒泡法迴圈的次數

int m2=0; 全域性變數定義直接插入法迴圈的次數

int m3=0; 全域性變數定義快速法迴圈的次數

int suiji(int a,int n) ；隨機生成目的數函式

} jianpan(int a,int n) 鍵盤輸入目的數函式

} maopao(int a,int n) 冒泡法排序程式

m1++; 計算迴圈次數

}printf(" bubba the sorted nember:\n");

for(i=0;i

printf("time effective:%d",m1); 輸出冒泡法的時間效率m1

} zhicha(int b,int n) 直接插入排序子程式

b[j]=temp;

} for(i=0;iprintf(" %d",b[i]); 將排好的數顯示出來

if((i+1)%5==0) printf("\n");

}printf("time effective:%d\n",m2);輸出時間效率

} quick(int c,int l,int h) 快速排序法

int temp;

int i,j,k;

i=l;j=h;

if(l

if(ic[i++]=c[j];

while(itemp)

i++; m3++;}

if(ic[j--]=c[i];

c[i]=temp;

quick(c,l,i-1);遞迴呼叫排序

quick(c,i+1,h);遞迴呼叫排序

}}main()

if(k==2) k=2 則呼叫鍵盤輸入函式

for(i=0;i

maopao(a,n); 呼叫冒泡法程式

zhicha(b,n); 呼叫直接插入排序

printf("quick sort:\n");

quick(c,0,n-1); 呼叫快速排序法

for(i=0;i

printf("time effective:%d",m3);

getchar();

}_ 在寫程式的過程思路比較清晰，遇到的困難主要是程式設計軟體的不相容，或是某些c語言規則在一些軟體上為非法的，早先我用的一直用地是devc++，但是在用隨機生成數子函式，一直提示有錯誤，改正不了，最後只好用最原始的turbo c問題解決了，發現最好用的還是tc啊，以後只用突出（我電腦一直裝不了vc++，不知道怎麼回事），在具體程式設計中需要考慮的是函式形參和實參的格式，一定要一致。

這次程式中主要用三種排序方法：a。氣泡排序b直接插入排序c。快速排序。其中

氣泡排序的時間複雜度：o(n2) 空間複雜度：o(1)

直接插入排序時間複雜度：o(n2) 空間複雜度：o(1)

排序演算法設計和比較

VB幾種排序演算法的比較設計報告

排序演算法總結

排序演算法總結

排序演算法設計和比較

VB幾種排序演算法的比較設計報告

排序演算法總結

排序演算法總結

相關推薦