数据结构课程讲义8ppt课件

Knuth的统计结论是，平均比较次数和 对象平均移动次数在n1.25 与1.6n1.25之间。
希尔排序的稳定性
希尔排序是一种不稳定的排序方法。 如序列 3 2 2* 5
§3 交换排序
基本原理：每一次两两比较待排序的记录 的排序码，只要是逆序的记录对，则进行 交换，直到所有的逆序对都交换完为止。
for (i=1;i<n;i++) { temp＝R[i]; j＝i-1; while (j>=0&&temp.key<R[j].key) {R[j+1]＝R[j];j++;} R[j+1]＝temp; }
}
算法中引入附加记录temp的作用：是进入 查找循环之前，它保存了R[i]的副本，使得 不至于因记录的后移而丢失R[i]中的内容。
合。
关键字(Key) 作为排序依据的数据对象中的属性
域。
主关键字 不同的数据对象若关键字互不相同，则
这种关键字称为主关键字。
排序的确切定义 使一组任意排列的对象变成一
组按关键字线性有序的对象。 用于排序测度的关键字通常称为排序码。
排序的几个基本概念
排序算法的稳定性 判断标准：排序码相同的数据对
评价排序算法好坏的标准主要有两条：算法 执行所需要的时间和所需要的附加空间。 另外，算法本身的复杂程度也是需要考虑 的一个因素。
排序算法所需要的附加空间一般都不大，矛 盾并不突出。而排序是一种经常执行的一 种运算，往往属于系统的核心部分，因此 排序的时间开销是算法好坏的最重要的标 志。
– 排序亦称分类，是计算机进行数据处理的一 种基本运算，其功能是将一个数据元素的无 序序列调整为一个有序序列。目的是达到当 计算机中的数据经过排序后，提高工作效率
datatype other; } rectype; rectype R[n];
其中n为记录总数加1
–§2 插入排序
基本原理，每步将一个待排序的 对象，按其关键字大小，插入到前面 已经排好序的一组对象适当位置上， 直到对象全部插入为止。
直接插入排序(Insert Sort) 希尔排序(Shell Sort)
概述 插入排序 交换排序 选择排序 归并排序 分配排序 外排序
§1 内排序 (Sorting)？
简单地说，排序就是将一组杂乱无章的数 据按一定的规律排列起来（递增或递减）。
排序是计算机中经常遇到的操作，通常称 为分类或整序。
排序的几个基本概念
数据表(Data List) 待排序的数据对象的有限集
• 然后，又从R[0]到R[n-2]中又进行一趟交换 冒泡，这样一直进行下去，直到最后一个元 素R[0]或某一趟没有交换元素为止。
冒泡排序示例
i (0) (1) (2) (3) (4) (5) 21 25 49 25* 16 08
1 08 21 25 49 25* 16 2 08 16 21 25 49 25* 3 08 16 21 25 25* 49 4 08 16 21 25 25* 49
象在排序过程中是否保持前后次序不变。如 2, 2*,1， 排序后若为1, 2*, 2 则该排序方法是不稳定的。
内排序与外排序 区分标准：排序过程是否全部在
内存进行。
排序的时间开销 它是衡量算法好坏的最重要的标
志。通常用算法执行中的数据比较次数和数据移动 次数来衡量。
排序的方法有很多，但简单地判断那一种算 法最好，以便能够普遍序算法由两重循环组成，对于有n 个记录的排序，内循环表明完成一趟排序所需 进行的记录关键字间的比较和记录的后移。
若初始时关键字递增有序，这是最好情况。每 一趟排序中仅需进行一次关键字的比较，所以 总的比较次数为n-1。在while循环之前和之中， 至少要移动记录两次，所以总的比较次数为 2(n-1)。
08 16 21 25* 25 49
希尔排序算法
rectype R[n+d1];
int d[t]; do
SHELLSORT(rectype R[],int d[]){ h＝d[k];
{ int i,j,k,h;
for (i=h+dl;i<n+dl;i++)
rectype temp;
{ temp＝R[i];
n1
比较次数 的 (最 ni)大 n(n值 1)/2O(n2) i1 n1
移动次数 的 3最 (ni大 )3n值 (n1)/2O(n2) i1
冒泡排序方法是稳定的。
3.2 快速排序
快速排序的基本思想
在当前无序区R[l]到R[h]任意取出一个元素作 为比较的“基准”，以此为基准将当前的无 序序列划分为两个部分： 一部分元素中所有的元素排序码都小于基准 元素； 另一部分元素中所有的元素排序码都大于基 准元素，则基准元素所在的位置就是该元素 排序的最终位置； 然后同法依次对两部分元素进行分划，继续 进行下去，直到得到一个有序序列为止。
两种常见的交换排序
冒泡排序(Bubble Sort) 快速排序(Quick Sort)
3. 1 冒泡排序
冒泡排序的基本思想
• 首先依序比较n个待排序记录的一端开始， 依次两两比较排序码，只要是逆序，则交换， 这样完成一趟交换排序，结果就是将最大 （或最小）的记录交换到最后面（或最前 面）；
希尔排序的基本过程
设待排序的对象序列有n个对象， 首先取一个整数gap<n作为间隔，将全 部对象分为gap个子序列，所有距离为 gap的对象放在同一个序列中，在每一 个子序列中分别施行直接插入排序，然 后缩小间隔gap，如取gap=gap/2，重 复上述的子序列划分和排序工作，直到 最后取gap为1为止。
若初始时关键字递减有序，这是最坏情况。这 时的记录比较和移动次数分别为：
n
比较次数的 i最 (n大 2)n (值 1)/2O(n2) i2
n
移动次数的 (i最 12大 )(n值 1)n (4)/2O(n2) i2
直接插入排序的稳定性
直接插入排序是一种稳定的排序方 法。
冒泡排序算法
•void bubblesort(R[])
• { for(i=0;i<n-2;i++)
• { flag=1;
•
for(j=n-1;j>=i;j++)
•
if (R[j+1].key<R[j].key)
•
{ t=R[j+1];
•
R[j+1]=R[j];
•
R[j]=t;
•
Flag=0; }
•
原理：关键字相同的两个对象，在 整个排序过程中，不会通过比较而 相互交换。
2.2 希尔(shell)排序
1959年由D.L. Shell提出，又称缩小 增量排序(Diminishing-increment sort) 。
基本思想：在插入排序中，只比较相 邻的结点，一次比较最多把结点移动 一个位置。如果对位置间隔较大距离 的结点进行比较，使得结点在比较以 后能够一次跨过较大的距离，这样就 可以提高排序的速度。
–
shell插入排序（缩小增量排序）
– 插入策略 二分插入排序
–
表插入排序
–
直接交换排序（冒泡排序）
– 交换策略
–
快速排序
–
直接选择排序
– 选择策略
–
堆排序
– 归并策略
– 分配策略 基数排序
为简单起见，数据的存储结构采用记 录数组形式。记录数组的类型说明如下：
typedef struct { keytype key;
希尔排序中gap的取法
• Shell最初的方案是 gap= n/2, gap=gap/2，直到gap=1.
• Knuth的方案是gap = gap/3+1 • 其它方案有：都取奇数为好；或
gap互质为好等等。
希尔排序的时间复杂度
对希尔排序的复杂度的分析很困难，在 特定情况下可以准确地估算关键字的比 较和对象移动次数，但是考虑到与增量 之间的依赖关系，并要给出完整的数学 分析，目前还做不到。
• 然后其余的记录同法进行两两比较，每一趟 都将较大（小）元素交换到最后（前）面， 一直进行下去，直到最后一个记录排完或没 有要交换的元素的时候为止。
3. 1 ，冒泡排序
冒泡排序的基本过程
• 首先从R[0]到R[n-1]对n个元素比较其排序码， 对逆序元素进行交换，完成一趟排序时，将 排序码值最到的元素几交换到最后一个位置， 即R[n-1]，该过程相当于一趟冒泡；
希尔排序示例
i (0) (1) (2) (3) (4) (5) gap
21 25 49 25* 16 08
1 21 - - 25*
3
25 - - 16
49 - - 08
21 16 08 25* 25 49
2 21 - 08 - 25
2
16 - 25* - 49
08 16 21 25* 25 49
3 08 16 21 25* 25 49 1
2.1 直接插入排序(Insert Sort)
基本思想：当插入第i个对象时， 前面的V[0],V[1],…,V[i-1]已经排好序， 此时，用v[i]的关键字与V[i-1], V[i2],…的关键字顺序进行比较，找到插 入位置即将V[i]插入，原来位置上对 象向后顺移。
直接插入排序举例
i (0) (1) (2) (3) (4) (5) temp [21] 25 49 25* 16 08 25
– Kp1≤Kp2≤Kp3≤……≤Kpn – 或 Kp1≥Kp2≥Kp3≥……≥Kpn – 即成为 ：{Rp1,Rp2,Rp3,……,Rpn} – 自然，不同的排序策略就得到不同的 排序过程； – 策略相同但排序所采用的排序方法不 同，都会有不同的排序算法。 – 常见的排序策略和方法有：