排序实验报告_排序综合实验报告材料

　数据结构

　排序算法综合实验报告

　姓 名： xx x x

　班 级： 10电信1

　学 号： xxx

　指导老师： 胡圣荣

　日期： 2012.12.15～2013.1.5

　华南农业大学工程学院

　算法基本思想：

　1、插入排序：每次将一个待排序的记录，按其关键字大小插入到前面已经排序好的序列中的适当位置，直到全部记录插入完毕为止。

　（1）直接插入排序：在排序过程中，每次都讲无序区中第一条记录插入到有序区中适当位置，使其仍保持有序。初始时，取第一条记录为有序区，其他记录为无序区。显然，随着排序过程的进行，有序区不断扩大，无序区不断缩小。最终无序区变为空，有序区中包含了所有的记录，排序结束。

　（2）希尔排序：将排序表分成若干组，所有相隔为某个“增量”的记录为一组，在各组进行直接插入排序；初始时增量d1较大，分组较多（每组的记录数少），以后增量逐渐减少，分组减少（每组的记录数增多），直到最后增量为1（d1>d2>...>dt=1）,所有记录放为一组，再整体进行一次直接插入排序。

　2、交换排序：每次比较两个待排序的记录，如果发现他们关键字的次序与排序要求相反时就交换两者的位置，直到没有反序的记录为止。

　（1）冒泡排序：设想排序表R[1]到R[n]垂直放置，将每个记录R[i]看作是重量为R[i].key的气泡；根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡违反本原则的轻气泡，就使其向上“漂浮”，如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。

　（2）快速排序：在待排序的n个记录中任取一个作为“基准”，将其与记录分为两组，第一组中个记录的键值均小于或等于基准的键值，第二组中个记录的键值均大于或等于基准的键值，而基准就排在这两组中间（这也是该记录的最终位置），这称为一趟快速排序（或一次划分）。对所分成的两组重复上述方法，直到所有记录都排在适当位置为止。

　3、选择排序：每次从待排序的记录中选出关键字最小（或最大）的记录，顺序放在已排好序的子序列的后面（或最前），直到全部记录排序完毕。

　（1）直接选择排序：首先，所有记录组成初始无序区R[1]到R[n]，从中选出键值最小的记录，与无序区第一个记录R[1]交换；新的无序区为R[2]到R[n]，从中再选出键值最小的记录，与无序区第一个记录R[2]交换；类似，第i趟排序时R[1]到R[i-1]是有序区，无序区为R[i]到R[n]，从中选出键值最小的记录，将它与无序区第一个记录R[i]交换，R[1]到R[i]变为新的有序区。因为每趟排序都使有序区中增加一个记录，所以，进行n-1趟排序后，整个排序表就全部有序了。

　（2）堆排序：利用小根堆（或大根堆）来选取当前无序区中关键字最小（或最大）的记录来实现排序的。下面介绍利用大根堆来排序。首先，将初始无序区调整为一个大根堆，输出关键字最大的堆顶记录后，将剩下的n-1个记录在重建为堆，于是便得到次小值。如此反复执行，知道全部元素输出完，从而得到一个有序序列。

　4、并归排序：指将若干个已排序的子表合成一个有序表。

　（1）二路并归排序：开始时，将排序表R[1]到R[n]看成n个长度为1的有序子表，把这些子表两两并归，便得到n/2个有序的子表（当n为奇数时，并归后仍是有一个长度为1的子表）；然后，再把这n/2个有序的子表两两并归，如此反复，直到最后得到一个程度为n的有序表为止。

　各种排序实验结果：

　CPU

　(英特尔)Intel(R) Core(TM) i5 CPU M 480 2.67GHz

　xx

　存

　4.00 GB (金士顿 PC3-10600 DDR3 1333MHz)

　学号

　xxxxxxxxxx

　主板

　宏碁 JE40_CP

　班级

　10电信1班

　操作系统

　Microsoft Windows 7 旗舰版 (64位/Service Pack 1)

　xxxxxxxxxxxxx

　编译软件

　Visual C++ 6.0

　email

　609803959qq.

　10^4

　2*10^4

　10^5

　2*10^5

　10^6

　2*10^6

　10^7

　2*10^7

　10^8

　10^5

　正序

　逆序

　直接插入

