堆排序简介.ppt

代码优化
在编写代码时，可以使用排序算法对数据进行排序，以提高代码执行效率。例如，在处理大量数据时，先对数据进行排序再进行处理可以显著提高处理速度。
01
02
03
04
CHAPTER
排序算法的优化
计数排序
通过统计数组中每个元素的出现次数，将数组分为若干子数组，然后对子数组进行排序，最后合并结果。计数排序适用于整数数组，尤其适用于小范围整数的排序。
基数排序
将数组中的元素按照位数分成若干个子数组，然后对每个子数组进行排序，最后合并结果。基数排序适用于整数和字符串的排序。
将数组分成若干个子数组，对每个子数组进行排序，最后合并结果。归并排序在合并过程中只涉及数据的移动，不涉及交换操作，因此交换次数较少。
归并排序
通过选择一个基准元素，将数组分成两部分，一部分比基准元素小，另一部分比基准元素大，然后递归地对这两部分进行排序。快速排序在内部递归调用时使用“分而治之”的策略，可以减少交换次数。
可读性和可维护性
良好的算法应该易于理解和实现，并且能够方便地进行修改和维护。
时间复杂度
衡量算法执行时间随数据规模增长的速度。常见的时间复杂度有O(n)、O(nlogn)、O(n^2)等。
空间复杂度
衡量算法所需额外空间的大小。常见的空间复杂度有O(1)、O(元素在原始序列中相邻，则在排序后的序列中它们的位置也相邻。稳定的排序算法有冒泡排序、插入排序、归并排序等。
桶排序
插入排序
05
CHAPTER
排序算法的复杂度分析
O(n)：如计数排序、基数排序
O(n^2)：如冒泡排序、插入排序
概念：时间复杂度是衡量排序算法执行时间随数据量增长而增长的速率。
O(nlogn)：如归并排序、快速排序

j j
j
j
ji
ij
ij
ij
i
i
i
二趟排序： 13 4 48 38 27 49 55 65 97 76 Ch8_3.c
希尔排序特点
子序列的构成不是简单的“逐段分割”，而是将相隔某个增 量的记录组成一个子序列 希尔排序可提高排序速度，因为 分组后n值减小，n² 更小，而T(n)=O(n² ),所以T(n)从总体 上看是减小了 关键字较小的记录跳跃式前移，在进行最后一趟增量为1 的插入排序时，序列已基本有序 增量序列取法 无除1以外的公因子 最后一个增量值必须为1
j j j j j j 排序结果：(13 27 38 49 65 76 97)
算法评价
时间复杂度 若待排序记录按关键字从小到大排列(正序) 关键字比较次数： n
1 n 1
i 2
记录移动次数：
2 2(n 1)
i 2
n
若待排序记录按关键字从大到小排列(逆序) n (n 2)(n 1) 关键字比较次数： i
§8.2 交换排序
冒泡排序
排序过程
将第一个记录的关键字与第二个记录的关键字进行比较，若 为逆序r[1].key>r[2].key，则交换；然后比较第二个记录与第 三个记录；依次类推，直至第n-1个记录和第n个记录比较为 止——第一趟冒泡排序，结果关键字最大的记录被安置在最 后一个记录上 对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记 录被安置在第n-1个记录位置 重复上述过程，直到“在一趟排序过程中没有进行过交换记 录的操作”为止
输出：13 27 38 49 50 65
76 97 50 49 38 65 27 13 输出：13 27 38 49 50 65 97 50

}
r[i]=x;
qksort(r,t,j-1);
2021/2/10
qksort(r,j+1,w);
21
}
– 算法评价 • 时间复杂度 – 最好情况（每次总是选到中间值作枢轴） T(n)=O(nlog2n) – 最坏情况（每次总是选到最小或最大元素 作枢轴）T(n)=O(n² )
T(n)=O(n²)
• 根据“寻找”插入位置的方法不同，插入法可分为：直 插排序、二分插入排序、希尔排序。
• (1) 直接插入排序
– 若将一个未排序的元素L[i]插入到已排序的具有i-1个 元素的序列的适当位置，步骤如下：
• a. 从右向左顺序搜索已排序的序列，若已排序序 列中的元素比L[i]大，则后移一个位置，直至找到 一个元素L[j-1](0≤j-1≤i-1)的关键字值比L[i]的关键 字值小；
• 希尔排序可提高排序速度，因为 – 分组后n值减小，n² 更小，而T(n)=O(n² )，所 以T(n)从总体上看是减小了 – 关键字较小的记录跳跃式前移，在进行最后一 趟增量为1的插入排序时，序列已基本有序
• 增量序列取法 – 无除1以外的公因子 – 最后一个增量值必须为1
2021/2/10
14
关键字小，则可分别对这两部分记录进行排序，以达到 整个序列有序。 关键字通常取第一个记录的值为基准值。
– 排序过程：对r[s……t]中记录进行一趟快速排序，附设两 个指针i和j，设基准值记录rp=r[s]，x=rp.key
• 初始时令i=s,j=t
• 首先从j所指位置向前搜索第一个关键字小于x的记录， 并和rp交换
9.3 交换排序
• (0) 基本思想：
– 两两比较待排序的数据元素的关键字，如果发生逆序， 则交换之，直到全部对象都排好序为止。

