排序综合数据结构课程设计论文.docx

理 学院 数学0902 班 学生 （16）马新月课程设计课题：16、综合排序：利用随机函数随机产生 N=200 个随机整数，对这些数进行多种方法的排序要求：1）至少采用三种方法实现上述问题求解（插入排序、希尔排序、冒泡排 序、快速排序、堆排序、归并排序）把排序后的结果存在不同的文 件中2）记录不同排序方法的运行时间，找出自己排序方法中最快的两种方法3）统计每种算法所用的比较次数和交换次数，以列表显示出来一、 课程设计工作日自 2012 年 乙月 21 日至 2012 年3 月」_日二、 同组学生： 马新月 三、 课程设计任务要求（包括课题来源、类型、目的和意义、基本要求、完成时间、主要参考资料等）：课题来源：教师提供课题类型：设计课程设计的目的1） 使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操 作实现算法，以及它们在程序中的使用方法2） 使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力3） 使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力天津职业技术师范大学课程设计评审表1 概要1.1 设计目的数据结构与算法课程主要是研究非数值计算的程序设计问题中所出现的 计算机操作对象以及它们之间的关系和操作的学科。

数据结构是介于数学、计算 机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、 数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、 系统工程等各种领域学习数据结构与算法是为了将实际问题中涉及的对象在计 算机中表示出来并对它们进行处理通过课程设计可以提高学生的思维能力，促 进学生的综合应用能力和专业素质的提高1）本演示程序对以下 6 种常用的内部排序算法进行实测比较：冒泡排序，直接插入排序，简单选择排序，快速排序，希尔排序，堆排序；2）待排序表的元素的关键字为整数比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换记为 3 次移动）；3）演示程序以以用户和计算机的对话方式执行，在计算机终端上显示提示信息，对随机数组进行排序，并输出比较指标值；4）最后对结果作出简单分析1.2 预期目标按要求输入不同的操作输入后，根据不同的输入进行不同的操作，最终达 到对各算法进行比较的目的通过此次课程设计主要达到以下目的了解并掌握数 据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发 过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用 所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开 发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。

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） 希尔排序先取一个正整数dlvn,把所有序号相隔dl的数组元素放一组，组内进行直 接插入排序；然后取d2vd1，重复上述分组和排序操作；直至di=1，即所有记录 放进一个组中排序为止；6） 堆排序堆排序是一树形选择排序，在排序过程中，将R[1..N]看成是一颗完全二叉 树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选 择最小的元素；堆的定义:N个元素的序列K1，K2，K3,…，Kn.称为堆，当且 仅当该序列满足特性：Ki

反而在这种情况下，快速排序反而慢了当n较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插 入或冒泡排序若待排序的记录的关键字在一个明显有限范围内时 , 且空间允许是用桶排 序当 n 较大时，关键字元素比较随机，对稳定性没要求宜用快速排序当 n 较大时，关键字元素可能出现本身是有序的，对稳定性有要求时，空间 允许的情况下，宜用归并排序当 n 较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用 堆排序3 流程图及详细算法3.1 流程图函数的调用关系图反映了演示程序的层次结构：图 3.1 流程图3.2 流程图模块说明1)Main 为主函数模块2)bubblesort，insertsort，selectsort，quicksort，shellsort，heansort 分别对应冒泡 排序，直接插入排序，简单选择排序，快速排序，希尔排序，堆排序的各函数模 块3)在初始化数据之后，选择对应的排序模块进行排序，并对排序做出比较3.3可排序表的抽象数据类型定义：typedef struct{// 定义一个 RedType 型结构体，存放关键字int key;} RedType;// 关键字为整型class LinkList// 定义一个顺序表public:RedType r[MAXSIZE+1];为 RedType//长度为MAXSIZE+1的数组r 数组里每个元素均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 #include #include #include #include #include #include #define MAXSIZE 1000#define TRUE 1#define FALSE 0typedef int BOOL;typedef struct{int key;} RedType;class LinkList{public:RedType r[MAXSIZE+1];int Length;int CmpNum, ChgNum;LinkList();bool LT(int i, int j);void Display();void Insert( int dk);void ShellSort();int Partition( int low, int high); void QSort( int low, int high); void QuickSort();void HeapAdjust( int s, int m);void HeapSort();void BubbleSort();int SelectMinKey( int k);void SelSort();void SelectSort();void AllAbove();};LinkList::LinkList(){int i;for (i = 0; i <= MAXSIZE; i++) r[i].key = rand()%1000;Length=MAXSIZE+1;CmpNum=0;ChgNum=0;}bool LinkList::LT(int i, int j){(CmpNum)++;if (i < j)return TRUE;elsereturn FALSE;void LinkList::Display(){int j;for(int i=0;i<=MAXSIZE;i++){ cout<