大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告材料各種排序算法性能比較

課程設(shè)計題目：各種排序算法性能比擬班級：2012年06月23日0/211/21 CONTENTS 2/21概述對3/21 時間復(fù)雜度分析SelectSort〕4/21 5/21 QuickSort〕個元素，經(jīng)過一趟排序后，將原序列分割成兩個子序列(R,R,…,R)和p(0)p(1)p(s-1)(R,R,…,R)，其中前一個子序列中的所有元素的關(guān)鍵詞均小于或等于p(s+1)p(s+2)p(n-1)該元素的關(guān)鍵詞值K，后一個子序列中元素的關(guān)鍵詞均大于或等于K。稱該p(s)p(s)元素R為分割元素，子序列(R,R,…,R)為其低端序列，p(s)p(0)p(1)p(s-1)(R,R,…,R)為其高端序列。很明顯，以后只需對低端和高端序列分別進p(0)p(1)p(s-1)226/21 t堆 直接插入排序#include<stdio.h>#include<stdlib.h>typedefstruct{ey}RecordNode;/*排序節(jié)點的類型*/typedefstruct{RecordNode*record;7/218/21 intn/*排序?qū)ο蟮拇笮?/}SortObject;/*排序節(jié)點的類型*/voidInsertSort(SortObject*p,unsignedlong*pare,unsignedlong*exchange){RecordNodetemp;SortObject*pvector;if((pvector=(SortObject*)malloc(sizeof(SortObject)))==NULL){printf("OverFollow!");getchar();exit(1);}for(i=0;i<p->n;i++)/*復(fù)制數(shù)組*/pvector->record[i]=p->record[i];pvector->n=p->n;*pare=0;*exchange=0;for(i=1;i<pvector->n;i++){temp=pvector->record[i];ji-1;while((temp.key<pvector->record[j].key)&&(j>=0))9/21 pvector->record[j+1]=pvector->record[j];j--;}{pvector->record[j+1]=temp;}}free(pvector);}voidSelectSort(SortObject*p,unsignedlong*pare,unsignedlong*exchange)RecordNodetemp;SortObject*pvector;if((pvector=(SortObject*)malloc(sizeof(SortObject)))==NULL){printf("OverFollow!");getchar();exit(1);}for(i=0;i<p->n;i++)/*復(fù)制數(shù)組*/pvector->record[i]=p->record[i];pvector->n=p->n;*pare=0;*exchange=0;10/21 for(i=0;i<pvector->n-1;i++)for(j=i+1;j<pvector->n;j++)eif(pvector->record[j].key<pvector->record[k].key)}{temp=pvector->record[i];pvector->record[i]=pvector->record[k];pvector->record[k]=temp;}}free(pvector);}voidBubbleSort(SortObject*p,unsignedlong*pare,unsignedlong*exchange)ijnoswapRecordNodetemp;SortObject*pvector;if((pvector=(SortObject*)malloc(sizeof(SortObject)))==NULL)printf("OverFollow!");getchar();exit(1);}11/21 for(i=0;i<p->n;i++)/*復(fù)制數(shù)組*/pvector->record[i]=p->record[i];pvector->n=p->n;*pare=0;*exchange=0;for(i=0;i<pvector->n-1;i++)if(pvector->record[j+1].key<pvector->record[j].key)temp=pvector->record[j];pvector->record[j]=pvector->record[j+1];pvector->record[j+1]=temp;noswap=0;}}}free(pvector);}voidShellSort(SortObject*p,intd,unsignedlong*pare,unsignedlong*exchange)inti,j,increment;RecordNodetemp;SortObject*pvector;12/21 if((pvector=(SortObject*)malloc(sizeof(SortObject)))==NULL)printf("OverFollow!");getchar();exit(1);}for(i=0;i<p->n;i++)/*復(fù)制數(shù)組*/pvector->record[i]=p->record[i];pvector->n=p->n;*pare=0;*exchange=0;for(increment=d;increment>0;increment/=2){for(i=increment;i<pvector->n;i++){temp=pvector->record[i];while(j>=0&&temp.key<pvector->record[j].key)epvector->record[j+increment]=pvector->record[j];j-=increment;}pvector->record[j+increment]=temp;}13/21 }free(pvector);}VoidSiftHeap(SortObject*pvector,intsize,intp,unsignedlong*pare,unsignedlong*exchange){RecordNodetemp;temp=pvector->record[p];child=2*i+1;while(child<size){if(child<size-1&&pvector->record[child].key<pvector->record[child+1].key){child++;}if(temp.key<pvector->record[child].key){14/21 pvector->record[i]=pvector->record[child];child=2*i+1;}elsebreak;}pvector->record[i]=temp;}voidHeapSort(SortObject*p,unsignedlong*pare,unsignedlong*exchange)RecordNodetemp;SortObject*pvector;if((pvector=(SortObject*)malloc(sizeof(SortObject)))==NULL){printf("OverFollow!");getchar();exit(1);}for(i=0;i<p->n;i++)pvector->record[i]=p->record[i];pvector->n=p->n;*pare=0;*exchange=0;15/21 n=pvector->n;for(i=n/2-1;i>=0;i--)SiftHeap(pvector,n,i,pare,exchange);{temp=pvector->record[0];pvector->record[0]=pvector->record[i];pvector->record[i]=temp;SiftHeap(pvector,i,0,pare,exchange);}free(pvector);}RecordNodetemp;temp=pvector->record[i];while(i!=j){while((pvector->record[j].key>=temp.key)&&(j>i))j--; }{pvector->record[i++]=pvector->record[j];}while((pvector->record[i].key<=temp.key)&&(j>i)){}{pvector->record[j--]=pvector->record[i];}}pvector->record[i]=temp;QuickSort(pvector,left,i-1,pare,exchange);QuickSort(pvector,i+1,right,pare,exchange);}voidSortMethod(void)unsignedlongnum[3][12]={0};16/2117/21 SortObject*pvector=(SortObject*)malloc(sizeof(SortObject));randomize();for(j=0;j<3;j++){for(i=0;i<MAXSORTNUM[j];i++)pvector->record[i].key=random(5000);pvector->n=MAXSORTNUM[j];InsertSort(pvector,&num[j][0],&num[j][1]);SelectSort(pvector,&num[j][2],&num[j][3]);BubbleSort(pvector,&num[j][4],&num[j][5]);ShellSort(pvector,4,&num[j][6],&num[j][7]);Heapsort(pvector,&num[j][8],&num[j][9]);QuickSort(pvector,0,MAXSORTNUM[j]-1,&num[j][10],&num[j][11]);}printf("\nSortMethodpareAsFollows:");for(j=0;j<3;j++){printf("\n\nWhenThemaxnumis%d,theresultis:\n",MAXSORTNUM[j]);printf("1.InsertSortMethod:pared-->%-7ldExchanged-->%-7ld\n",num[j][0],num[j][1printf("2.SelectSortMethod:pared-->%-7ldExchanged-->%-7ld\n",num[j][2],num[j][3]);printf("3.BubbleSortMethod:pared-->%-7ldExchanged-->%-7ld\n",num[j][4],num[j][5printf("4.ShellSortMethod:pared-->%-7ldExchanged-->%-7ld\n",num[j][6],num[j][7]);18/21printf("5.HeapSortMethod:pared-->%-7ldExchanged-->%-7ld\n",num[j][8],num[j][