数据结构课程设计(内部排序算法比较_C语言)

内部排序算法比较目录摘要 ......................................................................................... 错误！未定义书签。

1绪论 . (1)2系统分析 (1)2.1功能需求 (1)2.2数据需求 (1)2.3性能需求 (1)3总体设计 (1)3.1系统设计方案 (1)3.2功能模块设计 (2)4详细设计 (3)4.1数据结构定义 (3)4.2伪随机产生数据模块 (4)4.3简单选择排序模块 (5)4.4起泡排序模块 (6)4.5直接插入排序模块 (7)4.6希尔排序模块 (8)4.7快速排序模块 (9)4.8归并排序模块 (10)4.9条形图模块 (11)5调试与测试 (12)5.1调试 (12)5.2测试 .................................................................................. 错误！未定义书签。

6结论 .. (13)结束语 (13)参考文献 (14)附录1－用户手册 (15)附录2－源程序 (17)1绪论随着科技的快速发展，越来越多的企业不再浪费人力财力去计算一些统计性结果，而是应用一些简单的程序或系统来完成这些任务。

随着学习数据结构课程的深入，了解了不同排序算法的不同排序方法，每种排序对数据的比较次数、移动次数和排序用时都是不同的，本程序实现了六种内部排序算法的比较，并用条形图直观的显示出各种算法的优劣。

运用伪随机产生的数据，调用六种排序算法，记录其比较次数、移动次数和排序时间，再分别用条形图（星号表示）表示出来。

2系统分析2.1 功能需求(1)对起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、归并排序算法进行比较。

(2)待排序的元素的关键字为整数，其中数据要用伪随机产生程序产生，并且至少用5组的输入数据做比较，再使用各种算法对其进行排序，记录其排序时间，再汇总比较。

数据结构课程设计—内部排序算法比较在计算机科学领域中，数据的排序是一项非常基础且重要的操作。

内部排序算法作为其中的关键部分，对于提高程序的运行效率和数据处理能力起着至关重要的作用。

本次课程设计将对几种常见的内部排序算法进行比较和分析，包括冒泡排序、插入排序、选择排序、快速排序和归并排序。

冒泡排序是一种简单直观的排序算法。

它通过重复地走访要排序的数列，一次比较两个数据元素，如果顺序不对则进行交换，并一直重复这样的走访操作，直到没有要交换的数据元素为止。

这种算法的优点是易于理解和实现，但其效率较低，在处理大规模数据时性能不佳。

因为它在最坏情况下的时间复杂度为 O(n²)，平均时间复杂度也为O(n²)。

插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入，直到整个序列有序。

插入排序在数据量较小时表现较好，其平均时间复杂度和最坏情况时间复杂度也都是 O(n²)，但在某些情况下，它的性能可能会优于冒泡排序。

选择排序则是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。

以此类推，直到全部待排序的数据元素排完。

选择排序的时间复杂度同样为O(n²)，但它在某些情况下的交换操作次数可能会少于冒泡排序和插入排序。

快速排序是一种分治的排序算法。

它首先选择一个基准元素，将数列分成两部分，一部分的元素都比基准小，另一部分的元素都比基准大，然后对这两部分分别进行快速排序。

快速排序在平均情况下的时间复杂度为 O(nlogn)，最坏情况下的时间复杂度为 O(n²)。

然而，在实际应用中，快速排序通常表现出色，是一种非常高效的排序算法。

归并排序也是一种分治算法，它将待排序序列分成若干个子序列，每个子序列有序，然后将子序列合并成一个有序序列。

《数据结构与算法分析》课程设计教学任务书一、课程设计的目的数据结构与算法课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。

数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。

学习数据结构与算法是为了将实际问题中涉及的对象在计算机中表示出来并对它们进行处理。

通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。

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

二、课程设计的基本要求1. 独立思考，独立完成：课程设计中各任务的设计和调试要求独立完成，遇到问题可以讨论，但不可以拷贝。

2. 做好上机准备：每次上机前，要事先编制好准备调试的程序，认真想好调试步骤和有关环境的设置方法，准备好有关的文件。

3. 按照课程设计的具体要求建立功能模块，每个模块要求按照如下几个内容认真完成：a）需求分析：在该部分中叙述，每个模块的功能要求b）概要设计：在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义）c）详细设计：各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组程序，每个功能模块采用不同的函数实现）源程序要按照写程序的规则来编写。

要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释d）调试分析：测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是那些，问题如何解决？），算法的改进设想课程设计总结：（保存在word文档中）总结可以包括：课程设计过程的收获、遇到的问题、解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对《数据结构》课程的认识等内容4. 实现的结果必须进行检查和演示，程序源代码和程序的说明文件必须上交，作为考核内容的一部分。

数据结构课程设计题目：内部排序算法的比较姓名：李吉倩学号：020*********系年级：计算机科学与技术2010级完成时间：2012.8-2012.9实验报告一、需求分析1.本程序对以下六种常用的内部排序进行实测比较：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。

