二级C语言排序技术2

请问冒泡排序法，快速排序法，简单插入排序法，希尔排序法，简单选择排序法，堆排序法的复杂度比较

追问：所答非所问，拜托

答案：很简单，对于笔试，多看看书书，对照书本多做做模拟题。机试那你要多上机练练，不懂的地方找一个会C语言的人请教一下。辅导书用南开100题比较不错，祝你好运！计算机二级C语言笔试有：公共基础知识 二级C，上机有：程序填空 程序改错 程序编译（这三题主要是应用函数调用）A 公共基础知识基本要求1.掌握算法的基本概念。2.掌握基本数据结构及其操作。3.掌握基本排序和查找算法。4.掌握逐步求精的结构化程序设计方法。5.掌握软件工程的基本方法，具有初步应用相关技术进行软件开发的能力。6.掌握数据库的基本知识，了解关系数据库的设计。考试内容一、基本数据结构与算法1.算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。2.数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。3.线性表的定义；线性表的顺序存储结构及其插入与删除运算。4.栈和队列的定义；栈和队列的顺序存储结构及其基本运算。5.线性单链表、双向链表与循环链表的结构及其基本运算。6.树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。7.顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。二、程序设计基础1.程序设计方法与风格2.结构化程序设计。3.面向对象的程序设计方法，对象，方法，属性及继承与多态性。三、软件工程基础1.软件工程基本概念，软件生命周期概念，软件工具与软件开发环境。2.结构化分析方法，数据流图，数据字典，软件需求规格说明书。3.结构化设计方法，总体设计与详细设计。4.软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试。5.程序的调试，静态调试与动态调试。四、数据库设计基础1.数据库的基本概念：数据库，数据库管理系统，数据库系统。2.数据模型，实体联系模型及E―R图，从E―R图导出关系数据模型。3.关系代数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论。4.数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略。考试方式1.公共基础知识的考试方式为笔试，与C语言程序设计（C++语言程序设计、Java语言程序设计、Visual Basic语言程序设计、Visual FoxPro数据库程序设计或Access数据库程序设计）的笔试部分合为一张试卷，公共基础知识部分占全卷的30分。2.公共基础知识有l0道选择题和5道填空题。B C语言程序设计基本要求1.熟悉TURBO C集成环境。2.熟练掌握结构化程序设计的方法，具有良好的程序设计风格。3.掌握程序设计中简单的数据结构和算法。4.TURBO C的集成环境下，能够编写简单的C程序，并具有基本的纠错和调试程序的能力。考试内容一、C语言的结构1.程序的构成，MAIN函数和其他函数。2.头文件，数据说明，函数的开始和结束标志。3.源程序的书写格式。4.C语言的风格。二、数据类型及其运算1.C的数据类型（基本类型，构造类型，指针类型，空类型）及其定义方法。2.C运算符的种类、运算优先级和结合性。3.不同类型数据间的转换与运算。4.C表达式类型（赋值表达式，算术表达式，关系表达式，逻辑表达式，条件表达式，逗号表达式）和求值规则。三、基本语句1.表达式语句，空语句，复合语句。2.数据的输入与输出，输入输出函数的调用。3.复合语句。4.GOTO语句和语句标号的使用。四、选择结构程序设计1.用IF语句实现选择结构。2.用SWITCH语句实现多分支选择结构。3.选择结构的嵌套。五、循环结构程序设计1.FOR循环结构。2.WHILE和DO WHILE循环结构。3.CONTINUE语句和BREAK语句。4.循环的嵌套。六、数组的定义和引用1.一维数组和易做图数组的定义、初始化和引用2.字符串与字符数组。七、函数1.库函数的正确调用。2.函数的定义方法。3.函数的类型和返回值。4.形式参数与实在参数，参数值的传递。5.函数的正确调用，嵌套调用，递归调用。6.局部变量和全局变量。7.变量的存储类别（自动，静态，寄存器，外部），变量的作用域和生存期。8.内部函数与外部函数。八、编译预处理1.宏定义：不带参数的宏定义；带参数的宏定义。2.“文件包含”处理。九、指针1.指针与指针变量的概念，指针与地
（1）交换类排序法
交换类排序法是指借助数据元素之间的互相交换进行排序的一种方法。冒泡排序法与快速排序法都属于交换类排序方法。
冒泡排序法是一种最简单的交换类排序方法，它是通过相邻数据元素的交换逐步将线性表变成有序。假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n(n–1)/2。但这个工作量不是必需的，一般情况下要小于这个工作量。
快速排序法也是一种交换类的排序方法，但由于它比冒泡排序法的速度快，因此称之为快速排序法。其关键是对线性表进行分割，以及对各分割出的子表再进行分割。
（2）插入类排序法
插入类排序法主要有简单插入排序法和希尔排序法。
简单插入排序法，是指将无序序列中的各元素依次插入到已经有序的线性表中。在这种排序方法中，每一次比较后最多移掉一个逆序，因此，这种排序方法的效率与冒泡排序法相同。在最坏情况下，简单插入排序需要n(n–1)/2次比较。
希尔排序法对简单插入排序做了较大的改进。它是将整个无序序列分割成若干小的子序列分别进行插入排序。希尔排序的效率与所选取的增量序列有关。在最坏情况下，希尔排序所需要的比较次数为O(n1.5)。
（3）选择类排序
选择类排序主要有简单选择类排序法和堆排序法。
简单选择排序法的基本思想是：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面（这是它应有的位置）；然后对剩下的子表采用同样的方法，直到子表空为止。对于长度为n的线性表，在最坏情况下需要比较n(n–1)/2次。
堆排序法也属于选择类排序法。具有n个元素的序列（h1, h2, …, hn），当且仅当满足条件：
  或  
(i=1, 2, …, n/2）时称之为堆。可见，堆顶元素（即第一个元素）必为最大项。
堆排序的方法对于规模较小的线性表并不适合，但对于较大规模的线性表来说是很有效的。在最坏情况下，堆排序需要比较的次数为O(nlog2n)。
这个你要去好好看看数据结构这本书

上一个：C语言树和二叉树
下一个：C语言高手来呀！！！！