第二个问题解决方法——筛选
方法：输出堆顶元素之后，以堆中最后一个元素替代之；然 后将根结点值与左、右子树的根结点值进行比较，并与其中 小者进行交换；重复上述操作，直至叶子结点，将得到新的 堆，称这个从堆顶至叶子的调整过程为“筛选”
例 38 50 97 76
13 27 65 49 13 38
97 27 38 50 76
2 (n 4)(n 1) 记录移动次数： (i 1) 2 i 2
i 2 n
若待排序记录是随机的，取平均值 n2 关键字比较次数： T(n)=O(n² ) 4 记录移动次数：
空间复杂度：S(n)=O(1)
n2 4
折半插入排序
排序过程：用折半查找方法确定插入位置的排序叫~
初始时令i=s,j=t 首先从j所指位置向前搜索第一个关键字小于x的记录，并和rp 交换 再从i所指位置起向后搜索，找到第一个关键字大于x的记录， 和rp交换 重复上述两步，直至i==j为止 再分别对两个子序列进行快速排序，直到每个子序列只含有 一个记录为止
x 例 初始关键字： 27 49 i 完成一趟排序： ( 27 38 13 49 65 i 13) 49 97 76 j 97 49 13 j 97 65 49 27 50 j 50)
13 38
76 65 27 49
堆排序：将无序序列建成一个堆，得到关键字最小 （或最大）的记录；输出堆顶的最小（大）值后，使 剩余的n-1个元素重又建成一个堆，则可得到n个元素 的次小值；重复执行，得到一个有序序列，这个过程 叫~ 堆排序需解决的两个问题：
如何由一个无序序列建成一个堆？ 如何在输出堆顶元素之后，调整剩余元素，使之成为一个新 的堆？
按排序所需工作量

数据结构
例： 初始
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) 且分别称之为小顶堆和大顶堆。

