数据结构 第3章 内部排序

第三章排序一、选择题1．某内排序方法的稳定性是指( D )。

A．该排序算法不允许有相同的关键字记录、B．该排序算法允许有相同的关键字记录C．平均时间为0（n log n）的排序方法 D．以上都不对2．下面给出的四种排序法中( )排序法是不稳定性排序法。

A. 插入B. 冒泡C. 二路归并D. 快速排序3．下列排序算法中，其中（ CD ）是稳定的。

A. 堆排序，冒泡排序B. 快速排序，堆排序C. 直接选择排序，归并排序D. 归并排序，冒泡排序6．若要求尽可能快地对序列进行稳定的排序，则应选（ B ）。

A．快速排序 B．归并排序 C．冒泡排序12．排序趟数与序列的原始状态有关的排序方法是( D )排序法。

A．插入 B. 选择 C. 冒泡 D. 快速17．数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的( C )的两趟排序后的结果。

A．选择排序 B.冒泡排序 C.插入排序18．数据序列（2，1，4，9，8，10，6，20）只能是下列排序算法中的( A )的两趟排序后的结果。

A. 快速排序B. 冒泡排序C. 选择排序D. 插入排序19．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 8447 （4） 15 21 25 47 84，则采用的排序是 ( A )。

A. 选择B. 冒泡C. 快速D. 插入24．下列序列中，（ D ）是执行第一趟快速排序后所得的序列。

A. [68，11，18，69] [23，93，73]B. [68，11，69，23] [18，93，73]C. [93，73] [68，11，69，23，18]D. [68，11，69，23，18] [93，73]28．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( C )排序。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

基本要求：（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、对关键字序列（21,19,37,5,2），经直接插入排序法由小到大排序，第一趟后所得结果为（）。

A.(19，21，5，2，37)B.(19，21，37，5，2)C.(19，21，2，5，37)D.(19，21，5，37，2)正确答案：B2、对关键字序列（21,19,37,5,2），经冒泡排序法由小到大排序，第一趟后所得结果为（）。

A.(19，21，37，5，2)B.(19，21，2，5，37)C.(19，21，5，37，2)D.(19，21，5，2，37)正确答案：D3、对关键字序列（149,138,165,197,176,113,127），采用基数排序的第一趟之后所得结果为（）。

A.(113，165，176，197，127，138，149)B.(113，165，176，127，197，138，149)C.(113，127，138，149，165，176，197)D.(149，138，165，197，176，113，127)正确答案：A4、下列各项键值（）序列不是堆的。

A.(5，23，68，16，94)B.(5，23，16，94，68)C.(5，16，23，68，94)D.(5，23，16，68，94)正确答案：A5、假设一组待排序的关键字序列为（24,62,36,19），要求从小到大进行排序，（）是归并排序的过程。

A.(24，62，36，19)(24，36，62，19)(19，24，36，62)B.(24，62，19，36)(19，24，36，62)C.(62，24，36，19)(19，24，36，62)D.(24，19，36，62)(24，19，36，62)(19，24，36，62)正确答案：B6、在第一趟排序之后，不能确保将数据表中某一个元素放在其最终位置上的排序算法是（）。

A.归并排序B.快速排序C.冒泡排序D.选择排序正确答案：A7、对于下列排序，（）的时间效率与关键字初始序列有直接关系。

数据结构--内部排序算法1、下列排序算法中，_____________排序在某趟结束后不一定能选出一个元素放到其最终的位置上。

（1）选择（2）冒泡（3）归并（4）堆2、下列排序算法中，依次将待排序列中的元素和前面有序序列合并为一个新的有序序列的排序算法是___________________。

（1）直接插入排序（2）冒泡排序(3)快速排序（4）直接选择排序3、下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是______________。

（1）直接插入排序列（2）快速排序（3）直接选择排序（4）堆排序4、依次将待排序序列中的元素和有序子序列合并一个新的有序子序列的算法是______________。

（1）快速排序（2）插入排序（3）冒泡排序（4）堆排序5、已知数据表A中每个元素距其最终位置不远，则采用_____________排序算法最节省时间。

