数据结构课程设计实验报告_内部排序算法比较.doc

数据结构课程设计

实验报告

内部排序算法比较

08 级计算机科学与技术专业

E10814131

郭磊

2010 年 06 月 13 日

【实验简介】

3、 用五组不同的长度不小于 100 的数据进行测试，并对测试结果作出简单

的分析，对得出结果拨动大小的进行解释；

【设计模块】

【对应模块算法说明】

(1) 此算法程序中需要用到顺序表数据类型,数据元素的类型定义如下:

typedef struct{

}RedType;

typedef struct{

下：

起泡排序：若待排序列为“正序”，则需进行一趟排序在排序过程中关键字需进行 n-1 次比

较，无须移动纪录；若是“逆序”，则进行 n-1 趟排序，需 n(n-1)/2 次比较，并坐等数量级

生成随机数 Switch 函数 菜单函数

SelectSortinsertSortBubbleSort

HeapSort

的移动，因此总的事件复杂度为 O（n

）;

直接插入排 序 待排序 纪录是随机的，关键字 间的移动次数和比 较次数的平均值约

为 n*n/4,即时间复杂度为 O（n

）;

简单的选择排序 虽然在排序过程中所需要的移动次数较少，最小时为 0，最大时为 3（n-

1 ）；但 是 关键 字 的比 较次 数 总是 相 同的 ，均 为 n(n-1)/2 ，因 此 ，时 间复 杂 度亦 为

O（n

快速排序 其平均时间是 kn*㏑n,其中 n 为待排序列中纪录的个数，k 为某个常数，其时

在最坏的情况下，其时间复杂度为 O（n*㏑n）；

① 冒泡排序 该算法的的思路是首先将第 1 个记录的关键字负值给 L.r[0]，然后用

L.r[0]与第（i+1）个记录的关键字比较,若为逆序,则交换第 i 与第 i+1 两记录的位置,然后

让 i 加 1，重复以上操作，直至 i=n-1 为止;依次进行第二趟、第三趟……作同样的操作，

直至所有的记录按正序排列（一般需要 n-1 趟比较，第 i 趟从 L.r[1]到 L.r[n-i+1]依次比

较，1≦ i ≦n-i，比较结果是让其中最大的记录放在 L.r[n-i+1]的位置）

void BubbleSort(Sqlist *L) //冒泡排序

{

L->r[0]=L->r[j+1]; //保证 L->r[0]始终为较大的记录

L->r[j+1]=L->r[0]; //把最大的记录放到祠堂排序的最高位置

}

② 直接插入排序 本算法的思路是，把 L->r[0]设置为哨兵，排序时把第 i 个记录复制给

哨兵，并于其前的 i-1 个记录进行比较，找到第一个比起大的记录，利用循环让记录后移 ，

{

if((L->r[i].key < L->r[i-1].key))

{

L->r[0] = L->r[i]; //复制哨兵

L->r[i] = L->r[i-1];

for(j=i-2;(L->r[0].key < L->r[j].key);j--)

L->r[j+1] = L->r[j]; //纪录后移

}

{

L->r[0]=L->r[k];

j=k;

}

if (i!=j)

L.r[i]←→L.r[j]; //与第 i 个记录交换

④ 快速查找排序 其基本思想为，通过一趟排序将带排序记录分割成两部分，其中一部

速排序。其中一趟快速排序的算法为：

int serchSort(Sqlist *L,int low,int high) //快速排序单次排序

{

while(low<high && L->r[high].key>=pivotkey) high--;

}

void QSort(Sqlist *L, int low, int high) // 快速排序

if (low < high)

{ // 长度大于 1

pivotloc = serchSort(L, low, high); //调用 serchSort（）将 L.r[low..high]一分为

二

if(L->r[i].key < L->r[i-dlta[k]].key)

{

L->r[0] = L->r[i];

for(j=i-dlta[k];j>0 && (L->r[0].key < L->r[j].key);j-=dlta[k])

L->r[j+dlta[k]] = L->r[j];

L->r[j+dlta[k]] = L->r[0];

⑥ 堆排序 基本思想是使记录序列按关键字非递减有序排列，则再对排序的算法中先建立

rc = L->r[s];

L->r[s] = L->r[j];

}

void HeapSort(Sqlist *L) //堆排序