选择排序种类： 简单选择排序 树形选择排序 堆排序
2019/9/7
30
10.4.1 简单选择排序
待排记录序列的状态为：
有序序列R[1..i-1] 无序序列 R[i..n]
有序序列中所有记录的关键字均小于无序序列中记 录的关键字，第i趟简单选择排序是从无序序列 R[i..n]的n-i+1记录中选出关键字最小的记录加入 有序序列
2019/9/7
5
排序的类型定义
#define MAXSIZE 20 // 待排序记录的个数
typedef int KeyType;
typedef struct
{ KeyType key;
InfoType otherinfo; ∥记录其它数据域
} RecType;
typedef struct {
RecType r[MAXSIZE+1];
分别进行快速排序：[17] 28 [33] 结束 结束
[51 62] 87 [96] 51 [62] 结束
结束
快速排序后的序列： 17 28 33 51 51 62 87 96
2019/9/7
26
自测题 4 快速排序示例
对下列一组关键字 （46,58,15,45,90,18,10,62） 试写出快速排序的每一趟的排序结果

final↑ ↑first
i=8
[51 51 62 87 96 17 28 33]

final↑ ↑first
2019/9/7
14
希尔(shell )排序
基本思想：从“减小n”和“基本有序”两 方面改进。
将待排序的记录划分成几组，从而减少参 与直接插入排序的数据量，当经过几次分 组排序后，记录的排列已经基本有序，这 个时候再对所有的记录实施直接插入排序。

for(i = 1 ; i <= n ; i++) {
cin >> x; put(x); } for(i = 1 ; i < n ; i++) { x = get(); y = get(); ans += x + y; put(x + y); } cout << ans << endl; }
//建堆，其实直接将数组排序也是建堆方法之一
即：
get和put操作的复杂度均为log2n。所以建堆复杂度为nlog2n。合 并果子时，每次需要从堆中取出两个数，然后再加入一个数，因此一 次合并的复杂度为3log2n，共n-1次。所以整道题目的复杂度是nlog2n。
【参考程序】
#include <iostream> #include <cstdio> using namespace std; int heap_size, n; int heap[30001]; void swap(int &a, int &b) //加&后变量可修改 {
if(heap[now] >= heap[next]) break;
swap(heap[now], heap[next]);
now = next;
}
}
使用C++标准模板库STL（需要头文件<algorithm>）：
void put(int d)
{
heap[++heap_size] = d;
//push_heap(heap + 1, heap + heap_size + 1);

实现“一趟插入排序”可分三步进行： 实现“一趟插入排序”可分三步进行： 三步进行 1．在 有序区 中查找 R[i] 的插入位置， ． 的插入位置， 2．记录后移一个位置； ．记录后移一个位置； 3．将 R[i] 插入（复制）到 相应 的位置上。 ． 插入（复制） 的位置上。
第8页
直接插入排序
R0 初始状态 i =2 i =3 i =4 i =5 76 38
49 } // InsertSort 7趟 i =6 13 13 38 49 65 76 97 27 49 排序 排序过程： 个记录看成是一个有序子序列， 排序过程：先将序列中第 1 个记录看成是一个有序子序列， i =7 27 13 27 38 49 65 76 97 49 个记录开始，逐个进行插入，直至整个序列有序。 然后从第 2 个记录开始，逐个进行插入，直至整个序列有序。 i =8 49 13 27 38 49 49 65 76 97
数据结构(C++语言版)
第1页
目 录
1 2 3 3 4 3 5 3 6 3
第2页
排序的基本概念 插入类排序 交换类排序 选择类排序 归并排序 小结
概念
排序：将数据元素的一个任意序列，重新排列成一个按关键 排序：将数据元素的一个任意序列，重新排列成一个按关键 字有序的序列 的序列。 字有序的序列。 R1, R2, R3, R4, R5, R6, R7, R8 例：将关键字序列：52, 49, 80, 36, 14, 58, 61, 23 将关键字序列： K1, K2, K3, K4, K5, K6, K7, K8 Kp1 ≤Kp2 ≤Kp3 ≤Kp4 ≤Kp5 ≤ Kp6 ≤Kp7 ≤Kp8 调整为：14, 23, 36, 49, 调整为： Rp1, Rp2, Rp3, Rp4, 52, 58, Rp5, Rp6, 61 , 80 Rp7, Rp8

讨论：若记录是链表结构，用直接插入排序行否？折半插入 排序呢？
答：直接插入不仅可行，而且还无需移动元素，时间效率更 高！但链表无法“折半”！
折半插入排序的改进——2-路插入排序见教材P267。 （1）基本思想： P267 （2）举 例：P268 图10.2 （3）算法分析：移动记录的次数约为n2/8
13 20 39 39 42 70 85
i=8
0
1
2
3
4
5
6
7
8
Hj
折半插入排序的算法分析 • 折半查找比顺序查找快，所以折半插入排序
就平均性能来说比直接插入排序要快。
• 在插入第 i 个对象时，需要经过 log2i +1
次关键码比较，才能确定它应插入的位置。 • 折半插入排序是一个稳定的排序方法。
for ( j=i-1；j>=high+1；--j) L.r [j+1] = L.r [j]；// 记录
后移
L.r [high+1] = L.r [0]；
// 插入
} // for
} // BInsertSort
初始
30 13 70 85 39 42 6 20
012345678
i=2 13
30
13
数逐渐变多，由于前面工作的基础，大多数对象已基本有 序，所以排序速度仍然很快。
时间效率： O(n1.25）～O（1.6n1.25）——经验公式
空间效率：O（1）——因为仅占用1个缓冲单元 算法的稳定性：不稳定——因为49*排序后却到了49的前面
希尔排序算法（主程序）
参见教材P272
void ShellSort(SqList &L，int dlta[ ]，int t){