数据结构课程讲义8.pptVIP

§1 内排序 (Sorting)？ 简单地说，排序就是将一组杂乱无章的数据按一定的规律排列起来（递增或递减）。 排序是计算机中经常遇到的操作，通常称为分类或整序。 排序的几个基本概念 数据表(Data List) 待排序的数据对象的有限集合。 关键字(Key) 作为排序依据的数据对象中的属性域。 主关键字 不同的数据对象若关键字互不相同，则这种关键字称为主关键字。 排序的确切定义 使一组任意排列的对象变成一组按关键字线性有序的对象。 用于排序测度的关键字通常称为排序码。 排序的几个基本概念 排序算法的稳定性 判断标准：排序码相同的数据对象在排序过程中是否保持前后次序不变。如 2, 2*,1，排序后若为1, 2*, 2 则该排序方法是不稳定的。 内排序与外排序 区分标准：排序过程是否全部在内存进行。 排序的时间开销 它是衡量算法好坏的最重要的标志。通常用算法执行中的数据比较次数和数据移动次数来衡量。 排序亦称分类，是计算机进行数据处理的一种基本运算，其功能是将一个数据元素的无序序列调整为一个有序序列。目的是达到当计算机中的数据经过排序后，提高工作效率和质量。是在线性表上施加的操作。 排序码就是指作为排序依据的数据项。数据元素可以有多个排序码。 排序的精确定义： 有n个记录（元素）： {R1，R2，R3，………，Rn} 及其对应的排序码序列： {K1，K2，K3，…………Kn} 所确定的1，2，………….n的一种排列p1,p2,p3,……,pn，使得相应的排序码满足非递减（或非递增）关系： Kp1≤Kp2≤Kp3≤……≤Kpn 或 Kp1≥Kp2≥Kp3≥……≥Kpn 即成为 ：{Rp1,Rp2,Rp3,……,Rpn} 自然，不同的排序策略就得到不同的排序过程； 策略相同但排序所采用的排序方法不同，都会有不同的排序算法。 常见的排序策略和方法有： 直接插入排序 shell插入排序（缩小增量排序） 插入策略 二分插入排序 表插入排序 直接交换排序（冒泡排序） 交换策略 快速排序 直接选择排序 选择策略 堆排序 归并策略 分配策略 基数排序 2.1 直接插入排序(Insert Sort) 直接插入排序举例 i (0) (1) (2) (3) (4) (5) temp [21] 25 49 25* 16 08 25 1 [21 25] 49 25* 16 08 49 2 [21 25 49] 25* 16 08 25* 3 [21 25 25* 49] 16 08 16 4 [16 21 25 25* 49] 08 08 5 [08 16 21 25 25* 49] 直接插入排序算法由两重循环组成，对于有n个记录的排序，内循环表明完成一趟排序所需进行的记录关键字间的比较和记录的后移。 若初始时关键字递增有序，这是最好情况。每一趟排序中仅需进行一次关键字的比较，所以总的比较次数为n-1。在while循环之前和之中，至少要移动记录两次，所以总的比较次数为2(n-1)。 若初始时关键字递减有序，这是最坏情况。这时的记录比较和移动次数分别为： 直接插入排序的稳定性 直接插入排序是一种稳定的排序方法。 原理：关键字相同的两个对象，在整个排序过程中，不会通过比较而相互交换。 2.2 希尔(shell)排序 1959年由D.L. Shell提出，又称缩小增量排序(Diminishing-increment sort) 。 基本思想：在插入排序中，只比较相邻的结点，一次比较最多把结点移动一个位置。如果对位置间隔较大距离的结点进行比较，使得结点在比较以后能够一次跨过较大的距离，这样就可以提高排序的速度。 希尔排序的基本过程 希尔排序示例 i