　(带监视哨）

　C

　24.874

　100.158

　2500.3

　9995.6

　0.099999

　5000.05

　t(时间)

　0.156

　0.546

　13.391

　53.417

　>5min

　0

　27.486

　直接插入

　(无监视哨）

　C

　24.874

　100.158

　2500.3

　9995.6

　0.099999

　4999.95

　t

　0.156

　0.578

　14.21

　56.715

　>5min

　0

　29.137

　希尔排序

　(无监视哨)

　C

　0.261664

　0.598651

　4.29106

　9.60946

　70.5165

　166.929

　1084.56

　2461.37

　17159.6

　1.50001

　2.24458

　t

　0.015

　0.016

　0.047

　0.109

　0.717

　1.591

　11.544

　27.735

　208.722

　0.02

　0.02

　直接选择

　C

　0

　0

　0

　0

　0

　0

　t

　0.218

　0.78

　19.367

　77.32

　>5min

　19.751

　20.249

　冒泡(上升)

　C

　49.9905

　199.985

　4999.94

　19999.9

　0.099999

　4999.95

　t

　0.452

　1.825

　45.542

　182.678

　>5min

　0

　47.326

　冒泡(下沉）

　C

　49.9904

　199.96

　4999.78

　19999.9

　0.099999

　4999.95

　t

　0.483

　1.902

　47.239

　189.081

　>5min

　0

　47.503

　快速(递归)

　C

　0.170775

　0.361618

　2.17042

　4.79646

　25.8125

　57.6668

　320.86

　647.454

　3493.6

　2201.3

　2201.4

　t

　0.01

　0.01

　0.031

　0.062

　0.219

　0.484

　2.577

　5.297

　29.377

　18.026

　18.195

　堆排序

　(非递归)

　C

　0.235479

　0.510793

　3.01938

　6.43895

　36.7932

　77.5876

　434.639

　909.281

　5012.88

　3.11252

　2.92664

　t

　0.016

　0.016

　0.047

　0.094

　0.499

　0.968

　7.223

　17.093

　123.429

　0.04

　0.05

　堆排序

　(递归)

　C

　0.235479

　0.510793

　3.01938

　6.43895

　36.7932

　77.5876

　434.639

　909.281

　5012.88

　3.11252

　2.92664

　t

　0

　0.015

　0.078

　0.125

　0.903

　1.825

　13.659

　31.742

　235.346

　0.06

　0.07

　二路归并

　(非递归)

　C

　0.123676

　0.267361

　1.56651

　3.33305

　18.7166

　39.4319

　224.002

　468.006

　2540.15

　0.877986

　0.815024

　t

　0

　0.015

　0.046

　0.062

　0.25

　0.546

　3.017

　6.457

　35.309

　0.03

　0.03

　实验结果原因分析和结论：

　1. 插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。反而在这种情况下，快速排序反而慢了。

　当n较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。

　若待排序的记录的关键字在一个明显有限围时,且空间允许是用桶排序。

　当n较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。

　当n较大时，关键字元素可能出现本身是有序的，对稳定性有要求时，空间允许的情况下。宜用归并排序。

　当n较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序。

　2.插入排序、冒泡排序、选择排序的时间复杂性为O(n2)

　?其它非线形排序的时间复杂性为O(nlog2n)

　?线形排序的时间复杂性为O(n);

　3.在算法运行期间，运行QQ软件、360安全卫士、360杀毒、word文档、ppt、酷狗等软件会影响绝对时间和逻辑时间，使时间增大

　4.随着n的取值增大，算法的实际时间增长速度逐渐增大。

　5.直接插入排序（有、无监视哨）、冒泡排序（上升、下沉）、堆排序（递归、非递归）的关键字比较次数相同，但绝对时间相差比较大；直接选择排序与冒泡排序的关键字比较次数相近。

　6.相比较其他同学的数据，直接插入（有、无监视哨），直接选择，冒泡（上升、下沉）的结果相差较小，希尔选择结果相差很大，另快速（递归），堆（递归，非递归），二路归并（非递归）结果并不会受计算机环境而不同。

　附录：源程序极其代码

　#define CPP C++

　#define MPP M++

　#define MP2 M+=2

　#define MP3 M+=3

　#include <fstream.h>

　#include <iomanip.h>

　#include <stdlib.h>

　#include <time.h>

　#include <math.h>

　const int maxsize=20000; //排序表容量

　typedef int datatype;

　typedef struct {

　 datatype key; //关键字域

　// othertype other; //其它域

　} rectype; //记录类型

　typedef rectype list[maxsize+2]; //排序表类型，0号单元不用

　__int64 C,M; //比较和移动次数

　void check(list R,int n) { //检验排序结果

　 int i;

　 for(i=2;i<=n;i++)

　 if(R[i].key<R[i-1].key) {cout<<"Error!\n";return;}

　 cout<<"Correct! ";

　}

　void disp(list R,int n) { //显示排序后的结果

　 int i;

　 for(i=1;i<=n;i++) {

　 cout<<setw(4)<<R[i].key<<" ";

　// if(i%20==0) cout<<endl;

　 }

　 cout<<endl;

　}

　void InsertSort1(list R,int n) {//直接插入排序，带监视哨(并不改变关键字次数)

　 int i,j;

　 for(i=2;i<=n;i++) { //依次插入R[2],R[3],…,R[n]

　 if(CPP,R[i].key>=R[i-1].key) continue;

　 //R[i]大于有序区最后一个记录，则本趟不需插入

　 MPP,R[0]=R[i]; //R[0]是监视哨

　 j=i-1;

　 do { //查找R[i]的插入位置

　 MPP,R[j+1]=R[j];j--; //记录后移，继续向前搜索

　 } while(CPP,R[0].key<R[j].key);

　 MPP,R[j+1]=R[0]; //插入R[i]

　 }

　}

　void InsertSort2(list R,int n) {//直接插入排序，无监视哨

　 int i,j;rectype x; //x为辅助量(用R[0]代替时间变长)

　 for(i=2;i<=n;i++) { //进行n-1次插入

　 if(CPP,R[i].key>=R[i-1].key) continue;

　 MPP,x=R[i]; //待排记录暂存到x

　 j=i-1;

　 do { //顺序比较和移动

　 MPP,R[j+1]=R[j];j--;

　 } while(j>=1 && (CPP,x.key<R[j].key));

　 MPP,R[j+1]=x; //插入R[i]

　 }

　}

　void ShellSort1(list R,int n){//一趟插入排序，h为本趟增量

　 int h,i,j,k;

　 for(h=n/2;h>=1;h=h/2){

　 for(i=1;i<=h;i++){ //i为组号

　 for(j=i+h;j<=n;j+=h){ //每组从第2个记录开始插入

　 if(CPP,R[j].key>=R[j-h].key) continue;//R[j]大于有序区最后一个记录，

　 //则不需要插入

　 MPP,R[0]=R[j]; //R[0]保存待插入记录，但不是监视哨

　 k=j-h; //待插记录的前一个记录

　 do{ //查找正确的插入位置

　 MPP,R[k+h]=R[k];k=k-h;//后移记录，继续向前搜索

　 }while(k>0&&(CPP,R[0].key<R[k].key));

　 MPP,R[k+h]=R[0]; //插入R[j]

　 }

　 }

　 if(h==1) break;

　 }

　}

　void SelectSort1(list R,int n){

　 int i,j,k;

　 for(i=1;i<=n-1;i++){//n-1趟排序

　 k=i;

　 for(j=i+1;j<=n;j++)//在当前无序区从前向后找键值最小的记录R[k]

　 if(R[j].key<R[k].key) k=j;

　 if(k!=i){R[0]=R[i];R[i]=R[k];R[k]=R[0];}//交换R[i]和R[0]，R[0]作辅助量

　 }

　}

　void BubbleSort1(list R,int n) {//上升法冒泡排序

　 int i,j,flag;rectype x; //x为辅助量(可用R[0]代替)

　 for(i=1;i<=n-1;i++) { //做n-1趟扫描

　 flag=0; //置未交换标志

　 for(j=n;j>=i+1;j--) //从下向上扫描

　 if(CPP,R[j].key<R[j-1].key) { //交换记录

　 flag=1;

　 MP3,x=R[j];R[j]=R[j-1];R[j-1]=x;//交换

　 }

　 if(!flag) break; //本趟未交换过记录，排序结束

　 }

　}

　void BubbleSort2(list R,int n) {//下沉法，冒泡排序

　 int i,j,flag;rectype x; //x为辅助量(可用R[0]代替)

　 for(i=1;i<=n-1;i++) { //做n-1趟扫描

　 flag=0; //置未交换标志

　 for(j=1;j<=n-i;j++) //从上向下扫描

　 if(CPP,R[j].key>R[j+1].key) {//交换记录

　 flag=1;

　 MP3,x=R[j];R[j]=R[j+1];R[j+1]=x;//交换

　 }

　 if(!flag) break; //本趟未交换过记录，排序结束

　 }

　}

　int Partition(list R,int p,int q) {//对R[p]到R[q]划分，返回基准位置

　 int i,j;rectype x; //辅助量(可用R[0]代替)

　 i=p;j=q;MPP,x=R[p]; //x存基准(无序区第一个记录)

　 do {

　 while((CPP,R[j].key>=x.key) && i<j) j--;//从右向左扫描(取消=变快)

　 if(i<j) {MPP,R[i]=R[j];i++;} //交换R[i]和R[j]

　 while((CPP,R[i].key<=x.key) && i<j) i++;//从左向右扫描

　 if(i<j) {MPP,R[j]=R[i];j--;} //交换R[i]和R[j]

　 } while(i<j);

　 MPP,R[i]=x; //基准移到最终位置

　 return i; //最后i=j

　}

　void QuickSort1(list R,int s,int t) {//对R[s]到R[t]快速排序，递归算法m

　 int i;

　 if(s>=t) return; //只有一个记录或无记录时无需排序

　 i=Partition(R,s,t); //对R[s]到R[t]做划分

　 QuickSort1(R,s,i-1); //递归处理左区间

　 QuickSort1(R,i+1,t); //递归处理右区间

　}

　void Sift1(list R,int p,int q){ //堆围为R[p]~R[q],调整R[p]为堆，非递归算法

　int j;

　MPP,R[0]=R[p]; //R[0]作辅助量

　j=2*p; //j指向R[p]的左孩子

　while(j<=q){

　if(j<q && (CPP,R[j].key<R[j+1].key)) j++; //j指向R[p]的右孩子

　if(CPP,R[0].key>=R[j].key) break; //根结点键值大于孩子结点，已经是堆，调整结束

　MPP,R[p]=R[j]; //将R[j]换到双亲位置上

　p=j; //修改当前被调整结点

　j=2*p; //j指向R[p]的左孩子

　}

　MPP,R[p]=R[0]; //原根结点放入正确位置

　}

　void Sift2(list R,int p,int q){ //堆围为R[p]~R[q],调整R[p]为堆，递归算法

　int j;

　if(p>=q) return; //只有一个元素或无元素

　j=2*p;

　if(j>q) return;

　if(j<q && (CPP,R[j].key<R[j+1].key)) j++; //j指向R[p]的右孩子

　if(CPP,R[p].key>=R[j].key) return; //根结点关键字已最大

　MPP,R[0]=R[j]; //交换R[j]和R[p]，R[0]作辅助量

　MPP,R[j]=R[p];

　MPP,R[p]=R[0];

　Sift2(R,j,q); //递归

　}

　void HeadSort1(list R,int n){ //堆R[1]到R[n]进行堆排序

　int i;

　for(i=n/2;i>=1;i--) Sift1(R,i,n); //建初始堆

　for(i=n;i>=2;i--){ //进行n-1趟堆排序

　MPP,R[0]=R[1]; //堆顶和当前堆底交换，R[0]作辅助量

　MPP,R[1]=R[i];

　MPP,R[i]=R[0];

　Sift1(R,1,i-1); //R[1]到R[i-1]重建成新堆

　}

　}

　void HeadSort2(list R,int n){ //堆R[1]到R[n]进行堆排序

　int i;

　for(i=n/2;i>=1;i--) Sift2(R,i,n); //建初始堆

　for(i=n;i>=2;i--){ //进行n-1趟堆排序

　MPP,R[0]=R[1]; //堆顶和当前堆底交换，R[0]作辅助量

　MPP,R[1]=R[i];

　MPP,R[i]=R[0];

　Sift2(R,1,i-1); //R[1]到R[i-1]重建成新堆

　}

　}

　void Merge(list R,list R1,int low,int mid,int high) {

　//合并R的两个子表：R[low]~R[mid]、R[mid+1]~R[high]，结果在R1中

　 int i,j,k;

　 i=low;

　 j=mid+1;

　 k=low;

　 while(i<=mid && j<=high)

　 if(CPP,R[i].key<=R[j].key) MPP,R1[k++]=R[i++]; //取小者复制

　 else MPP,R1[k++]=R[j++];

　 while(i<=mid) MPP,R1[k++]=R[i++]; //复制左子表的剩余记录

　 while(j<=high) MPP,R1[k++]=R[j++]; //复制右子表的剩余记录

　}

　void MergePass(list R,list R1,int n,int len) {//对R做一趟归并，结果在R1中

　 int i,j;

　 i=1; //i指向第一对子表的起始点

　 while(i+2*len-1<=n) { //归并长度为len的两个子表

　 Merge(R,R1,i,i+len-1,i+2*len-1);

　 i=i+2*len; //i指向下一对子表起始点

　 }

　 if(i+len-1<n) //剩下两个子表，其中一个长度小于len

　 Merge(R,R1,i,i+len-1,n);

　 else //子表个数为奇数,剩一段

　 for(j=i;j<=n;j++) //将最后一个子表复制到R1中

　 MPP,R1[j]=R[j];

　}

　void MergeSort(list R,list R1,int n) {//对R二路归并排序，结果在R中(非递归算法)

　 int len;

　 len=1;

　 while(len<n) {

　 MergePass(R,R1,n,len);len=len*2; //一趟归并，结果在R1中

　 MergePass(R1,R,n,len);len=len*2; //再次归并，结果在R中

　 }

　}

　int random1(int num) {return rand();} //0~RAND_MAX=32767

　int random3(int num) {//素数模乘同余法,0~M

　 int A=16807; // 16807764261123,630360016 48271?

　 int M=2147483647; //有符号4字节最大素数,2^31-1

　 int Q=M/A;

　 int R=M%A;

　 static int x=1,n=0,g=0; //seed(set to 1)

　 static double r,r1=0,r2=0;

　 int x1;

　 x1=A*(x%Q)-R*(x/Q);

　 if(x1>=0) x=x1;

　 else x=x1+M;

　 r=1.*x/M;if(r>0.5) g++;

　 n++;r1+=r;r2+=r*r;

　 if(n%maxsize==0) {

　 cout<<"x="<<r<<" "<<g<<" "<<"n="<<n<<" "<<r1/n<<" "<<r2/n<<" "<<(r2-r1)/n+.25<<endl;

　 }

　 return x;

　}

　void main() {

　 rectype *R,*R1,*S; //R1用于归并排序的辅助存储，S用于保存初始排序数据

　 R=new list;if(R==NULL) {cout<<"数组太大!\n";exit(-1);}

　 R1=new list;if(R1==NULL) {cout<<"数组太大!\n";exit(-1);}

　 S=new list;if(S==NULL) {cout<<"数组太大!\n";exit(-1);}

　 int i,n=maxsize;

　 int choice;

　 clock_t t1,t2;

　 // float s,t;

　 // 正序序列

　 // for(i=1;i<=n;i++)

　 // S[i].key=i;

　 //反序序列

　 // for(i=1;i<=n;i++)

　 // S[i].key=n-i+1;

　 // srand( (unsigned)time( NULL ) );

　 for(i=1;i<=n;i++)

　 S[i].key=random3(n); //生成0-n之间的随机数

　 do {

　 C=M=0;

　 for(i=1;i<=n;i++)

　 R[i].key=S[i].key; //取出初始数据用于排序

　 cout<<"选择排序方法(0: 退出): \n\

　 11：直接插入(带监视哨) 12：直接插入(无监视哨) \n\

　 21：希尔排序(无监视哨) \n\

　 31：直接选择 \n\

　 41：冒泡(上升) 42：冒泡(下沉） \n\

　 51：快速(递归) \n\

　 61：堆排序(非递归) 62:堆排序(递归) \n\

　 71：二路归并(非递归) \n";

　 cin>>choice;

　 switch(choice) {

　 case 11:

　 t1=clock();

　 InsertSort1(R,n);

　 t2=clock();

　 break;

　 case 12:

　 t1=clock();

　 InsertSort2(R,n);

　 t2=clock();

　 break;

　 case 21:

　 t1=clock();

　 ShellSort1(R,n);

　 t2=clock();

　 break;

　 case 31:

　 t1=clock();

　 SelectSort1(R,n);

　 t2=clock();

　 break;

　 case 41:

　 t1=clock();

　 BubbleSort1(R,n);

　 t2=clock();

　 break;

　 case 42:

　 t1=clock();

　 BubbleSort2(R,n);

　 t2=clock();

　 break;

　 case 51:

　 t1=clock();

　 QuickSort1(R,1,n);

　 t2=clock();

　 break;

　 case 61:

　 t1=clock();

　 HeadSort1(R,n);

　 t2=clock();

　 break;

　 case 62:

　 t1=clock();

　 HeadSort2(R,n);

　 t2=clock();

　 break;

　 case 71:

　 t1=clock();

　 MergeSort(R,R1,n);

　 t2=clock();

　 break;

　 default:;

　 }

　 check(R,n);

　 //disp(R,n);

　 cout<<" C="<<C/1e6<<" M="<<M/1e6<<" C+M="<<(C+M)/1e6;

　 cout<<" 时间："<<float(t2-t1)/CLK_TCK<<endl;

　 } while(choice!=0);

　 delete R;delete S;

　// delete R1;

　}