青岛大学数据结构与算法——第8章

一 概述

• 排序概述
• 插入排序
• 交换排序
• 选择排序
• 归并排序
• 基数排序

二 排序概述(分类)

2.1 存储介质

内部和外部

2.2 比较器个数

串行和并行

2.3 操作

• 比较排序
• 基数排序

2.4 辅助空间

• 原地排序
• 非原地排序

2.5 稳定性

• 稳定排序
• 非稳定排序

2.6 自然性

• 自然排序
• 非自然排序

三 插入排序

• 直接插入排序：直接插入排序+哨兵
• 折半插入排序
• 希尔排序：分成若干个子序列、直接插入排序、增量序列

四 交换排序

4.1 冒泡排序

前后交换

4.2 快速排序

• 首元素作为中心
• 小的左边，大的放右边
• 递归，剩1

五 选择排序

5.1 简单选择排序

选择最小(大)放在首位

5.2 堆排序

大根堆和小根堆

六 归并排序

2个-归并成1个排序

七 基数排序

• 思想：分配+收集、关键字k放在第k个箱子里、个/十/百
• 桶排序/箱排序
• 示例：1w人按照生日排序

八 图示