內(nèi)部排序算法比較

1、內(nèi)部排序算法比較班級(jí)： 姓名： 學(xué)號(hào)： 完成日期：題目：試通過(guò)隨機(jī)數(shù)據(jù)比較各算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動(dòng)次數(shù)，以取得直觀感受。一需求分析1.對(duì)常用的6種內(nèi)部排序算法進(jìn)行比較：冒泡排序，直接插入排序，簡(jiǎn)單選擇排序，快速排序，希爾排序，堆排序。2.待排序表的表長(zhǎng)不小于100；其中的數(shù)據(jù)要用偽隨機(jī)數(shù)產(chǎn)生程序產(chǎn)生；至少要用5組不同的輸入數(shù)據(jù)作比較；比較的指標(biāo)為有關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字的移動(dòng)次數(shù)（關(guān)鍵字交換計(jì)為3次移動(dòng)）3.最后要對(duì)結(jié)果作出簡(jiǎn)單分析，包括對(duì)各組數(shù)據(jù)得到結(jié)果波動(dòng)大小的解釋。二概要設(shè)計(jì)1.主界面設(shè)計(jì)對(duì)六種內(nèi)部排序算法進(jìn)行比較，可通過(guò)隨機(jī)數(shù)程序產(chǎn)生幾組數(shù)，要求用戶手動(dòng)輸入產(chǎn)生隨機(jī)數(shù)的

2、個(gè)數(shù)。運(yùn)行界面如圖所示：選擇1運(yùn)行程序，選擇2退出程序2存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)本程序采用順序表結(jié)構(gòu)，具體結(jié)構(gòu)定義如下：typedef struct int key; ElemType;typedef struct ElemType *elem; int length;SqList;3.系統(tǒng)功能設(shè)計(jì)1）分配內(nèi)存空間。創(chuàng)建順序表2）利用偽隨機(jī)數(shù)產(chǎn)生程序產(chǎn)生隨機(jī)數(shù)，作為程序運(yùn)行的數(shù)據(jù)3）實(shí)現(xiàn)每種排序算法的功能函數(shù)三模塊設(shè)計(jì)隨機(jī)數(shù)產(chǎn)生模塊1.模塊設(shè)計(jì)主程序模塊排序算法模塊2.系統(tǒng)子程序及功能設(shè)計(jì)本系統(tǒng)共設(shè)置13個(gè)函數(shù)，其中包括主函數(shù)。各函數(shù)名及功能說(shuō)明如下。1） void addlist(SqList &

3、;L) /建立個(gè)空順序表2） void random(SqList &L) /隨機(jī)數(shù)產(chǎn)生函數(shù)3） void memory(SqList &M,SqList &L) /記錄L，以保證每個(gè)排序函數(shù)使用一組隨機(jī)數(shù)4） void BubbleSort(SqList &L) /冒泡排序5） void InsertSort(SqList &L) /直接插入排序6） void SelectSort(SqList &L) /選擇排序7） int Partition(SqList &L,int low,int high) /返回快速排序樞軸的位置8） vo

4、id QSort(SqList &L,int low,int high) /對(duì)子序列作快速排序9） void QuickSort(SqList &L) /對(duì)數(shù)序表作快速排序10）void ShellSort (SqList &L) /希爾排序11）void HeapAdjust(SqList &L,int s,int m )/堆排序算法子程序12）void HeapSort(SqList &L) /對(duì)順序表進(jìn)行堆排序13）void main() /主函數(shù)，調(diào)用各模塊函數(shù)3.函數(shù)主要調(diào)用關(guān)系913）main（）51243211068117四詳細(xì)設(shè)計(jì)1.數(shù)據(jù)

5、類型定義typedef struct int key; ElemType;typedef struct ElemType *elem; int length;SqList;2.全局變量定義int bj1=0,yd1=0,bj2=0,yd2=0,bj3=0,yd3=0,bj4=0,yd4=0,bj5=0,yd5=0,bj6=0,yd6=0;/記錄每種算法的比較，移動(dòng)次數(shù)int n；/隨機(jī)數(shù)的個(gè)數(shù)2.系統(tǒng)主要子程序詳細(xì)設(shè)計(jì)（1）主函數(shù)設(shè)計(jì)模塊主要是輸入數(shù)據(jù)，以及程序界面的設(shè)計(jì)，調(diào)用系統(tǒng)的各個(gè)子程序，并輸出結(jié)果。（詳見(jiàn)源程序）（2）隨機(jī)數(shù)產(chǎn)生模塊利用偽隨機(jī)數(shù)產(chǎn)生程序產(chǎn)生數(shù)據(jù)，并存儲(chǔ)到順序表中。voi

6、d random(SqList &L) L.length=0;static bool first=true;if(first)srand(time(0);first=false;/使每次產(chǎn)生的隨機(jī)數(shù)不同for(int i=1;i<n+1;i+)a: L.elemi.key=rand(); if(L.elemi.key>30000) goto a; +L.length; （3）排序算法模塊實(shí)現(xiàn)冒泡排序，直接插入排序，簡(jiǎn)單選擇排序，快速排序，希爾排序以及堆排序的算法。（祥見(jiàn)源程序）五測(cè)試分析運(yùn)行程序后，得到如圖所示：輸入：1輸入：100選擇1重復(fù)上述步驟，輸入150，200，2

7、50，300得到另外四個(gè)結(jié)果：退出程序，請(qǐng)選擇：2結(jié)果分析：冒泡排序，直接插入排序以及簡(jiǎn)單選擇排序比較次數(shù)較多，快速排序，希爾排序及堆排序比較次數(shù)較少；并可得冒泡排序和直接插入排序相對(duì)較穩(wěn)定，其他四種內(nèi)部排序?yàn)椴环€(wěn)定排序。六源程序清單#include"iostream"#include"stdio.h"#include"stdlib.h"#include"string.h"#include"time.h"using namespace std;#define LIST_INIT_SIZE 500

