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

示意图：

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

反序则交换 有序区

<6>堆排序：通过建立大根堆或者小根堆，取出根节点，反复调整堆使之保持大根堆或者小根堆，直至最后序列有序。

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

int i;

for (i=Max/2; i>=1; i--)

HeapSortSift(parray, i, Max) ; for (i=1; i

parray[0]=parray[Max-i+1]; parray[Max-i+1]=parray[1]; parray[1]=parray[0]; movetimes[5]+=3;

HeapSortSift(parray, 1, Max-i); }

return 0; }

void Sort::HeapSortSift(long int parray[], int k, int m) {

int i,j; i=k;

j=2*i; //置i为要筛的结点，j为i的左孩子 while (j<=m) //筛选还没有进行到叶子 {

if (j

j++;

comparetimes[5]++;

} //比较i的左右孩子，j为较大者 if (parray[i]>parray[j]) {

comparetimes[5]++; break;

} //根结点已经大于左右孩子中的较大者 else

第5页

{

parray[0]=parray[i]; parray[i]=parray[j]; parray[j]=parray[0]; movetimes[5]+=3; i=j;

j=2*i; //被筛结点位于原来结点j的位置

<7>归并排序：将若干个有序序列两两归并，直至所有待排序的记录都在一个有序序列为止。

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

long int r1[Max+1]; int h(1);

while (h

MergePass(parray, r1, h); //归并 h=2*h;

MergePass(r1, parray, h); h=2*h; }

return 0; }

void Sort::Merge(long int parray[], long int r1[], int s, int m, int t) //一次归并 {

int i=s; int j=m+1; int k=s;

while (i<=m && j<=t) {

comparetimes[6]++; movetimes[6]++;

if (parray[i]<=parray[j]) {

r1[k++]=parray[i++]; } else

r1[k++]=parray[j++]; }

if (i<=m)

第6页

while (i<=m) {

r1[k++]=parray[i++]; movetimes[6]++; } else

while (j<=t) {

r1[k++]=parray[j++]; movetimes[6]++; } }

void Sort::MergePass(long int parray[], long int r1[], int h) //一趟归并 {

int i(1),k;

while (i<=Max-2*h+1) {

Merge(parray, r1, i, i+h-1, i+2*h-1); i+=2*h; }

if (i

Merge(parray, r1, i, i+h-1, Max); else for (k=i; k<=Max; k++) {

r1[k]=parray[k]; movetimes[6]++;

（3）比较上述排序算法中关键字的比较次数和移动次数：

使用函数指针数组，分别指向各排序函数的入口地址，然后在Statistics()函数中加以调用，使得排序函数运行在统计时间函数之间，这样使用一个for语句即可实现算法的一次性调用、时间统计、移动次数和比较次数统计。 void Statistics(Sort &obj,int i,int j)

{

obj.startTime=obj.GetNowTime(); (obj.*pFunction[i])(obj.pRandom1); obj.endTime=obj.GetNowTime();

obj.runtime[i][j]=obj.endTime-obj.startTime;

}

建立两个数组分别统计运行次数，再统一使用一个数组记录七种算法在三种不同数据情况下的移动次数和交换次数。在分别运行乱序、顺序和逆序数组排序时取出前两个数组的值写入第三个数组，然后置零继续统计。

(4)算法的执行时间：

第7页

获取当前系统时间，精确到微秒，分别在代码运行前后调用记录前后时间，再相减即可得到代码运行时间。此处调用函数QueryPerformanceCounter()用于得到高精度计时器的值。

long double Sort::GetNowT33ime() {

LARGE_INTEGER litmp; LONG64 QPart;

QueryPerformanceCounter(&litmp); QPart=litmp.QuadPart;

return (long double)QPart;

（5）各种算法的时间复杂度与空间复杂度：

排序方法 直接插入排序 希尔排序 起泡排序 快速排序 简单选择排序 堆排序 归并排序

3. 程序运行结果 （1）流程图：

平均情况 最好情况 最坏情况 辅助空间 O(n2) O(nlog2n)~O(n2) O(n2) O(nlog2n) O(n2) O(nlog2n) O(nlog2n) O(n) O(n1.3) O (n) O(nlog2n) O(n2) O(nlog2n) O(nlog2n) O(n2) O(n2) O(n2) O(n2) O(n2) O (nlog2n) O(nlog2n) O(1) O(1) O(1) O(log2n) ~O(n) O(1) O(1) O(n)

开始 产生随机数组 乱序数组七种排序和统计 顺序数组七种排序和统计 第8页