北邮数据结构实验报告实验四排序含源码

北京邮电大学信息与通信工程学院

//插入排序

void InsertSort(int r[], int n) { int move=0, compare=0; long double start=0,end=0,time=0; start=GetNowTime(); for(i=2;i

cout<

//希尔排序

void ShellSort(int r[], int n) { int move=0,compare=0; long double start=0,end=0,time=0; start=start=GetNowTime(); int d; //定义增量

for(d=n/2;d>=1;d=d/2) //以增量为d进行直接插入排序 { for(i=d+1;i0&&r[0]

第9页

北京邮电大学信息与通信工程学院

compare++; } } end=GetNowTime(); time=end-start; for(i=1;i

cout<<\排序所需时间：\移动次数：\ 比较次数：\

cout<

//改进型起泡排序

void BubbleSort(int r[], int n) { long double start=0,end=0,time=0; int move=0,compare=0; int exchange; int bound;

exchange=n-1; //第一趟起泡排序的范围是r[0]到r[n-1] start=GetNowTime(); while (exchange) //仅当上一趟排序有记录交换才进行本趟排序

{ bound=exchange; //表示无序的范围 exchange=0; for(int j=0;jr[j+1]) { temp=r[j]; //交换r[i]和r[i+1] r[j]=r[j+1]; r[j+1]=temp; move=move+3; exchange=j; //记录每一次发生记录交换的位置，即记录无序区的位置

} compare++; } end=GetNowTime(); time=end-start; for(int i=0;i

cout<

cout<<\排序所需时间：%us 移动次数：\ 比较次数：

第10页

北京邮电大学信息与通信工程学院

\

cout<

//快速排序一次划分

int Emove=0,Ecompare=0; long double Etime;

int Partition(int r[], int first, int end) { i=first; //初始化 j=end;

while (i

while(i

while(i

Ecompare++; if(i

//快速排序，在一次排序结束后，左边区的元素都比右边区的小，只要分开再排序即可 void QuickSort(int r[],int first,int end2)

第11页

北京邮电大学信息与通信工程学院

{

long double start=0,end=0; start=GetNowTime(); if (first

QuickSort(r,first,pivot-1); //递归地对左侧子序列进行快速排序 QuickSort(r,pivot+1,end2); //递归地对右侧子序列进行快速排序 } end=GetNowTime(); Etime=end-start; }

void Print() { cout<

}

//简单选择排序,每一趟都找到最小值与比较域内第一个值交换 void SelectSort(int r[], int n) { long double start=0,end=0,time=0; int compare=0,move=0; int index; //设置关键值下标 start=GetNowTime();

for(i=0;i

cout<

第12页