2.待排序表的元素的关键字为整数，雍正徐、逆序和随机数产生器产生的随机数做测试比较。

比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换记为3次移动）。

3.程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”下，用户可由键盘输入产生随机数的种子，计算机终端显示各内部排序的比较参数。

4.最终对结果做出简单分析，包括对各组数据得出结果波动大小给予解释。

二、概要设计1.可排序表的抽象数据类型定义：ADT OrderableList{数据对象：D = {ai |ai∈IntegerSet,i = 1,2,……,n,n >= 0}数据关系：R1 = {<ai-1,ai>|ai-1,ai∈D.i = 2,……,n}基本操作：SelectListType(c)操作结果：打印提示信息，请用户选择待排序表的类型，顺序型、逆序型还是随机数组。

BubbleSort(&L)操作结果：进行起泡排序，返回排序后的顺序表InsertSort(&L)操作结果：进行插入排序，返回排序后的顺序表SelectSort(&L)操作结果：进行选择排序，返回排序后的顺序表QuickSort(&L)操作结果：进行快速排序，返回排序后的顺序表ShellSort(&L)操作结果：进行希尔排序，返回排序后的顺序表HeapSort(&L)操作结果：进行堆排序，返回排序后的顺序表SelectSortMethod(&L,c1)操作结果：打印提示信息，请用户选择排序方法，起泡排序、插入排序、选择排序、快速排序、希尔排序还是堆排序OutPut(L)操作结果：打印排序中关键字的比较次数和移动次数}ADT OrderableList2.本程序包含两个模块：1）.主程序模块int mian(){初始化；用户选择待测表的类型；输入选择，用switch语句判断；While（“命令”！= “退出”）{接受命令；处理命令；}}２）．可排序表单元模块----实现可排序表的抽象数据类型各模块之间的调用关系：主程序模块可排序表单元模块三、详细设计1.根据题目要求何可排序表的基本操作特点，可排序表采用证书顺序表存储结构，并实现在头文件SqList.H。

《数据结构》课程设计报告排序算法的实现与比较设计内容及要求编程实现插入、希尔、快速、堆排序、归并排序算法，并计算每种算法的比较、交换次数。

将待排数据从磁盘文件读入，实施排序后将数据写入另一个文件中。

概述在本设计课题中，我们将对常见的5中排序算法——插入、希尔、快速、堆排序、归并排序进行各种情况下的比较，如待排数据为顺序、逆序或随机的情况下，各个算法对于特定数据的性能。

基于此点考虑，在程序中选择采用以毫秒为单位的执行时间来衡量算法对特定数据的性能高低。

本文将主要介绍《排序之谜》程序（以下简称“程序”）的数据结构的设计、功能设计以及相关技术讨论等。

本程序在Microsoft Windows Server 2003/Microsoft Visual C++ 2005的命令行编译器cl.exe环境编译下通过。

分发包说明程序分发包中将包含以下文件，其用途分别如表格1所示。

数据结构设计主程序数据结构主程序中采用两个整型数组input_array和output_array，其长度均为10000，分别作为待排序数据和已排序数据的存放空间，并设置一整型数组sort_time用来存放5个算法的执行时间。

之所以这样设计，是因为所有的用户定义函数都完全按照既定的“标准”设计实现，使得整个程序的可伸缩性大大增强。

排序算法的设计实现程序中的全部5中排序算法均按照标准化的函数名、返回值和形参表设计，其形式为：1实现。

插入排序插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的有序表。

快速排序1参见：参考资料[2]和[3]。

快速排序是对冒泡法排序的一种改进。

它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录均比另一部分记录小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

归并排序归并排序的核心操作是将一位数组中前后两个相邻的有序序列归并为一个有序序列，其实现如下：并为相邻的有序序列，依次递归的执行下去，最终归并为一个有序序列。

实验报告3实验名称：数据结构与软件设计实习题目：内部排序算法比较专业：生物信息学班级：01 姓名：学号：实验日期：2010.07.24一、实验目的：比较冒泡排序、直接插入排序、简单选择排序、快速排序、希尔排序；二、实验要求：待排序长度不小于100，数据可有随机函数产生，用五组不同输入数据做比较，比较的指标为关键字参加比较的次数和关键字移动的次数；对结果做简单的分析，包括各组数据得出结果的解释；设计程序用顺序存储。

三、实验内容对各种内部排序算法的时间复杂度有一个比较直观的感受，包括关键字比较次数和关键字移动次数。

将排序算法进行合编在一起，可考虑用顺序执行各种排序算法来执行，最后输出所有结果。

四、实验编程结果或过程：1. 数据定义typedef struct { KeyType key; }RedType; typedef struct { RedType r[MAXSIZE+1]; int length;}SqList;2. 函数如下，代码详见文件“排序比较.cpp”int Create_Sq(SqList &L)void Bubble_sort(SqList &L)//冒泡排序void InsertSort(SqList &L)//插入排序void SelectSort(SqList &L) //简单选择排序int Partition(SqList &L,int low,int high) void QSort(SqList &L,int low,int high)//递归形式的快速排序算法void QuickSort(SqList &L)void ShellInsert(SqList &L,int dk)//希尔排序void ShellSort(SqList &L,int dlta[ ])3. 运行测试结果，运行结果无误，如下图语速个数为20元素个数为100错误调试无。

