实验-各种排序方法的比较

《实验-各种排序方法的比较》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验六各种排序方法的比较一、实验目的1．通过实验掌握排序的基本概念，对排序的稳定性及排序的时间复杂性有深刻的认识。2．掌握各种排序方法的基本思想和算法实现。3．能够灵活地选用某种排序方法解决问题。二、实验要求1．认真阅读和掌握本实验的参考程序。2．保存程序的运行结果，并结合程序进行分析。三、实验内容编写一个程序，对所给的数据(程序中给出或通过键盘初始化均可)进行排序，要求尽可能多的选择不同的排序算法，并显示排序前和排序后的结果。#include#include#defineTRUE1

2、#defineFALSE0#defineN10inta[10]={9,27,45,87,17,23,25,92,8,75};typedefstruct{intkey;intinfo;}RecordNode;typedefstructSort{intn;//记录个数RecordNode*record;}SortObject;/*直接插入排序*/voidinsertSort(SortObject*pvector){inti,j;RecordNodetemp;for(i=1;in;i++){temp=pve

3、ctor->record[i];j=i-1;while((temp.keyrecord[j].key)&&(j>=0)){pvector->record[j+1]=pvector->record[j];j--;}if(j!=(i-1))pvector->record[j+1]=temp;}}/*二分法插入排序*/voidbinSort(SortObject*pvector){inti,j,left,mid,right;RecordNodetemp;for(i=1;in;i++){t

4、emp=pvector->record[i];left=0;right=i-1;while(left<=right){mid=(left+right)/2;if(temp.keyrecord[mid].key)right=mid-1;elseleft=mid+1;}for(j=i-1;j>=left;j--)pvector->record[j+1]=pvector->record[j];if(left!=i)pvector->record[left]=temp;}}structNode;typedef

5、structNodeListNode;structNode{intkey;ListNode*next;};typedefListNode*LinkList;voidlistSort(LinkList*plist){ListNode*now,*pre,*p,*q,*head;head=*plist;pre=head->next;if(pre==NULL)return;now=pre->next;if(now==NULL)return;while(now!=NULL){q=head;p=head->next;while(p!

6、=now&&p->key<=now->key){q=p;p=p->next;}if(p==now){pre=pre->next;now=pre->next;continue;}pre->next=now->next;q->next=now;now->next=p;now=pre->next;}}/*Shell排序*/voidshellSort(SortObject*pvector,intd){/*按递增序进行Shell排序*/inti,j,increment;RecordNodetemp;for(increment=d;

7、increment>0;increment/=2){for(i=increment;in;i++){temp=pvector->record[i];j=i-increment;while(j>=0&&temp.keyrecord[j].key){pvector->record[j+increment]=pvector->record[j];j-=increment;}pvector->record[j+increment]=temp;}}}/*直接选择排序*/voidselectS

8、ort(SortObject*pvector){inti,j,k;RecordNodetemp;for(i=0;in-1;i++){/*做n-1趟选择排序*/k=i;for(j=i+1;jn;j++)/*在无序区内找出排序码最小的记录Rk*/if(pvector->record