页数：28页文件大小：433.7 KB来源： 数据结构-C#语言描述ppt课件
本课件系统讲解内部排序：先区分内排序与外排序，再按插入、交换、选择、归并四条线索依次展开直接插入排序与希尔排序、冒泡排序与快速排序、直接选择排序与堆排序、二路归并排序，逐页图解排序过程并给出各自的时间复杂度，最后结合数据规模给出算法选用建议。
本页为第九章排序封面。本章讲解排序的基本概念，以及插入排序、交换排序、选择排序与归并排序四类内部排序方法。
排序（Sorting）是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为按关键字“有序”的记录序列。
如何进行排序，特别是高效率地进行排序是计算机工作者学习和研究的重要课题之一。本章主要介绍几类内部排序方法的基本思想、排序过程、算法实现。
插入排序（Insertion Sort）的主要思想是不断地将待排序的元素插入到有序序列中，使有序序列不断扩大，直至所有元素都进入有序序列中。
本页演示直接插入排序的一趟插入过程：待排序列为 3、6、5、9、7、1、8、2、4，指针 i 指向当前待插入元素，指针 j 在已排好的有序区中从后向前寻找插入位置，待插入元素先暂存在 temp 中，比它大的元素依次右移，最后把 temp 放回空出的位置。
本页演示改进后的直接插入排序：把待插入元素放到 R[0] 作为哨兵，查找插入位置时不必再判断下标是否越界，只要当前元素大于哨兵就右移，比较到 R[0] 时必然停止。
这一改进减少了每趟排序中的一次越界判断，在数据量较大时能明显节省时间。
希尔排序（Shell Sort）又称为缩小增量排序，是由 D.L.Shell 在 1959 年提出的，它是对直接插入排序的一种改进方法。
直接插入排序法更适合数据量较少的排序，当待排序记录序列接近“正序”时，其时间复杂度也可提高至接近 O(n)。希尔排序正是依据此，对直接插入排序进行改进。其基本思想是将待排序的记录划分成几组，从而减少参与直接插入排序的数据量，当经过几次分组排序后，记录的排列已经基本有序，这时再对所有记录实施直接插入排序。
本页演示希尔排序的第一趟分组：待排序列为 3、6、5、9、7、1、8、2、4，取增量 d=4，则下标相差 4 的元素被划入同一组，各组内分别做直接插入排序，指针 i、j 与暂存单元 temp 在组内移动。
一趟结束后增量逐次缩小，直到 d=1 时对整个序列做最后一次直接插入排序。
希尔排序适用于待排序记录数目较大的情况，在此情况下，希尔排序一般要比直接插入排序快。
1971 年，斯坦福大学的詹姆斯·彼得森和戴维·L·拉塞尔在大量实验的基础上推导出，希尔排序的时间复杂度约为 O(n 的 1.3 次方)。
交换排序（Exchange Sort）的主要思路是在排序过程中，通过对待排序记录序列中元素进行比较，如果发现次序相反，就将存储位置交换来达到排序目的。
本节主要介绍两种交换排序方法：冒泡排序和快速排序。
冒泡排序（Bubble Sort）是一种简单的交换排序方法。它的基本思想是对所有相邻记录进行比较，如果是逆序，则将其交换，最终达到有序。
本页演示冒泡排序的一趟扫描：指针 j 从左到右依次比较相邻的两个元素，指针 i 记录本趟扫描的终点，每发现一对逆序元素就立即交换，一趟结束后最大的元素被推到序列末尾。
冒泡排序法在运行时间方面，待排序记录越接近有序，算法的执行效率就越高，反之，执行效率就越低，它的平均时间复杂度为 O(n 的平方)。
快速排序是由 C.A.R Hoarse 提出并命名的一种排序方法。在各种排序方法中，这种方法对元素之间比较次数较少，因而速度也比较快，被认为是目前最好的排序方法之一。
在 .NET 的多个集合类所使用的 Sort() 方法正是使用快速排序法对集合中的元素进行排序的。
本页演示快速排序的一趟划分：待排序列为 3、6、5、9、7、1、8、2、4，取基准值放入 temp，指针 i 从左向右找大于基准的元素，指针 j 从右向左找小于基准的元素，二者都停住时交换，直到 i 与 j 相遇，最后把基准放回分界位置。
快速排序的平均时间复杂度为 O(nlog2n)。就平均时间而言，快速排序是目前被认为最好的内部排序方法。
但是，如果待排序记录的初始状态有序，快速排序蜕化为冒泡排序，其时间复杂度为 O(n 的平方)。也就是说，排序记录越乱，基准两侧记录数量越接近，排序速度越快；待排序记录越有序，排序速度越慢。
为了避免一趟排序后的记录集中到基准的一侧，可以在快速排序前对序列进行“预处理”，将序列的第一个元素、中间元素和最后一个元素进行对比，取中间的值作为基准值。
选择排序（Selection Sort）是以选择为基础的一种常用排序方法，它的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的记录序列的最后，直到全部排列完为止。
选择排序的方法有很多种，这里只介绍两种最有代表性的方法：直接选择排序和堆排序。
直接选择排序的基本思想是：第一趟从所有的 n 个记录中选取最小的记录放在第一位，第二趟从 n-1 个记录中选取最小的记录放到第二位。以此类推，经过 n-1 趟排序后，整个序列就成为有序序列。
本页演示直接选择排序的一趟选择：待排序列为 3、6、5、9、7、1、8、2、4，指针 i 指向本趟要确定的位置，指针 j 扫描剩余区间，指针 k 记录当前找到的最小关键字所在位置，一趟扫描结束后把 k 处元素与 i 处元素交换。
简单选择排序需要外循环 n-1 趟，在每一趟外循环之中又有一个内循环，内循环要做 n-i 次比较，由此简单选择排序的平均时间复杂度为 O(n 的平方)。
堆排序（Heap Sort）是由 J.Williams 在 1964 年提出的，它是在选择排序的基础上发展起来的，比选择排序的效率要高。
堆：如果将堆看成是一棵完全二叉树，则这棵完全二叉树中的每个非叶子结点的值均不大于（或不小于）其左、右孩子结点的值。由此可知，若一棵完全二叉树是堆，则根结点一定是这棵树的所有结点的最小者或最大者。
非叶子结点的值大于其左、右孩子结点值的堆被称为大根堆；非叶子结点的值小于其左、右孩子结点的值的堆被称为小根堆。图中 (a) 为大根堆，(b) 为小根堆，(c) 因父子大小关系不满足而不是堆。
堆排序的时间，主要由建立初始堆和反复重建堆这两个部分的时间开销构成。堆排序的最坏时间复杂度为 O(nlog2n)。
堆排序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。
归并排序（Merging Sort）是利用“归并”技术来进行的排序，所谓归并是指将两个或两个以上的有序表合并成一个新的有序表。它的基本思想是：将这些有序的子序列进行合并，从而得到有序的序列。
合并是一种常见运算，其方法为比较各子序列的第一个记录，将小者取出作为合并序列的第一个记录，如此继续比较，最终可以得到排序结果。因此，归并排序的基础是合并。
利用二个有序序列的合并来实现归并排序被称为二路归并排序。二路归并排序的基本思想是：如果序列中有 n 个记录，可以先把它看成 n 个子序列（由于只包含一个记录，所以是排好序的）。
将每相邻的两个子序列合并，得到 n/2 个有序子序列，每个子序列包含 2 个记录。继续将这些子序列合并，得到 n/4 个有序子序列。如此反复，直到最后合并成一个有序序列，排序完成。
本页演示二路归并排序的合并过程：初始序列 5、1、7、8、3、2、6、9、4 先看作九个长度为 1 的有序段，第一轮两两合并成长度为 2 的有序段，随后继续两两合并，直到合成一个完整的有序序列。
二路归并排序易于在链表上实现，它的时间复杂度无论是在最好情况下还是在最坏情况下均是 O(nlog2n)，但二路归并排序跟其他排序相比，需要更多的临时空间。
本章介绍了多种排序方法，其中并无绝对好与不好的算法，每种排序方法都有其优缺点，适合于不同的环境。因此在实际应用中，应根据具体情况做出选择。下面提出几点建议供读者参考：
下载地址：{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}