内部排序算法比较1、课程设计的目的本课程设计为了更好的了解和认识数据结构常用的内部排序算法。

排序对于数据结构的管理来说是至关重要的，所以熟悉掌握和深入了解这些常用的经典内部排序算法是有必要的。

2、课程设计的要求1. 掌握常用的排序方法和各种排序方法的特点。

2.熟悉排序的基本概念。

3、课程设计的内容3.1需求分析编制一个演示内部排序算法比较的程序。

可对冒泡排序、直接插入排序、简单选择排序、快速排序、希尔排序和堆排序进行比较。

3.2概要设计（1）冒泡排序基本思想是：设数组a中存放了n 个数据元素，循环进行n-1次如下的排序过程：第一次时，依次比较相邻两个数据元素a[i]和a[i+1].key(i=0,1,2,3...,n-2).若为逆序，则交换两个数据元素，否则不交换，这样，当作完n-1次比较后数值最大的数据元素将比放置在a[n-1]中。

第二次时，数据元素个数减1，即数据元素个数为n-1，操作方法与第一次类似，这样，n个数据元素集合中数值次大的数据元素将被放置在a[n-2]中。

当第n-1次排序结束时，n个数据元素集合中次小的数据元素将被放置在a[1]中，而a[0]中放置了最小的数据元素。

冒泡排序算法的空间复杂度为o(n2)。

（2）直接插入排序基本思想是:顺序地把待插入的数据元素按其关键字的大小插入到已排序数据元素子集合的适当位置.子集合的数据元素个数从只有一个数据元素开始逐次增大,当子集合最终与集合大小相同时排序完毕.设待排序的N个数据元素存放在数组A中,初始时子集合a[0]以排好序.第一次循环准备把数据元素a[1]插入到以排好序的子集合中,这只需比较a[0].key和a[1].key,若a[0].key<=a[1].key,则说明序列已有序,否则,将a[1]插入到a[0]之前,这样子集合的大小增大为2;第二次循环是把数据元素a[2]插入到以排好序的子集合中,这需要先比较a[2].key和a[1].key,已确定是否需要把a[2]插到a[1]之前,然后比较a[2].key和a[0].key,以确定是否需要把a[2]插入到a[0]之前;这样的循环过程一直进行到a[n-1]插入完为止.这时,数据元素集合a[0],a[1],a[2],...,a[n-1]就全部排好了序。

《数据结构与算法》实验报告一、需求分析问题描述：在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。

试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。

基本要求：（l）对以下6种常用的内部排序算法进行比较：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。

（2）待排序表的表长不小于100000；其中的数据要用伪随机数程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。

（3）最后要对结果作简单分析，包括对各组数据得出结果波动大小的解释。

数据测试：二．概要设计1.程序所需的抽象数据类型的定义：typedef int BOOL; //说明BOOL是int的别名typedef struct StudentData { int num; //存放关键字}Data; typedef struct LinkList { int Length; //数组长度Data Record[MAXSIZE]; //用数组存放所有的随机数} LinkList int RandArray[MAXSIZE]; //定义长度为MAXSIZE的随机数组void RandomNum() //随机生成函数void InitLinkList(LinkList* L) //初始化链表BOOL LT(int i, int j,int* CmpNum) //比较i和j 的大小void Display(LinkList* L) //显示输出函数void ShellSort(LinkList* L, int dlta[], int t,int* CmpNum, int* ChgNum) //希尔排序void QuickSort (LinkList* L, int* CmpNum, int* ChgNum) //快速排序void HeapSort (LinkList* L, int* CmpNum, int* ChgNum) //堆排序void BubbleSort(LinkList* L, int* CmpNum, int* ChgNum) //冒泡排序void SelSort(LinkList* L, int* CmpNum, int* ChgNum) //选择排序void Compare(LinkList* L,int* CmpNum, int* ChgNum) //比较所有排序2 .各程序模块之间的层次（调用）关系：二、详细设计typedef int BOOL; //定义标识符关键字BOOL别名为int typedef struct StudentData //记录数据类型{int num; //定义关键字类型}Data; //排序的记录数据类型定义typedef struct LinkList //记录线性表{int Length; //定义表长Data Record[MAXSIZE]; //表长记录最大值}LinkList; //排序的记录线性表类型定义int RandArray[MAXSIZE]; //定义随机数组类型及最大值/******************随机生成函数********************/void RandomNum(){int i; srand((int)time(NULL)); //用伪随机数程序产生伪随机数for(i=0; i小于MAXSIZE; i++) RandArray[i]<=(int)rand(); 返回;}/*****************初始化链表**********************/void InitLinkList(LinkList* L) //初始化链表{int i;memset(L,0,sizeof(LinkList));RandomNum();for(i=0; i小于<MAXSIZE; i++)L->Record[i].num<=RandArray[i]; L->Length<=i;}BOOL LT(int i, int j,int* CmpNum){(*CmpNum)++; 若i<j) 则返回TRUE; 否则返回FALSE;}void Display(LinkList* L){FILE* f; //定义一个文件指针f int i;若打开文件的指令不为空则//通过文件指针f打开文件为条件判断{ //是否应该打开文件输出“can't open file”;exit(0); }for (i=0; i小于L->Length; i++)fprintf(f,"%d\n",L->Record[i].num);通过文件指针f关闭文件;三、调试分析1.调试过程中遇到的问题及经验体会:在本次程序的编写和调试过程中，我曾多次修改代码，并根据调试显示的界面一次次调整代码。

