第7章数据结构的 排序

Shell排序的性能分析
Shell排序的时间复杂度在O(nlog2n)和O(n2)间， Knuth的 统计结论是，平均比较次数和记录平均移动次数在n1.25与 1.6n1.25之间
Shell排序是一种不稳定的排序方法
最后谈一下delta的取法。 Shell最初的方案是delta=n/2， delta=delta/2，直到delta=1。Knuth的方案是delta=delta/3 +1。其它方案有：都取奇数为好；或delta互质为好等等。 而使用象1, 2, 4, 8, …或1, 3, 6, 9, …这样的增量序列就不太 合适，因为这样会使几个元素多次被分到一组中，从而造 成重复排序，产生大量无用的比较操作
另外，在无序子表中向前移动的过程中，如果没 有交换元素，则说明无序子表已有序，无须再做 排序
24
冒泡排序算法实现
1 void bubble_sort(RecType R[ ], int n) { 2 //待排序元素用一个数组R表示，数组有n个记录
3 int i, j; 4 bool swap=TRUE; //判断无序子表是否已有序的变量
内排序和外排序 按照排序过程中使用内、外存的不 同将排序方法分为内排序和外排序。若待排序记录全 部在内存中，称为内排序；若待排序记录的数量很大， 以致内存一次不能容纳全部记录，在排序过程中需要 进行内、外存交换，称为外排序。本章仅讨论内排序
内排序可分为五大类：插入排序、交换排序、选择排 序、归并排序和基数排序
直接插入排序(straight insert sort) 折半插入排序(binary insert sort) Shell排序(Shell sort)
10
10.2.1 直接插入排序举例

数据结构各章概要数据结构是计算机科学中非常重要的一个学科，其主要研究各种数据的组织方式和操作方法。

善于运用合适的数据结构可以提高算法的效率，并优化程序的性能。

本文将对数据结构的各个章节进行概要介绍，帮助读者了解不同章节的主要内容和应用。

第一章：引论在引论章节，我们将引入数据结构的基本概念和术语，例如什么是数据、数据项、数据对象等等。

同时，还将介绍数据结构的分类和基本操作，如搜索、遍历、插入、删除和排序。

这些基础知识是后续章节的基础。

第二章：线性表线性表是数据结构中最简单、最基本的一种结构。

其特点是数据元素之间的前驱和后继关系非常明确。

线性表可以用数组和链表两种方式实现。

在本章节中，我们将分别介绍顺序表和链表的实现原理、插入、删除、合并以及应用场景。

第三章：栈和队列栈和队列是两种特殊的线性表结构，它们对数据的访问具有限制性。

栈具有“先进后出”的特点，而队列则具有“先进先出”的特点。

在本章节中，我们将介绍栈和队列的实现方式以及常见的应用场景，如递归、表达式求值、广度优先搜索等。

第四章：串串是由零个或多个字符组成的有限序列，其长度可以为零。

在本章节中，我们将介绍串的定义和操作，包括字符串的模式匹配、模式识别和编辑操作。

串的相关算法在文本处理、计算机网络等领域具有广泛的应用。

第五章：数组和广义表数组是一种在内存中以连续方式存储的数据结构，它具有高效的随机访问特性。

广义表是线性表的一种扩展，可以包含表结构、原子结构以及其他广义表。

本章节将介绍数组和广义表的定义、操作和应用。

第六章：树树是一种非线性的数据结构，具有分层次、递归和层次遍历等特点。

在本章节中，我们将介绍树的基本概念、二叉树、树的遍历算法、平衡树以及树的应用，如编译器中的语法树、文件系统的目录结构等。

第七章：图图是一种复杂的非线性数据结构，由顶点集合和边集合组成。

在本章节中，我们将介绍图的各种表示方式，图的遍历算法、最短路径算法以及常用的图算法，如最小生成树算法和拓扑排序。

比较次数 记录移动次数
最好 平均 最坏
n1 (n1)(n4)/4 (n1)(n2)/2
2n2 (n1)(n8)/4 (n1)(n4)/2
优点：算法简单. 缺点：期望和最坏复杂度为 O(n2) . 稳定性：稳定 辅助空间： O(1)
希尔排序(shell)
将记录按下标的一定增量分组，对每组使用直 接插入排序算法排序；
最 坏时间复杂度 排序前记录已按关键词逆序排列，即dj j-1. 总的
比较次数为n1 n(n-1)/2，总的移动次数为 2(n1) n(n-1)/2.
期望时间复杂度
考察分析 j 2 n dj 的期望值。
对于序列 K1，K2，…，Kn ，如果 1 i j n，且 Ki Kj，则称（Ki , Kj）为上述序列的一个反序对.
实际上， j 2 n dj 正好是序列 K1，K2，…，Kn
的反序对个数。反序对的平均个数为 0+ (0+1)/2+ (0+1+2)/3+ (0123)/4(01234)/5 (012345)/6 … (012…n1)/n 01/22/2 3/24/25/2…( n1)/2 n(n1)/4
直接插入排序小结
7.6 .
79
90
90
90
90 四
趟
56
79
79
88
88 完 交
90
56
88
79
79
成替 排上
4
88
56
56
56 序 浮
下
32
4
32
35
35
沉
27
32
27
32
32
排 序

数据结构
例： 初始
49 38 65 97 76 13 27
48
55
4
取d1=5 一趟分组：49 38 65 97 76 13 27
48
55
4
一趟排序：13 27 48 55 4
49 38
65
97
76
取d2=3 13 27 48 55 4 二趟分组：
49 38
65
97
76
二趟排序：13
4
48 38 27
做出相应的调整，那样排序的总体效率会非常高。
• 堆排序(Heap Sort)就是对简单选择排序的一种改进。堆排序 算法是Floyd和Williams在1964年共同发明，同时发明了“堆” 这样的数据结构。
数据结构
堆的定义
一、定义
16 11 9
10 1 2
2
5 4
6
大顶堆
8
1
6 9
小顶堆
数据结构
11 4 12 16 5
• R[0]为监视哨（Sentinel），省略下标越界检查“j>0”：一 旦越界，j=0<1，循环条件R[0]<R[j]不成立，自动控制 while循环的结束。
例：有监视哨，第3趟
0 1 2 3 4 5 6 7 8 9 10 m
初始：
i=3: j=2: j=1: j=0:
49 38 13 76 27 49 38 49 13 76 27 49 13 38 49 13 76 27 49 13 38 49 49 76 27 49 13 38 38 49 76 27 49 13 13 38 49 76 27 49
8
堆的定义
一、定义 • 堆是具有下列性质的完全二叉树：任一结点关键字大于等于 其孩子结点的关键字，称为大顶堆；任一结点关键字小于等 于其孩子结点的关键字，称为小顶堆。 • 将R[1]到R[n]看成完全二叉树的顺序存储结构。根据二叉树 的性质5，如果双亲下标为i，其左右孩子的下标分别为2i和 2i+1. 当且仅当任一R[i]满足以下关系时，称之为堆： R[i] ≤ R[2i]且R[i] ≤ R[2i+1] (1 ≤ i ≤ n/2) 或者 R[i] ≥ R[2i]且R[i] ≥ R[2i+1] (1 ≤ i ≤ n/2) 且分别称之为小顶堆和大顶堆。