（1）堆排序（2）插入排序（3）快速排序（4）直接选择排序6、下列排序算法中，_______________算法可能会出现下面情况，在最后一趟开始之前，所有元素都不在其最终的位置上。

（1）堆排序（2）冒泡排序（3）快速排序（4）插入排序7、数据表A中有10000个元素，如果仅要求求出其中最大的10个元素，则采用____________排序算法最节省时间。

（1）堆排序（2）希尔排序（3）快速排序（4）直接选择排序8、下列算法中，____________每一趟都能选出一个元素放在其最终位置上，并且是不稳定的。

（1）冒泡排序（2）希尔排序（3）直接选择排序列（4）直接插入排序9、下列排序算法中，某一趟结束后未必能选出一个元素放在其最位置上的是__________________。

（1）堆排序（2）冒泡排序（3）快速排序（4）直接插入排序10、下列排序算法中，________________算法可能会出现下面情况，初始数据有序时，花费的时间反而最多。

内部排序算法比较第一章问题描述排序是数据结构中重要的一个部分，也是在实际开发中易遇到的问题，所以研究各种排算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决！该系统通过对各种内部排序算法如直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序、二路归并排序等，以关键码的比较次数和移动次数分析其特点，并进行比较，估算每种算法的时间消耗，从而比较各种算法的优劣和使用情况！排序表的数据是多种不同的情况，如随机产生数据、极端的数据如已是正序或逆序数据。

比较的结果用一个直方图表示。

第二章系统分析界面的设计如图所示：|******************************||-------欢迎使用---------||-----（1）随机取数-------||-----（2）自行输入-------||-----（0）退出使用-------||******************************|请选择操作方式：如上图所示该系统的功能有：（1）：选择 1 时系统由客户输入要进行测试的元素个数由电脑随机选取数字进行各种排序结果得到准确的比较和移动次数并打印出结果。

（2）选择 2 时系统由客户自己输入要进行测试的元素进行各种排序结果得到准确的比较和移动次数并打印出结果。

（3）选择0 打印“谢谢使用！！”退出系统的使用！！第三章系统设计（I）友好的人机界面设计：（如图3.1所示）|******************************||-------欢迎使用---------||-----（1）随机取数-------||-----（2）自行输入-------||-----（0）退出使用-------||******************************|（3.1）（II）方便快捷的操作：用户只需要根据不同的需要在界面上输入系统提醒的操作形式直接进行相应的操作方式即可！如图（3.2所示）|******************************||-------欢迎使用---------||-----（1）随机取数-------||-----（2）自行输入-------||-----（0）退出使用-------||******************************|请选择操作方式：（用户在此输入操作方式）（3.2）（III）系统采用定义结构体数组来存储数据。

第一节栈
一、栈的定义及其运算
1、栈的定义
栈(Stack)：是限定在表的一端进行插入和删除运算的线性表，通常将插入、删除的一端称为栈项(top)，另一端称为栈底(bottom)。

不含元素的空表称为空栈。

栈的修改是按后进先出的原则进行的，因此，栈又称为后进先出(Last In First Out)的线性表，简称为LIFO表。

真题选解
（例题·填空题）1、如图所示，设输入元素的顺序是（A，B，C，D），通过栈的变换，在输出端可得到各种排列。

若输出序列的第一个元素为D，则输出序列为。

隐藏答案
【答案】DCBA
【解析】根据堆栈"先进后出"的原则，若输出序列的第一个元素为D，则ABCD入栈，输出序列为DCBA
2、栈的基本运算
(1)置空栈InitStack(&S)：构造一个空栈S。

自考《数据结构》各章要点一第一章概论数据就是指能够被计算机识别、存储和加工处理的信息的载体。

数据元素是数据的基本单位，可以由若干个数据项组成。

数据项是具有独立含义的最小标识单位。

数据结构的定义：·逻辑结构：从逻辑结构上描述数据，独立于计算机。

·线性结构：一对一关系。

·线性结构：多对多关系。

·存储结构：是逻辑结构用计算机语言的实现。

·顺序存储结构：如数组。

·链式存储结构：如链表。

