1概要

1.1设计目的

数据结构与算法课程主要是研究非数值计算的程序设计问题中所出现的

计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。学习数据结构与算法是为了将实际问题中涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。

1）本演示程序对以下6种常用的内部排序算法进行实测比较：冒泡排序，直接插入排序，简单选择排序，快速排序，希尔排序，堆排序；

2）待排序表的元素的关键字为整数。比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换记为3次移动）；

3）演示程序以以用户和计算机的对话方式执行，在计算机终端上显示提示信息，对随机数组进行排序，并输出比较指标值；

4）最后对结果作出简单分析。

1.2预期目标

按要求输入不同的操作。输入后，根据不同的输入进行不同的操作，最终达到对各算法进行比较的目的。通过此次课程设计主要达到以下目的了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。

- 5 - 5

2排序算法

2.1各排序算法的特点

1）冒泡排序

冒泡排序的基本概念是：依次比较相邻的两个数，将大数放在前面，小数放在后面。即首先比较第1个和第2个数，将大数放前，小数放后。然后比较第2个数和第3个数，将大数放前，小数放后，如此继续，直至比较最后两个数，将大数放前，小数放后，此时第一趟结束，在最后的数必是所有数中的最小数。重复以上过程，仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再大于第2个数），将大数放前，小数放后，一直比较到最小数前的一对相邻数，将大数放前，小数放后，第二趟结束，在倒数第二个数中得到一个新的最小数。如此下去，直至最终完成排序。由于在排序过程中总是大数往前放，小数往后放，相当于气泡往上升，所以称作冒泡排序。

2）直接插入排序

每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从后向前扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。

3）简单选择排序

（1）在一组元素V[i]~V[n-1]中选择具有最小排序码的元素（2）若它不是这组元素中的第个元素，则将它与这一组元素中的第一个元素对调；（3）在这组元素中剔除这个具有最小排序码的元素，在剩下的元素V[i+1]~V[n-1]中重复执行第（1）（2）步，直到剩余元素只有一个为止。 4）快速排序

首先检查数据列表中的数据数，如果小于两个，则直接退出程序。如果有超过两个以上的数据，就选择一个分割点将数据分成两个部分，小于分割点的数据放在一组，其余的放在另一组，然后分别对两组数据排序； 5） 希尔排序

先取一个正整数d1

- 6 -

6

堆排序是一树形选择排序，在排序过程中，将R[1..N]看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素；堆的定义: N个元素的序列K1，K2，K3，...，Kn.称为堆，当且仅当该序列满足特性：Ki≤K2i Ki ≤K2i+1(1≤ I≤ [N/2])；

2.2各算法的比较方法

1.稳定性比较

插入排序、冒泡排序、简单选择排序及其他线形排序是稳定的 希尔排序、快速排序、堆排序是不稳定的 2.时间复杂性比较

插入排序、冒泡排序、选择排序的时间复杂性为O(n2) 其它非线形排序的时间复杂性为O(nlog2n) 线形排序的时间复杂性为O(n); 3.辅助空间的比较

线形排序的辅助空间为O(n),其它排序的辅助空间为O(1); 4.其它比较

插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。

反而在这种情况下，快速排序反而慢了。

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

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

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

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

- 7 -

7

3流程图及详细算法

3.1流程图

函数的调用关系图反映了演示程序的层次结构：

main strand BubbleSort InsertSort SelectSort QuickSort ShellSort HeapSor

InitLinkList RandomNuLT Display 图3.1 流程图

3.2流程图模块说明

1）Main为主函数模块

2）bubblesort，insertsort，selectsort，quicksort，shellsort，heansort分别对应冒泡排序，直接插入排序，简单选择排序，快速排序，希尔排序，堆排序的各函数模块

3）在初始化数据之后，选择对应的排序模块进行排序，并对排序做出比较

3.3可排序表的抽象数据类型定义：

typedef struct{ //定义一个RedType型结构体，存放关键字 int key; //关键字为整型 } RedType;

class LinkList //定义一个顺序表

- 8 -

8

{ public:

RedType r[MAXSIZE+1]; //长度为MAXSIZE+1的数组r，数组里每个元素均为RedType

int Length; //数组长度

int CmpNum, ChgNum; //关键字的比较次数，移动次数 LinkList(); //构造函数

bool LT(int i, int j); //比较i和j的大小 void Display(); //输出数组元素 void Insert( int dk); //插入排序 void ShellSort(); //希尔排序

int Partition( int low, int high); //比基准小的数放左边，比起大的数放右边，返回基准位置

void QSort( int low, int high); //从low到high位置进行快速排序 void QuickSort(); //对有序表进行快速排序 void HeapAdjust( int s, int m); //将无序堆调整为大顶堆 void HeapSort(); //堆排序，将大顶堆转换为小顶堆 void BubbleSort(); //冒泡排序

int SelectMinKey( int k); //找到数组中最小值，返回最小值位置 void SelSort(); //对顺序表进行选择排序 void SelectSort(); //界面设计

void AllAbove(); //统计以上所有排序关键字的比较次数、移动次数及所消耗的时间 };

3.4程序代码

3.4.1 函数声明

#include #include

- 9 -

9