内部排序算法比较【实验简介】1、在教科书各种内部排序算法的时间复杂度分析结果只给出了算法执行的时间的阶，或大概的执行时间，如：直接插入排序即时间复杂度为O（n*n）2、通过五组随机数据、一组正序数据与一组逆序数据比较6种常用的内部算法（起泡排序、直接插入排序、简单选择排序、快速查找排序、希尔排序、堆排序）的关键字比较次数和关键字移动次数，以取得直观感受；3、用五组不同的长度不小于100的数据进行测试，并对测试结果作出简单的分析，对得出结果拨动大小的进行解释；【设计模块】【对应模块算法说明】(1) 此算法程序中需要用到顺序表数据类型,数据元素的类型定义如下:typedef struct{KeyType key; //关键字项}RedType;typedef struct{RedType r[MAXSIZE+1]; //0号单元闲置或用作哨兵单元int length; //顺序表长度int info; //记录关键字移动次数int cmp; //关键字的比较次数}Sqlist;(2) 本实验用到六种排序算法，一个主函数和菜单函数,其中排序算法分别为起泡排序、直接插入排序、简单选择排序、快速查找排序、希尔排序、堆排序；相应时间复杂度分析如下：起泡排序：若待排序列为“正序”，则需进行一趟排序在排序过程中关键字需进行n-1次比较，无须移动纪录；若是“逆序”，则进行n-1趟排序，需n(n-1)/2次比较，并坐等数量级的移动，因此总的事件复杂度为O（n2）;直接插入排序待排序纪录是随机的，关键字间的移动次数和比较次数的平均值约为n*n/4,即时间复杂度为O（n2）;简单的选择排序虽然在排序过程中所需要的移动次数较少，最小时为0，最大时为3（n-1）；但是关键字的比较次数总是相同的，均为n(n-1)/2，因此，时间复杂度亦为O（n2）;快速排序其平均时间是kn*㏑n,其中n为待排序列中纪录的个数，k为某个常数，其时间复杂度为O（n*㏑n）；希尔排序当增序序列为dlta[k]=2t-k+1-1时，时间复杂度为O（n3/2）,其中t为排序趟数，1≤k≤t≤㏒2(n+1);堆排序此排序对于含n个元素的序列排序时，总共进行的关键字比较次数不超过4n，且在最坏的情况下，其时间复杂度为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) //冒泡排序{for(i=0;i<L->length;i++){L->r[0]=L->r[1];for(j=1;j<N-i;j++)if(L->r[0].key>=L->r[j+1].key)L->r[j] L->r[j+1]; //交换两记录的位置elseL->r[0]=L->r[j+1]; //保证L->r[0]始终为较大的记录L->r[j+1]=L->r[0]; //把最大的记录放到祠堂排序的最高位置}printf(L->r[MAXSIZE]);//输出排序后数组和相关数据}②直接插入排序本算法的思路是，把L->r[0]设置为哨兵，排序时把第i个记录复制给哨兵，并于其前的i-1个记录进行比较，找到第一个比起大的记录，利用循环让记录后移，把其放到第一个比起大的记录前面。

XXXXXX大学《数据结构》课程设计报告目录排序算法比较一、需求分析二、程序的主要功能三、程序运行平台四、数据结构五、算法及时间复杂度六、测试用例七、程序源代码二感想体会与总结排序算法比较一、需求分析利用随机函数产生N个随机整数（N = 500，1000，1500，2000，2500，…,30000），利用直接插入排序、折半插入排序，起泡排序、快速排序、选择排序、堆排序，基数排序七种排序方法（可添加其它排序方法）进行排序（结果为由小到大的顺序），并统计每一种排序所耗费的时间（统计为图表坐标形式）。

二、程序的主要功能1.用户输入任意个数，产生相应的随机数2.用户可以自己选择排序方式（直接插入排序、折半插入排序、起泡排序、快速排序、选择排序、堆排序、基数排序）的一种3.程序给出原始数据、排序后从小到大的数据，并给出排序所用的时间。

三、程序运行平台Visual C++ 6.0版本四、数据结构本程序的数据结构为线形表，线性顺序表、线性链表。

1、结构体：typedef struct{int *r; //r指向线形表的第一个结点。

r[0]闲置，不同的算法有不同的用处，如用作哨兵等。

int length; //顺序表的总长度}Sqlist;2、空线性表Status InitSqlist(Sqlist &L){L.r=(int *)malloc(MAXSIZE*sizeof(int)); //分配存储空间if(!L.r){printf("存储分配失败！");exit(0);} //存储分配失败L.length=0;//初始长度为0return OK;}五、算法及时间复杂度（一）各个排序是算法思想：（1）直接插入排序：将一个记录插入到已排好的有序表中，从而得到一个新的，记录数增加1的有序表。

（2）折半插入排序：插入排序的基本插入是在一个有序表中进行查找和插入，这个查找可利用折半查找来实现，即为折半插入排序。

课程设计任务书题目常用内部排序算法分析与比较专业、班级计算机科学与技术10-02班学号姓名主要内容：分析直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序等常用的内部排序算法的思想，通过交换次数以及比较次数来对这些算法进行比较。

基本要求：通过给定的记录数目及排序思想，设计相应的存储结构，程序之中要求可以实现完全随机，部分逆序等测试数据，来对每一种排序算法进行验证。

其次还要设计出一个统计交换次数和比较次数的函数来进行计数。

从待排序的记录数目、记录大小、关键字结构及其对稳定性的要求讨论出每种算法使用的环境。

主要参考资料：严蔚敏吴伟民数据结构（C语言版）清华大学出版社完成期限：2012/6/21指导教师签名：课程负责人签名：2012年 6月 21 日一、设计题目：常用的内部排序的算法分析和比较二、运行环境：操作系统：Windows软件：Visual C++ 6.0三、设计目的：针对常见的计算机内部排序算法，如直接插入排序、希尔排序、冒泡排序、简单选择排序、堆排序、归并排序、基数排序等，通过是自己设计的程序，借助排序中交换次数和比较次数来比较这些算法的适用范围。

四、程序设计的流程图：五、算法分析：1、简单选择排序：简单选择排序的每一趟都是从待排的数据元素中选出一个最小（最大）的一个元素，顺序的放在已经排好的数列的最后，直到全部待排序的数据元素排序完毕。

2、直接插入排序：这是一种最简单的排序方法，它的基本操作时将一个记录插入到一个已经排好序的有序表中，从而得到一个新的记录数增1的有序表。

其效率：从空间的角度来看待，它只需要一个辅助的空间，从时间上来看的话，排序的基本操作是比较两个关键字的大小和移动（本程序中将移动和交换看成一样）记录。

在整个排序的过程中，当待排序列中的关键字非递减有序的话，那么比较次数最小n-1，且不需要移动，当待排序列逆序时，比较次数达到最大（n+2）（n-1）/2，记录的移动的次数也达到最大值（n+4）（n-1）/2。

题目：编制一个演示内部排序算法比较的程序班级：姓名：学号：完成日期：一、需求分析1．本演示程序对以下6种常用的内部排序算法进行实测比较：起泡排序，直接插入排序，简单选择排序，快速排序，希尔排序，堆排序。

2．待排序表的元素的关键字为整数。

比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换记为3次移动）。

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

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

二、概要设计1．可排序表的抽象数据类型定义：ADT OrderableList{数据对象：D={ai|ai∈IntegerSet,i=1,2,…,n,n≥0}数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,…,n}基本操作：InitList(n)操作结果：构造一个长度为n，元素值依次为1，2，…,n的有序表。

RandomizeList(d,isInverseOrder)操作结果：首先根据isInverseOrder为True或False,将表置为逆序或正序，然后将表进行d(0≤d≤8)级随机打乱。

d为0时表不打乱，d越大，打乱程度越高。

RecallList()操作结果：恢复最后一次用RandomizeList随机打乱得到的可排序表。

ListLength()操作结果：返回可排序表的长度。

ListEmpty()操作结果：若可排序表为空表，则返回Ture，否则返回False。

BubbleSort( &c, &s)操作结果：进行起泡排序，返回关键字比较次数c和移动次数s。

InsertSort( &c, &s)操作结果：进行插入排序，返回关键字比较次数c和移动次数s。

SelectSort ( &c, &s)操作结果：进行选择排序，返回关键字比较次数c和移动次数s。

QuickSort(&c, &s)操作结果：进行快速排序，返回关键字比较次数c和移动次数s。

排序算法比较c语言课程设计一、教学目标本课程的教学目标是使学生掌握排序算法的原理和实现，能够运用C语言编写排序算法，并理解不同排序算法的性能和适用场景。

具体目标如下：1.知识目标：学生需要了解常见排序算法的原理和实现，包括冒泡排序、选择排序、插入排序、快速排序等。

2.技能目标：学生能够运用C语言编写排序算法，并能够分析代码的性能和优化空间。

3.情感态度价值观目标：学生通过实践操作和问题解决，培养编程思维和解决问题的能力，激发对计算机科学的兴趣和热情。

二、教学内容本课程的教学内容主要包括排序算法的原理和实现，以及C语言编程基础。

具体安排如下：1.排序算法的原理和实现：介绍冒泡排序、选择排序、插入排序、快速排序等常见排序算法的原理和实现方法。

2.C语言编程基础：介绍C语言的基本语法和编程方法，包括变量、数据类型、运算符、控制语句等。

3.排序算法的性能分析：分析不同排序算法的性能，包括时间复杂度和空间复杂度，并理解影响性能的因素。

三、教学方法本课程的教学方法包括讲授法、实践操作法和讨论法。

具体方法如下：1.讲授法：通过讲解排序算法的原理和实现方法，使学生掌握基本概念和理论知识。

2.实践操作法：通过编写C语言代码实现排序算法，使学生能够将理论知识应用到实际编程中。

3.讨论法：通过小组讨论和问题解决，培养学生的编程思维和解决问题的能力。

四、教学资源本课程的教学资源包括教材、编程环境和辅助教学工具。

具体资源如下：1.教材：选择一本与C语言编程和排序算法相关的教材，提供理论知识的学习和参考。

2.编程环境：提供C语言编程环境，如Visual Studio、Code::Blocks等，方便学生编写和调试代码。

3.辅助教学工具：提供编程实例和练习题，帮助学生巩固知识和提高编程能力。

以上是本课程的教学目标、教学内容、教学方法和教学资源的设计。

通过本课程的学习，希望学生能够掌握排序算法的原理和实现，提高编程能力，并培养解决问题的能力。

排序算法比较c语言课程设计一、课程目标知识目标：1. 理解排序算法的基本概念和分类；2. 掌握冒泡排序、选择排序、插入排序等常见排序算法的实现原理和步骤；3. 了解不同排序算法的时间复杂度和空间复杂度分析；4. 学会使用C语言实现不同排序算法。

技能目标：1. 能够运用所学排序算法解决实际问题；2. 培养良好的编程习惯，编写结构清晰、可读性强的代码；3. 提高分析问题和解决问题的能力，具备一定的算法优化意识。

情感态度价值观目标：1. 培养学生对计算机科学的兴趣，激发学习热情；2. 培养学生的团队合作意识，提高沟通能力；3. 培养学生勇于面对挑战，克服困难的精神。

课程性质：本课程为C语言程序设计的一部分，重点在于让学生通过排序算法的学习，掌握C语言编程技巧，提高解决问题的能力。

学生特点：学生已经具备一定的C语言基础，了解基本的数据结构和算法，但对于排序算法的深入理解和应用尚有不足。

教学要求：注重理论与实践相结合，让学生在实践中掌握排序算法的原理和应用。

通过案例分析和编程实践，培养学生分析问题、解决问题的能力。

同时，关注学生的情感态度价值观培养，提高综合素质。

在教学过程中，将课程目标分解为具体的学习成果，以便进行教学设计和评估。

二、教学内容1. 排序算法基本概念：介绍排序的定义、排序算法的稳定性、内排序与外排序的分类。

2. 常见排序算法：- 冒泡排序：讲解其原理、实现步骤、时间复杂度和空间复杂度分析；- 选择排序：介绍其原理、实现步骤、时间复杂度和空间复杂度分析；- 插入排序：阐述其原理、实现步骤、时间复杂度和空间复杂度分析；- 快速排序：讲解其原理、实现步骤、时间复杂度和空间复杂度分析，以及优化方法。

3. 排序算法性能比较：分析各种排序算法的时间复杂度和空间复杂度，探讨不同场景下排序算法的适用性。

4. C语言实现排序算法：结合教材，编写冒泡排序、选择排序、插入排序和快速排序的C语言代码，并进行调试和优化。

****课程设计报告题目：各种内部排序性能比较学生姓名：彭伟奇学号： 1021112417班级：10211124指导教师：高永平2012年6 月15 日一、课程设计目的本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。

二、实验要求任务：用程序实现插入法排序、起泡法、选择法、快速法、合并法排序；输入的数据形式为任何一个正整数，大小不限。

输出的形式：数字大小逐个递增的数列。

功能要求：给出多组不同元素个数的输入数据(可考虑用随机函数生成整数，而不用人工输入)，并用列表打印出每种排序下的各趟排序结果。

每个排序法结束时应打印出其元素比较的次数和交换的次数。

此程序需将结果用列表打印，一定要将其打印结果排列好。

三、程序源代码#include "stdlib.h"#include"stdio.h"#include"time.h"#define MAXSIZE 200typedef int KeyType;typedef struct //定义存储记录关键字及其他信息的结构体{ KeyType key;char other;}RedType;typedef struct //定义存储所有记录的结构体{ RedType r[MAXSIZE+1];int length;}SqList;typedef struct{int move; /*记录数据移动次数*/int comp; /*记录数据比较次数*/}Recode;int dlta[5]={31,15,7,3,1}; //初始化希尔排序的增量序列int num[10]={0}; //记录每个排序方法的移动次数和比较次数int flag=0; //标记变量//利用产生的随即数模拟用户输入的数据class sort{public:void select_sort(SqList L);void Zhijie(SqList L) ;void ShellInsert(SqList *L,int dk,Recode *r);void ShellSort(SqList L,int dlta[],int t) ;void Maopao(SqList L);int Partition(SqList *L,int low,int high,Recode *r); void QuickSort(SqList L) ;protected:int dk,dlta[5],t,low,high;};void create(SqList *L,int length){ int i;srand(time(0));L->length=length;for(i=1;i<=L->length;i++){L->r[i].key=rand()%1000;L->r[i].other=rand()%5;}}/*输出元素*/void visit(SqList L){int i;printf("\n");for(i=1;i<=L.length;i++)printf("%4d%2c",L.r[i].key,L.r[i].other);printf("\n");}/*简单选择排序*/void select_sort(SqList L){ Recode r;p =0;r.move =0;int i,j,k;RedType t;for (i=1;i<L.length;i++){ j=i;for (k=i+1;k<=L.length;k++){ p++;if (L.r[j].key>L.r[k].key){j=k;}}if (i!=j){t=L.r[j];L.r[j]=L.r[i];L.r[i]=t;r.move =r.move +3;}}if(!flag){ printf("本次随机数据排序的移动次数为:");printf("%d\n",r.move);printf("本次随机数据排序的比较次数为:");printf("%d\n",p);printf("简单选择排序后的结果：");visit(L);}else{num[0]=r.move;num[1]=p;}}//直接插入排序void Zhijie(SqList L){ Recode r;p =0;r.move =0;int j;for(int i=2;i<=L.length;++i){ p ++;if(L.r[i].key<L.r[i-1].key){L.r[0]=L.r[i]; //复制为哨兵L.r[i]=L.r[i-1];r.move=r.move +2;for(j=i-2;L.r[0].key < L.r[j].key;--j){L.r[j+1]=L.r[j]; //记录后移r.move ++;p ++;}L.r[j+1]=L.r[0]; //插入到正确位置r.move ++;}}if(!flag){printf("本次随机数据排序的移动次数为:");printf("%d\n",r.move);printf("本次随机数据排序的比较次数为:");printf("%d\n",p);printf("直接插入排序后的结果：");visit(L);}else{num[2]=r.move;num[3]=p;}}void ShellInsert(SqList *L,int dk,Recode *r){ int i,j;for(i=dk+1;i<=L->length ;++i){ r->comp ++;if(L->r[i].key<L->r[i-1].key){ L->r[0]=L->r[i]; //暂存r->move ++;for(j=i-dk;j>0&&(L->r[0].key < L->r[j].key);j-=dk){ L->r[j+dk]=L->r[j]; //记录后移r->move ++;r->comp ++;}L->r[j+dk]=L->r[0]; //插入到正确位置r->move ++;}}}void ShellSort(SqList L,int dlta[],int t){ //按增量序列dlta[0..t-1]对顺序表L作希尔排序。

下载可编辑XXXXXX大学《数据结构》课程设计报告排序算法比较一、需求分析二、程序的主要功能三、程序运行平台四、数据结构五、算法及时间复杂度六、测试用例七、程序源代码二感想体会与总结排序算法比较一、需求分析利用随机函数产生N个随机整数(N二500, 1000, 1500, 2000, 2500,…,30000 )，利用直接插入排序、折半插入排序，起泡排序、快速排序、选择排序、堆排序，基数排序七种排序方法(可添加其它排序方法)进行排序(结果为由小到大的顺序)，并统计每一种排序所耗费的时间(统计为图表坐标形式)。

二、程序的主要功能1. 用户输入任意个数，产生相应的随机数2. 用户可以自己选择排序方式(直接插入排序、折半插入排序、起泡排序、快速排序、选择排序、堆排序、基数排序)的一种3. 程序给出原始数据、排序后从小到大的数据，并给出排序所用的时间。

三、程序运行平台Visual C++ 6.0 版本四、数据结构本程序的数据结构为线形表，线性顺序表、线性链表。

1、结构体:typedef struct{int *r; 〃r指向线形表的第一个结点。

r[0]闲置，不同的算法有不同的用处，如用作哨兵等。

int len gth; // 顺序表的总长度}Sqlist;2、空线性表Status In itSqlist(Sqlist &L){L.r=(int *)malloc(MAXSIZE*sizeof(int)); // 分配存储空间if(!L.r){prin tf(" 存储分配失败！");exit(0);} //存储分配失败L.length=O;〃初始长度为0return OK;}五、算法及时间复杂度（—）各个排序是算法思想：（1）直接插入排序：将一个记录插入到已排好的有序表中，从而得到一个新的，记录数增加1的有序表。

（2）折半插入排序：插入排序的基本插入是在一个有序表中进行查找和插入，这个查找可利用折半查找来实现，即为折半插入排序。

内部排序算法的实现与⽐较-数据结构课程设计内部排序算法的实现与⽐较1）问题描述在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执⾏时间的阶，或⼤概执⾏时间。

试通过随机数据⽐较各算法的关键字⽐较次数和关键字移动次数，以取得直观感受。

2）基本要求(1) 对常⽤的内部排序算法进⾏⽐较：直接插⼊排序、简单选择排序、冒泡排序、快速排序、希尔排序、归并排序。

(2) 利⽤随机函数产⽣N（N=30000）个随机整数，作为输⼊数据作⽐较；⽐较的指标为关键字参加的⽐较次数和关键字的移动次数（关键字交换计为3次移动）。

(3) 对结果作出简要分析。

3）测试数据随机函数产⽣。

4）提⽰主要⼯作是设法在已知算法中适当位置插⼊对关键字的⽐较次数和移动次数的计数操作。

注意采⽤分块调试的⽅法。

5）输⼊输出:输⼊数据：参加排序的整数个数N（N=30000，注：不得减少N）；输出数据：各种排序⽅法的关键字⽐较次数和移动次数（从⼩到⼤排列）。

本来冒泡排序交换次数想⽤树状数组BIT发现数据太多时 ⽤BIT加的数据会超限 所以还是直接⽤了冒泡排序上代码--纯C语⾔：/** zhagoodwell 查昊昊QQ微信：2423824433* 直接插⼊： charu函数* 选择： xuanzepai函数* 冒泡: maopao函数* 快排： Qsort 递归函数* 希尔：shell 函数* 归并：GB 函数*/# include <stdio.h># include <stdlib.h># include <time.h># define N 30000# define SR 1001int A[N],B[N],C[N],D[N],E[N],F[N],G[N];int a,aa,b,bb,d,dd,e,ee,f,ff,num; //单个字母的为记录的⽐较次数-移动的次数，双字母为关键字的移动次数long long c,cc;void charu(int A[],int n);//对n个元素直接插⼊排序void xuanzepai(int A[],int n);//对n个元素选择升序void maopao(int A[],int n); // 冒泡排序void Quicksort(int A[],int L,int R);//对[L,R]个元素快速升序void shell(int A[],int n);//对n个元素 shell 升序void GBPX(int S[],int L,int R,int T[]);// 归并排序int GB(int S[],int L,int M,int R,int T[]);//数组归并操作int gainint(int *p,int min,int max);//防输错⽽建的函数 *p的范围[min,max]int change(int *a,int *b);//交换函数交换a b的值void charu(int A[],int n)//返回循环⽐较次数int i,j,temp;for (i=1,a++;i<n;i++,a++)if (A[i]<A[i-1]){temp=A[i];for(a++,aa++,j=i-1;j>=0&& A[j]>temp;j--,a++,aa++) A[j+1]=A[j];A[j+1]=temp;}}void xuanzepai(int A[],int n)//以A[0]为⽐较依据升序{int i,j,k;for(i=0,b++;i<n-1;i++,b++){k=i;for(j=i+1,b++;j<n;j++,b++)if(A[j]<A[k]){ k=j;b++;}if(k!=i){bb+=change(&A[i],&A[k]);}}}void maopao(int A[],int n){int i,j;for (i = n -1 ; i>=0 ;i--){for (j = 0; j<i; j++){if(A[j]>A[j+1])cc+=change(&A[j],&A[j+1]);}}}void Quicksort(int A[],int L,int R)//快速排序升序{int i=L,j=R,T=A[L]; //T为基准数if(L>R) return;while(i!=j) //当数组左右两边没相遇{while(A[j]>=T&&i<j){j--;d++;} //从右向左找while(A[i]<=T&&i<j){i++;d++;} //从左向右找if(i<j)dd+=change(&A[i],&A[j]); //交换两数}if(L!=i)dd+=change(&A[L],&A[i]); //基准数归位Quicksort(A,L,i-1); //递归左Quicksort(A,i+1,R); //递归右}void shell(int A[],int n)//希尔排序增量为2{int i,j,k;for(k=n>>1,e++;k>0;k=k>>1,e++){for(i=k,e++;i<n;i++,e++){for(j=i-k,e++;j>=0;j-=k,e++)if(A[j]>A[j+k])ee+=change(&A[j],&A[j+k]);}}int GB(int S[],int L,int M,int R,int T[])//数组归并操作{int i=M,j=R,k=0,count=0;while(i>=L&&j>M){f++;if(S[i]>S[j]){T[k++]=S[i--];//从临时数组的最后⼀个位置开始排序}else T[k++]=S[j--];count++;}while(i>=L){f++;T[k++]=S[i--];} //若前半段数组还有元素未放⼊临时数组T中while(j>M){f++;T[k++]=S[j--];}for(i=0,f+=k;i<k;i++) S[R-i]=T[i];//写回原数组return count;}void GBPX(int S[],int L,int R,int T[]){int M;if(L<R){M=(L+R)>>1;GBPX(S,L,M,T);//找左半段的逆序对数⽬GBPX(S,M+1,R,T);//找右半段的逆序对数⽬ff+=GB(S,L,M,R,T);//找完左右半段逆序对以后两段数组有序，找两段之间的逆序对。