北邮数据结构实验 第三次实验 排序

数据结构实验报告

1．实验要求 (1)实验目的

通过选择下面两个题目之一，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。 (2)实验内容

使用简单数组实现下面各种排序算法，并进行比较。 排序算法：

1、插入排序 2、希尔排序

3、冒泡排序 4、快速排序 5、简单选择排序 6、堆排序（选作） 7、归并排序（选作） 8、基数排序（选作） 9、其他

要求： 1、测试数据分成三类：正序、逆序、随机数据

2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。

3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）

4、对2和3的结果进行分析，验证上述各种算法的时间复杂度

编写测试main()函数测试排序算法的正确性。

2. 程序分析 2.1 存储结构 顺序表: 示意图：

a0 a1 a2 a3 a4 a5 a6 a7

2.2 关键算法分析

（1） 测试数据的产生：正序、逆序、随机数据 用两个数组实现乱序、顺序以及逆序数据的排序。

基本思想为：随机序列产生一个指定长度的乱序序列，然后通过memcpy()函数拷贝到第

第1页

二个数组里，第二个数组作为乱序序列的保存数组，每次对第一个数组进行排序，之后拷贝第二个数组中的乱序序列到第一个数组，实现各次乱序排列。只要算法正确（第一步可以检验），之后顺序排列只需反复对第一个数组进行操作即可，再后用第二个数组保存逆序数组，然后同样在每次排序之后复制第二数组存储的乱序序列到第一组，对第一组反复排序即可。 <1> pRandom1=new long int[Max+1];pRandom2=new long int[Max+1];

<2> srand((unsigned)time(NULL)); for(int i = 1; i <= Max;i++ ) pRandom2[i]=rand(); <3> memcpy(obj.pRandom1,obj.pRandom2,(Max+1)*sizeof(long int));

（2） 排序算法：

<1>插入排序：依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕。

/1/int j=0;

/2/ for(int i =2; i <= Max;i++) parray[0]=parray[i];comparetimes[0]++;

/4/parray[j+1]=parray[0];movetimes[0]+=2; 示意图：

r1,r2,r3,…,ri-1,ri,ri+1,…,rn

有序区 待插入 无序区

<2>希尔排序：先将整个序列分割成若干个子列，分别在各个子列中运用直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。

int Sort::ShellSort(long int parray[]) {int j=0;

for(int d=Max/2;d>=1;d/=2) {for(int i=d+1;i<=Max;i++)

{ parray[0]=parray[i];

comparetimes[1]++;

for(j=i-d;j>0 && parray[0]

movetimes[1]++;} parray[j+d]=parray[0]; movetimes[1]+=2;}}

return 0;}

<3>冒泡排序：两两比较相邻记录的关键码，如果反序则交换，直到没有反序记录为止。

int Sort::BubbleSort(long int parray[])

第2页

{ int exchange=Max;

int bound,j; while(exchange) { bound=exchange;

exchange=0;

for(j=1;j

if(parray[j]>parray[j+1]) { parray[0]=parray[j];

parray[j]=parray[j+1]; parray[j+1]=parray[0]; exchange=j;

movetimes[2]+=3;}}}

return 0;}

示意图：

r1,r2,r3,…,ri-1,ri,ri+1,…,rn

反序则交换 有序区

<4>快速排序：首先选择一个基准，将记录分割为两部分，左支小于或等于基准，右支则大于基准，然后对两部分重复上述过程，直至整个序列排序完成。

int Sort::QuickSort(long int parray[])

{QuickSortRecursion(parray,1, Max);return 0;}

int Sort::QuickSortRecursion(long int parray[], int first=1, int end=Max) {if (first

{ int pivot=QuickSortPatition(parray, first, end);

QuickSortRecursion(parray, first, pivot-1);//左侧子序列排序 QuickSortRecursion(parray, pivot+1, end); //右侧子序列排序 } return 0;}

int Sort::QuickSortPatition(long int r[], int first, int end ) {int i=first;int j=end; int temp; while (i

{ while (i

comparetimes[3]++; } //右侧扫描 if (i

{ temp=r[i]; //将较小记录交换到前面 r[i]=r[j]; r[j]=temp; i++;

movetimes[3]+=3; }

第3页

while (i

i++;

comparetimes[3]++;

} //左侧扫描 if (i

temp=r[j]; r[j]=r[i];

r[i]=temp; //将较大记录交换到后面 j--;

movetimes[3]+=3; } }

return i; //i为轴值记录的最终位置

示意图：

r1,r2,r3,…,ri-1,ri,ri+1,…,rn

rri

<5>选择排序：从待排序的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第一个记录交换位置；然后从不包括第一个位置上的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第二个记录交换位置；如此重复，直到序列中只剩下一个记录为止。

int Sort::SelectSort(long int parray[]) {

int i,j,index,temp;

for (i=1; i

index=i;

for (j=i+1; j<=Max; j++) {

comparetimes[4]++; //在无序区中选取最小记录 if (parray[j]

if (index!=i) {

temp=parray[i];

parray[i]=parray[index]; parray[index]=temp; movetimes[4]+=3; } }

第4页