c语言数据结构_第08讲 排序

《c语言数据结构_第08讲 排序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实用数据结构基础第9章排序第9章排序知识点排序的基本概念插入排序方法：直接选择排序、二分插入排序快速排序、选择排序、归并排序各种排序方法性能比较难点堆排序快速排序归并排序要求熟练掌握以下内容：熟悉各种内部排序方法的基本思想和特点各种排序方法的优缺点及性能比较熟悉并掌握一些基本的排序算法了解以下内容：二路归并排序算法堆排序算法第9章目录9-1概述9-2插入排序9-3快速排序9-4选择排序9-5归并排序9-6各种排序方法比较小结实验9排序子系统习题99-1概述1．排序（Sorting）将数据元素（或记录）的任意序列，重新排列成一个按关键字有序

2、（递增或递减）的序列的过程称为排序。2．排序过程中的两种基本操作（1）比较两个关键字值的大小。（2）根据比较结果，移动记录的位置。3．对关键字排序的三个原则（1）关键字值为数值型的，则按键值大小为依据。（2）关键字值为ASCII码，则按键值的内码编排顺序为依据。（3）关键字值为汉字字符串类型，则大多以汉字拼音的字典次序为依据。4．排序方法的稳定和不稳定若对任意的数据元素序列，使用某个排序方法，对它按关键字进行排序，若对原先具有相同键值元素间的位置关系，排序前与排序后保持一致，称此排序方法是稳定的；反之，则称为不稳定的。例如：对数据键值为：

3、5，3，8，3，6，6，排序。若排序后的序列为：3，3，5，6，6，8，其相同键值的元素位置依旧是3在3前，6在6前，与排序前保持一致，则表示这种排序法是稳定的；若排序后的序列为：3，3，5，6，6，8，则表示这种排序法是不稳定的。5．待排序记录的三种存储方式（1）待排序记录存放在地址连续的一组存储单元上。类似于线性表的顺序存储结构。（2）待排序记录存放在静态链表中。记录之间的次序关系由指针指示，排序不需要移动记录。（3）待排序记录存放在一组地址连续的存储单元，同时另设一个指示各个记录存储位置的地址向量，在排序过程中不移动记录本身，而移动

4、地址向量中这些记录的“地址”，在排序结束后，再按照地址向量中的值调整记录的存储位置。6．内排序整个排序过程都在内存进行的排序称为内排序。7．外排序待排序的数据元素量大，以致内存一次不能容纳全部记录，在排序过程中需要对外存进行访问的排序称为外排序。9-2插入排序9-2-1直接插入排序1．基本思想直接插入排序（StraightInsertionSort）是一种最简单的排序方法，它的基本操作是将一个记录插到已排序好的有序表中，从而得到一个新的，记录数增1的有序表。插入前：（1358）[27496]有序无序插入后：（12358）[7496]有序无

5、序2.【例9-1】输入元素序列为：39，28，55，80，75，6，17，45，28按从小到大的序列排序。第一个取39，作第一个假设有序的记录，第二个取28，28<39，则交换。此后，每取来一个记录就与有序表最后一个关键字比较，若大于或等于最后一个关键字，则插入在其后；若小于最后一个关键字，则把取来的记录再与前一个关键字比较……，其过程如图9-1：排序以后，相同关键字元素的28和28与排序前的位置保持一致，即28仍然在28之前，所以直接插入排序方法是稳定的。监视哨（哨兵）的作用：（1）在进入确定插入位置的循环之前，保存了插入值r[i]的副

6、本，避免因记录的移动而丢失r[i]中的内容。（2）使内循环总能够结束，以免循环过程中数组下标越界。3．算法voidInsertsort(){for(i=2;i<=L;i++)//依次插入r[2],r[3],……r[n]{if(R[i].key

7、间效率：向有序表中逐个插入记录的操作，进行了n-1趟，每趟操作分为比较关键码和移动记录，而比较的次数和移动记录的次数取决于待排序列按关键码的初始排列。最好情况下：即待排序列已按关键字有序，每趟操作只需1次比较2次移动。总比较次数=n-1次总移动次数=2(n-1)次最坏情况下：即第j趟操作，插入记录需要同前面的j个记录进行j次关键码比较，移动记录的次数为j+2次。平均情况下：即第j趟操作，插入记录大约同前面的j/2个记录进行关键码比较，移动记录的次数为j/2+2次。直接插入排序的时间复杂度为O(n2)，辅助空间为O（1）。直接插入排序是稳定

8、的排序方法。直接插入排序最适合待排序关键字基本有序的序列。返回9-2-2二分插入排序(BinaryInsertongSort)1．基本思想直接插入算法虽然简单，但当记录数量n很大时，则比较次数