·稠密索引：每个结点都有索引项。

·稀疏索引：每组结点都有索引项。

·散列存储结构：如散列表。

·对数据的操作：定义在逻辑结构上，每种逻辑结构都有一个运算集合。

·常用的有：检索、插入、删除、更新、排序。

·数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。

·原子类型：由语言提供。

·结构类型：由用户借助于描述机制定义，是导出类型。

抽象数据类型ADT：·是抽象数据的组织和与之的操作。

相当于在概念层上描述问题。

·优点是将数据和操作封装在一起实现了信息隐藏。

程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。

算法取决于数据结构。

算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。

评价算法的好坏的因素：·算法是正确的；·执行算法的时间；·执行算法的存储空间(主要是辅助存储空间)；·算法易于理解、编码、调试。

时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。

渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。

评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。

算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。

时间复杂度按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、……k次方阶O(n^k)、指数阶O(2^n)。

一、课程设计概述：本次数据结构课程设计共完成二个题：a.教学计划编制问题b.内部排序算法的性能分析使用语言：C编译环境：/二、课程设计题目一[实验内容]教学计划编制问题[问题描述]答学的每个专业都要制定教学计划。

假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。

每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。

每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。

每门课恰好占一个学期。

试在这样的前提下设计一个教学计划编制程序[需求分析]（1）输入参数包括：学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串）、学分和直接先修课的课程号。

（2）允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。

（3）若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。

计划的表格格式自行设计。

[概要设计]md init() /*初始化教学计划*/void select (int quee[],int i,int j,md a) /*使课程集中在前面*/void arrage(md a) /*教学计划函数*/[流程图][详细设计]#include<>#include <>#define NULL 0#define maxsize 100 typedef struct stu {int number;int score;struct stu *next; }node;typedef struct{int vex_num;int vex_sco;int have;node *first;}sd;typedef struct{sd arry[maxsize];int max_class;int max_term;int score_limit;}md;md init(){int i,x,c;md a;node *p;printf("enter class total:");scanf("%d",&;printf("enter term total:");scanf("%d",&;printf("enter score limit:");scanf("%d",&;printf("enter class arrange \n");for (i=1;i<=;i++)[i].first=NULL;for(i=1;i<=;i++){printf("enter %i class number and score:",i);scanf("%d %d",&[i].vex_num,&[i].vex_sco);printf("enter %i prior class:",i);c=0;do{scanf("%d",&x);if (x>0){p=(node *)malloc(sizeof(node));p->number=[i].vex_num;p->next=[x].first;[x].first=p;c++;}}while(x>0);[i].have=c;}return a;}/*void disp(md a){node *p;int i;for (i=1;i<=;i++){printf("%d",[i].vex_num);p=[i].first;while(p!=NULL){printf("%d",[p->number].vex_num);p=p->next;}printf("\n");}} */void select (int quee[],int i,int j,md a){int k,temp,min;min=i;for(k=i+1;k<=j;k++)if [quee[k]].vex_sco<[quee[min]].vex_sco)min=k;if(min!=i){temp=quee[i];quee[i]=quee[min];quee[min]=temp;}}void arrage(md a){int quee[maxsize],front,bare,i,j,total_score;node *p;front=bare=0;j=1;for(i=1;i<=;i++)if [i].vex_num!=0&&[i].have==0)quee[++bare]=[i].vex_num;printf("\n %d term study:",j++);total_score=0;while(front!=bare){select(quee,front+1,bare,a);if (total_score+[quee[front+1]].vex_sco<={printf("%d",[quee[front]].vex_num);[quee[front]].vex_num=0;total_score+=[quee[front]].vex_sco;p=[quee[front]].first;while(p!=NULL){[p->number].have--;if [p->number].have==0)quee[++bare]=[p->number].vex_num;p=p->next;}}else{total_score=0;printf(" \n%d term study:",j++);}}}main(){md h;h=init();arrage(h);}[调试分析]问题：现象：最后结果存在问题，无法提供内存原因：函数的参数没有写正确：[运行结果及分析]课程设计题目二[实验内容]内部排序算法的性能分析[问题描述]。