數(shù)據(jù)結(jié)構(gòu) 內(nèi)部排序算法比較

內(nèi)部排序算法比較1、課程設(shè)計的目的本課程設(shè)計為了更好的了解和認識數(shù)據(jù)結(jié)構(gòu)常用的內(nèi)部排序算法。排序?qū)τ跀?shù)據(jù)結(jié)構(gòu)的管理來說是至關(guān)重要的，所以熟悉掌握和深入了解這些常用的經(jīng)典內(nèi)部排序算法是有必要的。2、課程設(shè)計的要求1.掌握常用的排序方法和各種排序方法的特點。2.熟悉排序的基本概念。3、課程設(shè)計的內(nèi)容3.1需求分析編制一個演示內(nèi)部排序算法比較的程序。可對冒泡排序、直接插入排序、簡單選擇排序、快速排序、希爾排序和堆排序進行比較。3.2概要設(shè)計（1）冒泡排序基本思想是：設(shè)數(shù)組a中存放了n個數(shù)據(jù)元素，循環(huán)進行n-1次如下的排序過程：第一次時，依次比較相鄰兩個數(shù)據(jù)元素a[i]和a[i+1].key(i=0,1,2,3...,n-2).若為逆序，則交換兩個數(shù)據(jù)元素，否則不交換，這樣，當作完n-1次比較后數(shù)值最大的數(shù)據(jù)元素將比放置在a[n-1]中。第二次時，數(shù)據(jù)元素個數(shù)減1，即數(shù)據(jù)元素個數(shù)為n-1，操作方法與第一次類似，這樣，n個數(shù)據(jù)元素集合中數(shù)值次大的數(shù)據(jù)元素將被放置在a[n-2]中。當?shù)趎-1次排序結(jié)束時，n個數(shù)據(jù)元素集合中次小的數(shù)據(jù)元素將被放置在a[1]中，而a[0]中放置了最小的數(shù)據(jù)元素。冒泡排序算法的空間復(fù)雜度為o(n2)。（2）直接插入排序基本思想是:順序地把待插入的數(shù)據(jù)元素按其關(guān)鍵字的大小插入到已排序數(shù)據(jù)元素子集合的適當位置.子集合的數(shù)據(jù)元素個數(shù)從只有一個數(shù)據(jù)元素開始逐次增大,當子集合最終與集合大小相同時排序完畢.設(shè)待排序的N個數(shù)據(jù)元素存放在數(shù)組A中,初始時子集合a[0]以排好序.第一次循環(huán)準備把數(shù)據(jù)元素a[1]插入到以排好序的子集合中,這只需比較a[0].key和a[1].key,若a[0].key<=a[1].key,則說明序列已有序,否則,將a[1]插入到a[0]之前,這樣子集合的大小增大為2;第二次循環(huán)是把數(shù)據(jù)元素a[2]插入到以排好序的子集合中,這需要先比較a[2].key和a[1].key,已確定是否需要把a[2]插到a[1]之前,然后比較a[2].key和a[0].key,以確定是否需要把a[2]插入到a[0]之前;這樣的循環(huán)過程一直進行到a[n-1]插入完為止.這時,數(shù)據(jù)元素集合a[0],a[1],a[2],...,a[n-1]就全部排好了序。直接插入排序算法最壞情況下的時間復(fù)雜度為O(n2).（3）直接選擇排序基本思想是：從待排序的數(shù)據(jù)元素集合中選取關(guān)鍵字最小的數(shù)據(jù)元素并將它與原始數(shù)據(jù)元素集合中的第一個數(shù)據(jù)元素交換位置；然后從不包括第一個位置的數(shù)據(jù)元素集合中選取關(guān)鍵字最小的數(shù)據(jù)元素并將它與原始數(shù)據(jù)集合中的第二個數(shù)據(jù)元素交換位置；如此重復(fù)，直到數(shù)據(jù)元素集合中只剩一個數(shù)據(jù)元素為止。直接選擇排序算法的時間復(fù)雜度為O(n2)。（4）快速排序快速排序是一種二叉樹結(jié)構(gòu)的交換排序方法，其基本思想是：設(shè)數(shù)組a中存放了n個數(shù)據(jù)元素，low為數(shù)組的低端下標，high為數(shù)組的高端下標，從數(shù)組a中任取一個元素作為標準，調(diào)整數(shù)組a中各個元素的位置，使排在標準元素前面元素的關(guān)鍵字均小于標準元素的關(guān)鍵字，排在標準元素后面元素均大于或等于標準元素的關(guān)鍵字。這樣一次過程結(jié)束后，一方面將標準元素放在了未來排好序的數(shù)組中該標準元素應(yīng)在的位置上，另一方面將數(shù)組中的元素以標準元素為中心分為了兩個子數(shù)組，位于標準元素左邊均大于等于標準元素的關(guān)鍵字。然后對這兩個子數(shù)組中的元素分別再進行方法類同的遞歸快速排序。（5）堆排序堆排序的基本思想是：循環(huán)執(zhí)行如下過程直到數(shù)組為空：(1)把堆頂a[0]元素為最大元素與當前最大堆的最后一個元素交換；(2)最大堆元素個數(shù)減1；(3)若此時根節(jié)點不滿足最大堆的定義，則調(diào)整根節(jié)點使之滿足最大堆的定義。堆排序算法的時間復(fù)雜度為O(nlog2n)。（6）各種排序的比較通過計算各種排序算法的平均時間復(fù)雜度等來比較幾種算法。冒泡排序算法平均時間復(fù)雜度為o(n2)。冒泡排序算法的空間復(fù)雜度為o(1).顯然，冒泡排序是一種穩(wěn)定的排序方法。直接插入排序算法的時間復(fù)雜度為o(n2)，空間復(fù)雜度為O(1).顯然,直接插入排序算法是一種穩(wěn)定的排序算法.直接選擇排序算法的時間復(fù)雜度為O(n2)。直接選接排序算法的空間復(fù)雜度為o(2)。顯然,直接選擇排序算法是一種不穩(wěn)定的排序算法.快速排序算法的平均算法復(fù)雜度為O（log2n）。平均空間復(fù)雜度為O（log2n）。快速排序算法是一種不穩(wěn)定的排序方法。堆排序算法的時間復(fù)雜度為O(nlog2n)。堆排序算法的空間復(fù)雜度為O(1)。觀察例子即可發(fā)現(xiàn)，堆排序算法是一種不穩(wěn)定的排序方法。3.3詳細設(shè)計（源代碼）#include<stdio.h>#include<time.h>#include<stdlib.h>#include<malloc.h>typedefintDataType;#defineMaxSize100staticintSortTAndTs[6][4];voidSortTimeAndTimes(intNo,inttime,inttimes)//算法的數(shù)據(jù)交換次數(shù)和算法耗時{SortTAndTs[No][1]=No; SortTAndTs[No][2]=time;SortTAndTs[No][3]=times;}voidShowResult(){ printf("排序方法\t數(shù)據(jù)交換次數(shù)\t排序所耗時間\n"); for(inti=1;i<=6;i++) { if(SortTAndTs[i][1]==1) { printf("冒泡排序法\t"); printf("%d\t\t",SortTAndTs[i][2]); printf("%d\n",SortTAndTs[i][3]); } elseif(SortTAndTs[i][1]==2) { printf("直接插入排序\t"); printf("%d\t\t",SortTAndTs[i][2]); printf("%d\n",SortTAndTs[i][3]); } elseif(SortTAndTs[i][1]==3) { printf("直接選擇排序\t"); printf("%d\t\t",SortTAndTs[i][2]); printf("%d\n",SortTAndTs[i][3]); } elseif(SortTAndTs[i][1]==4) { printf("快速排序\t"); printf("%d\t\t",SortTAndTs[i][2]); printf("%d\n",SortTAndTs[i][3]); } elseif(SortTAndTs[i][1]==5) { printf("堆排序\t\t"); printf("%d\t\t",SortTAndTs[i][2]); printf("%d\n",SortTAndTs[i][3]); } } }voidNoSort(intb[],intn)//排序前亂序數(shù)據(jù)輸出{ inti; inta[MaxSize]; for(i=0;i<n;i++) a[i]=b[i]; printf("排序前數(shù)據(jù)\t"); for(i=0;i<n;i++) { printf("%4d",a[i]); //printf("\t"); } printf("\n\n");}voidMaoPao(intb[],intn)//冒泡法排序{ NoSort(b,n); inti,j,flag=1; intq; inta[MaxSize]; for(i=0;i<n;i++) a[i]=b[i]; a[i]='\0'; clock_tbegin,end;//定義計時器 DataTypetemp; printf("冒泡法排序\n"); printf("排序過程\n"); begin=clock();//開始計時 for(i=1;i<n&&flag==1;i++) { flag=0; for(j=0;j<n-i;j++) { if(a[j]>a[j+1]) { flag=1; temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } printf("第%d次排序結(jié)果\t",i); for(q=0;q<n;q++) { printf("%4d",a[q]);//printf("\t"); } printf("\n\n"); } end=clock();//結(jié)束計時SortTimeAndTimes(1,i,end-begin); printf("所用時間%d\n",end-begin);}voidZhiJie(intb[],intn)//直接插入排序{ NoSort(b,n); inti,j; DataTypetemp; intq; inta[MaxSize]; for(i=0;i<n;i++) a[i]=b[i]; a[i]='\0'; clock_tbegin,end;//定義計時器 printf("直接插入排序\n"); printf("排序過程\n"); begin=clock();//開始計時 for(i=0;i<n-1;i++) { temp=a[i+1]; j=i; while(j>-1&&temp<a[j]) { a[j+1]=a[j]; j--; } a[j+1]=temp; printf("第%d次排序結(jié)果\t",i+1); for(q=0;q<n;q++) { printf("%4d",a[q]);//printf("\t"); } printf("\n\n"); } end=clock();//結(jié)束計時 SortTimeAndTimes(2,i+1,end-begin); printf("所用時間%d\n",end-begin);}voidSelectSort(intb[],intn)//直接選擇排序{ NoSort(b,n); inti,j,small; DataTypetemp; intq; inta[MaxSize]; for(i=0;i<n;i++) a[i]=b[i]; a[i]='\0'; clock_tbegin,end;//定義計時器 printf("直接選擇排序\n"); printf("排序過程\n"); begin=clock();//開始計時 for(i=0;i<n-1;i++) { small=i; for(j=i+1;j<n;j++) if(a[j]<a[small])small=j; if(small!=i) { temp=a[i]; a[i]=a[small]; a[small]=temp; } printf("第%d次排序結(jié)果\t",i+1); for(q=0;q<n;q++) { printf("%4d",a[q]); } printf("\n\n"); } end=clock();//結(jié)束計時 SortTimeAndTimes(3,i+1,end-begin); printf("所用時間%d\n",end-begin);}voidQuickSort(DataTypeb[],intn,intlow,inthigh)//快速排序{ inti; staticintsum=1; intleap=0; intq; inta[MaxSize]; for(i=0;i<n;i++) a[i]=b[i]; a[i]='\0'; clock_tbegin,end;//定義計時器 DataTypetemp=a[low];/*第一個元素為標準數(shù)據(jù)元素*/ begin=clock();//開始計時i=low; intj=high; while(i<j) { while(i<j&&temp<=a[j])j--;/*在數(shù)組的右端掃描*/ if(i<j) { a[i]=a[j]; i++; leap=1; } while(i<j&&a[i]<temp)i++;/*在數(shù)組的左端掃描*/ if(i<j) { a[j]=a[i]; j--; leap=1; } } a[i]=temp; if(leap==1) { printf("第%d次排序結(jié)果\t",sum); for(q=0;q<n;q++) { printf("%4d",a[q]); } sum++; printf("\n\n"); } if(low<i)QuickSort(a,n,low,i-1);/*對左端子集合進行遞歸*/ if(i<high)QuickSort(a,n,j+1,high);/*對右端子集合進行遞歸*/ if(high>low) { end=clock();//結(jié)束計時 SortTimeAndTimes(4,sum,end-begin); printf("所用時間%d\n",end-begin); } } intCreatHeap(DataTypea[],intn,inth){ inti,j,flag; staticintsum=0,q=0; DataTypetemp; i=h; j=2*i+1; temp=a[i]; flag=0; while(j<n&&flag!=1) { if(j<n-1&&a[j]<a[j+1])j++; if(temp>a[j]) flag=1; else { a[i]=a[j]; i=j; j=2*i+1; } } a[i]=temp; if(flag==0) { printf("第%d次排序結(jié)果\t",sum+1); for(q=0;a[q]!='\0';q++) { printf("%4d",a[q]); } printf("\n"); printf("\n"); sum++; } returnsum;}voidInitCreatHeap(DataTypea[],intn){ inti; for(i=(n-1)/2;i>=0;i--) CreatHeap(a,n,i);}voidHeapSort(intb[],intn)//堆排序{ NoSort(b,n); inti; inttimes; inta[MaxSize]; for(i=0;i<n;i++) a[i]=b[i]; a[i]='\0'; DataTypetemp; clock_tbegin,end;//定義計時器 printf("堆排序\n"); printf("排序過程\n"); begin=clock();//開始計時 InitCreatHeap(a,n); for(i=n-1;i>0;i--) { temp=a[0]; a[0]=a[i]; a[i]=temp; times=CreatHeap(a,i,0); } end=clock();//結(jié)束計時 SortTimeAndTimes(6,times,end-begin); printf("所用時間%d\n",end-begin);}voidmain(){ intBiaoChang=0; inti=0,j=0; intptrData[MaxSize]; intchoose; charpause; while(1) {printf("**************************************************************\n"); printf("****\n"); printf("****\n");printf("**歡迎使用內(nèi)部排序算法分析器**\n"); printf("****\n"); printf("**算法選擇提示**\n"); printf("****\n");printf("**1.冒泡排序**\n"); printf("**2.直接插入排序**\n"); printf("**3.簡單選擇排序**\n"); printf("**4.快速排序**\n"); printf("**5.堆排序**\n"); printf("**6.所有排列比較**\n"); printf("**0.退出程序**\n"); printf("****\n"); printf("************************************************************\n"); printf("請輸入要排序的數(shù)據(jù)表的表長"); scanf("%d",&BiaoChang);printf("請輸入要排序的數(shù)據(jù)\n"); //srand((unsigned)time(NULL)); for(i=0;i<BiaoChang;i++) { scanf("%d",&ptrData[i]); //ptrData[i]=rand()*10%1000; }ptrData[i]='\0'; //for(q=0;q<BiaoChang;q++) // { // printf("%d",ptrData[q]);//printf("");// // }printf("請選擇排序方法\n");printf("\n"); scanf("%d",&choose); switch(choose) { case1:MaoPao(ptrData,Bi