8、00int bj1=0,yd1=0,bj2=0,yd2=0,bj3=0,yd3=0,bj4=0,yd4=0,bj5=0,yd5=0,bj6=0,yd6=0,n;/yd，bj為記錄關(guān)鍵字比較和移動(dòng)的次數(shù)typedef struct int key; ElemType;typedef struct ElemType *elem; int length;SqList;void addlist(SqList &L)/初始化順序表a: printf("請(qǐng)輸入你要輸入的個(gè)數(shù):"); scanf("%d",&n); if(n>50000) pri

9、ntf("超出范圍重新輸入!n"); goto a; L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType); if(!L.elem)exit(0);void random(SqList &L)/隨機(jī)數(shù)產(chǎn)生程序 L.length=0;static bool first=true;if(first)srand(time(0);first=false;/使輸入相同個(gè)數(shù)時(shí)每次產(chǎn)生的隨機(jī)數(shù)不同for(int i=1;i<n+1;i+)a: L.elemi.key=rand(); if(L.elemi.key&g

10、t;30000) goto a; +L.length; void memory(SqList &M,SqList &L)/記錄L，使每個(gè)排序算法都用一組相同的隨機(jī)數(shù) M.length=0;for(int i=1;i<n+1;i+)M.elemi.key=L.elemi.key;+M.length;void BubbleSort(SqList &L)/冒泡排序int i,j;for(i=1;i<L.length;i+)for(j=1;j<L.length-i+1;j+)bj1+;if(L.elemj.key>L.elemj+1.key) L.ele

11、m0.key=L.elemj.key; L.elemj.key=L.elemj+1.key; L.elemj+1.key=L.elem0.key; yd1+=3; void InsertSort(SqList &L)/直接插入排序 int i,j; for(i=2;i<=L.length;i+) if(L.elemi.key<L.elemi-1.key) L.elem0.key=L.elemi.key; yd2+; j=i-1; bj2+; while(L.elem0.key<L.elemj.key) L.elemj+1.key=L.elemj.key; j-; yd

12、2+; bj2+; L.elemj+1.key=L.elem0.key; yd2+; void SelectSort(SqList &L)/選擇排序 int i,j,k; for(i=1;i<L.length;i+) k=i; for(j=i+1;j<L.length;j+) bj3+; if(L.elemj.key<L.elemk.key)k=j; if(i!=k) L.elem0.key=L.elemi.key; L.elemi.key=L.elemk.key; L.elemk.key=L.elem0.key; yd3+=3; int Partition(SqLi

13、st &L,int low,int high)/快速排序 int pivotkey; L.elem0=L.elemlow; yd4+; pivotkey=L.elemlow.key; while (low<high) yd4+; while(low<high&&L.elemhigh.key>=pivotkey) -high; L.elemlow=L.elemhigh; bj4+; yd4+; while (low<high&&L.elemlow.key<=pivotkey) +low; L.elemhigh=L.elemlo

14、w; bj4+; yd4+; L.elemlow=L.elem0; yd4+; return low;void QSort(SqList &L,int low,int high)/對(duì)順序表的子序列作快速排序 int pivotloc; if(low<high) pivotloc=Partition(L,low,high); QSort(L,low,pivotloc-1); QSort(L,pivotloc+1,high); void QuickSort(SqList &L)/對(duì)順序表L作快速排序 QSort(L,1,L.length);void ShellSort(SqL

15、ist &L)/希爾排序 int i,d=L.length/2,j,w=0,k; while(w<d) w=1; for(i=w;i<L.length;i=i+d) k=i; for(j=i+d;j<L.length;j=j+d) if(L.elemi.key>L.elemj.key) k=j; bj5+; if(i!=k) L.elem0.key=L.elemi.key; L.elemi.key=L.elemk.key; L.elemk.key=L.elem0.key; yd5+=3; w+; d=d/2; w=1; void HeapAdjust(SqLis

16、t &L,int s,int m )/調(diào)整L.elems的關(guān)鍵字，使L.elems.m成為一個(gè)大根堆SqList rc; rc.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType); if(!rc.elem)exit(0);int j;rc.elem0=L.elems;for(j=2*s;j<=m;j*=2)bj6+;if(j<m&&L.elemj.key<L.elemj+1.key)+j;bj6+;if(!(rc.elem0.key<L.elemj.key) break;L.elems=L

17、.elemj;s=j;yd6+=3;L.elems=rc.elem0;void HeapSort(SqList &L)/對(duì)順序表L進(jìn)行堆排序int i;for(i=L.length/2;i>0;-i)HeapAdjust(L,i,L.length);for(i=L.length;i>1;-i)L.elem1=L.elemi;yd6+=3;HeapAdjust(L,1,i-1);void main() SqList L,M; int a; M.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType); if(!M.elem)

18、exit(0);a:cout<<" -內(nèi)部排序算法比較-n" cout<<"*歡迎使用*n"cout<<"*(1)運(yùn)行程序*n"cout<<"*(2)退出系統(tǒng)*n" cout<<endl; cout<<"請(qǐng)選擇:" scanf("%d",&a);switch(a) case 1:system("cls");addlist(L);break;case 2:cout<<"謝謝使用"exit(0);break; random(L); memory(M,L); BubbleSort(M); memory(M,L); InsertSort(M); memory(M,L); SelectSort(M); memory(M,L); QuickSort(M); memory(M,L); ShellSort(M); memory(M,L); HeapSort(L); cout<<" *比較次數(shù)*移動(dòng)次數(shù)*n" cout<<"冒泡排序：