1、五 .综合排序 1、 设计目的 对于数据处理工作，排序是其最基本的运算之一。在当今的计算机系统中，花费在排序上的时间占系统 CPU 运行时间的很大比重（约 20%60%）。为了提高计算机的工作效率，人们提出了各种各样的排序算法，这些算法充分地展示了算法设计的某些重要原则和高超技巧。本设计旨在对一些常用的内部排序算法作深入地探讨和理解，通过比较，评价各算法的优劣。 2、 问题描述 各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直 观感受。 3、 设计要求 (1) 实现基本排序方法：直接插入排序、希尔
2、排序、冒泡、快速排序、直接选择、堆排序； （我们要求至少实现三种算法） (2) 对每种基本排序方法尽量给出改进算法； (3) 利用随机函数产生不少于 100 个随机整数，利用直接插入排序、希尔排序、冒泡、快速排序、直接选择、堆排序等排序方法进行递增排序，统计各算法的关键字比较次数和关键字移动次数； (4) 以菜单的形式组织程序各功能； (5) 至少要用 5 组不同的输入数据作比较，比较的指标为有关键字参加的比较次数和关键字移动次数（关键字交换计为 3 次移 动）； (6) 观察所有实验结果并汇集成表格加以总结。 4、 相关知识介绍 将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序
3、的序列叫排序。排序的目的是为了便于查找和处理，提高数据检索的效率。排序问题是要把若干无序数据元素序列排成一个有序序列。因此排序问题的数据元素集合是线性结构。在这个数据元素集合上也允许存取任意位置的数据元素，所以排序问题的数据结构是线性表。任何算法的实现方法都和算法所处理数据元素的存储结构有关。线性表的存储结构有顺序表和链表两种，因为数组具有随机存取特性，而链表不具备，所以排序 算法基本上是基于顺序表设计的。排序的方法很多，若按待排序记录所在位置可分为外部排序（排序过程中需对外存进行访问的排序）和内部排序（待排序记录存放在内存）；按排序依据的不同原则来看，内部排序又可分为插入排序（直接插入排序、
4、折半插入排序、希尔排序等）、交换排序（冒泡排序、快速排序等）、选择排序（简单选择排序、堆排序）、归并排序（ 2-路归并排序）和基数排序。 因为排序过程常包括两个基本操作：比较两个关键字大小；将记录从一个位置移动到另一个位置，所以我们通过统计各算法的关键字比较次数和关键字移动次数的方法，直观地感受 不同算法的时间复杂度。 5、 课程设计分析 插入排序的基本思想是，每次将一个待排序的记录按其关键字的大小插入到前面已经排好序的有序序列中的适当位置，直到全部记录插入完成为止。（ 1）直接插入排序是一种简单的排序方法，它的基本思想是将待插入记录 Ri与有序区的记录 Rj从右向左 (j=i-1,i-2 1
5、)比较，若 Rj Ri则 Rj右移一个位置到 Rj+1；否则，将 Ri插入到 j+1 处。在改进算法中引进附加记录 R0称为监视哨，其作用有两个：在进入查找（插入位置）循环之前，它保存了 Ri的副本， 保证不至于因记录后移而丢失 Ri的内容；在查找循环中，避免检测下标变量 j 是否越界，从而减少算法运行时间。（ 2）希尔排序的排序过程是先取一个正整数 d1n，把所有相隔 d1 的记录放一组，组内进行直接插入排序；然后取 d2d1，重复上述分组和排序操作；直至 di=1，即所有记录放进一个组中排序为止。该算法的执行时间依赖于增量序列（ d1,d2, di）的选择，好的增量序列具有的共同特征是：最
6、后一个增量是必须为 1，并应该尽量避免序列中的值（尤其是乡邻的值）互为倍数的情况。不妨用下列算式计算增量 d=d/3+1(d 初始值为 n)。 交换排序主要通过记录间关键字的比较与存储位置的交换来达到排序的目的，其特点是将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。应用交换排序思想的主要排序方法有冒泡排序和快速排序。（ 1）冒泡算法需要 n 1 趟排序，在算法中可作如下改进：设置一个布尔量 exchange，在每趟排序前，先将其值设为 FALSE；若在排序过程中发生了交换，则将其置为 TRUE；若在某趟排序中未发现 exchange 变化，则终止整个算法。 （ 2）快速排序
7、的基本思想是通过一趟排序，将待排序记录分割成独立的两部分，其中 一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序，就平均时间而言，快速排序是目前被认为最好的一种内部排序。 选择排序是的基本思想是，每一趟处理都是在 n-i+1(i=1,2 ,n-1)个记录中选择关键字最小的记录与其最后对应位置的记录交换，作为有序序列中的第 i 个记录。选择排序中常用的方法有直接选择排序和堆排序。 （ 1） 直接选择排序的排序过程：首先通过 n-1 次关键字比较，从 n 个记录中找出关键字最小的记录（用 k 指示），将它与第一个记录交换；再通过 n-2 次比较，从剩 余的 n-1 个记录中找出关键字次小的记录，将它与第二个记录交换；重复上述操作，共进行 n-1 趟排序后，排序结束。 堆的定义： n 个元素的序列 (k1,k2, kn)，当且仅当满足下列关系时，称之为堆。
