《数据结构（C语言版）》教案 第7章 排序（电子版）.doc

第7章 排序 本章教学提要 教学重点：排序的概念和评价方法 选择排序　 起泡排序 插入排序 快速分类 教学难点：希尔排序 利用二叉树进行插入排序 快速分类 合并排序与外部排序 本章教学内容 7．1排序的有关概念和术语 排序又叫做分类（sorting），排序是把一批数据按其关键字的先后顺序排列的过程。 评价排序特点的指标：排序过程中比较的次数和移动的次数；排序需要使用的存储空间；稳定性。 一种排序方法如果对于关键字相同的数据可以保证排序后不改变原来的先后顺序（原来在前面的排序后还在前面）就称其为稳定的排序方法，否则就是不稳定的。 7．2选择排序　 选择排序的过程：最初将所有n个数据作为“待选择序列”，同时建立起一个空的“选择结果序列”，第１轮在待选序列中选出一个关键字最大的数据，将它追加到结果序列中（在尾部插入），并将它从待选序列中删除。再进行第2轮选择，从待选序列的n-１个数据中找到最大关键字的数据（在n个数据中这是第2大的），再追加到结果序列中并从待选序列中将其删除，…，直到第n-1轮在2个数据的待选序列中选出最大的，然后追加并删除，剩余的１项数据直接追加到结果序列中排序就完成了。 7．3堆排序 堆排序就是利用一种叫做堆的逻辑结构进行的选择排序。所谓堆的存储结构可以用一维数组来表示：在a数组中，如果对任意0≤i≤(n/2-1)都有a[i]≤a[2i+1]，且当a[2i+2]n时有a[i]≤a[2i+2]的条件成立，我们就称a数组为堆。 7．4起泡排序 实施的步骤：每轮从a[0]到a[n-2]查找哪个a[i]比a[i+1]小，如果找到了这样的相邻反序就交换这两个变量（这就好比一个气泡向上升了一步）, 一轮完成并不能说排序已经完成，一轮轮地比较下去，直到某轮没有发现反序，所有的相邻反序就消灭完了。 7．5 插入排序 插入排序的步骤：由一轮轮的插入构成的。每轮插入都是先用待插入数据在一个原已有序的表中查找插入位置（在此位置插入后，表仍保持有序），然后再将此数据插入到找到的位置，这样作无疑得到多了一个数据的有序表。 7．6 移动最少和比较最少的插入排序 减少比较次数和移动次数是优化排序、提高效率的主要方向。 使用链表这种线性结构来存储待排序数据，插入的操作一定会简单得多，只需要在待插序列中删除当前的待插节点而把它插入到有序列中就行了。 我们力求找一种查找和插入次数都很少的插入法，希尔分类就是这样一种计算复杂性很低的插入算法,但希尔分类不具有稳定性。 7．7利用二叉树进行插入排序 建立排序二叉树的过程：从这个树的根节点（刚开始此节点为空）开始，用待插节点和树上的一些节点依次比较，以查找到其在树上的插入位置。我们称正在与待插节点比较的节点为当前节点。如果待插节点的数据大于当前节点的数据就用当前节点的左子节点代替当前节点进行下一次比较，否则用其右子节点代替当前节点进行下一次从比较，每比一次，当前节点就会走到下面一层，直到某次当前节点为空时，就把待插节点插入到当前空节点的位置上，即让原指向当前空节点的指针指向待插节点，这次插入就完成了。 7．8快速分类 快速分类：第一步的目标是得到一个序列和，其中包含这样一个元素a[y]，对于任何jy肯定都有a[j]≥a[y]，而对于任何ky都有a[y]≥a[k](0≤yn)，有了这样一个中间结果，第二步就可以分别对y两边的序列排序，排序的策略还可以使用上面的第一步对每个子序列进一步分割，不断细分下去直到序列中只有一项数据甚至没有数据时得到的子序列当然就是有序的，而所有这些无需再分的有序子序列合成的就是最终的排序结果。 7．9合并排序与外部排序 上一节的快速分类是不断对待排序列进行一分为二的处理，直分到每个序列最多只有１个数据时就不需再排序了。反过来思考，我们也可以认为整个待排序列中的每个数据都是一个已经有序的序列（在插入排序时我们就曾经这样考虑过），我们要做的只是将这些已经有序的序列两两合并为若干个所含数据更多的有序列（这种思路我们在希尔分类中也是熟悉的），每轮合并将使有序列的个数大约减少一半，而每个有序列的数据个数大约增加一倍。直合并到只有一个有序列时排序自然就完成了。这就是合并排序的总体过程。 外部排序：步骤是先选择一个内部排序方法，根据内存所能容纳的数据量和此内部排序的空间占用情况估算出一次能在内存中排序的最大数据量。 ７．10多关键字排序 所谓低关键字优先排序又叫做基数排序。它先按最低位的关键字（即排序关键字的最低位，例如对自然数而言是个位）分成若干个线性表，然后按从大到小的顺序将这些按最低关键字分类的线性表收集到一个统一的线性表中，虽然每个分类得到的表内并没有顺序，但收集这个表时也要依此表当时的排列次序进行。第二轮再按次低位的关键字的不同依数据在统一的线性表中的排列顺序把数据又分成若干