# 基本概念和排序方法的概述
# 排序
将一组杂乱无章的数据按一定规律顺次排列起来,即,将无序序列排列成一个有序序列的运算
# 排序方法分类
# 按存储介质分类
- 内部排序:数据量不大,数据在内存,无需内外存交换数据
- 外部排序:数据量较大,数据在外存
# 按比较器的个数分类
- 串行排序:单机处理
- 并行排序:多处理器
# 按主要操作分类
- 比较排序:用比较的方法
- 插入排序、交换排序、选择排序、归并排序
- 基数排序:不比较元素的大小,仅仅根据元素本身的取值确定其有序位置
# 按辅助空间可分为
- 原地排序:辅助空间用量 的排序方法
- 非原地排序:辅助空间用量超过 的排序方法
# 按稳定性排序
- 稳定排序:能够使任何数值相等的元素,排序以后相对次序不变
- 非稳定排序:不是稳定排序的方法
# 按自然性可分为
- 自然排序:输入数据越有序,排序速度越快的排序方法
- 非自然排序:不是自然排序的方法
# 插入排序
# 基本思想
每步将一个待排序的对象,按其关键码的大小,插入到前面已经排好序的一组对象的适当位置上,直到对象全部插入为止
# 直接插入排序
# 定义
采用顺序查找法查找插入位置
# 步骤
- 普通方式
- 复制插入位置
- 记录后移,查找插入位置
- 插入到正确位置
- 哨兵
- 复制为哨兵
- 记录后移,查找插入位置
- 插入到正确位置
# 算法
void InsertSort(SqList &L){ | |
int i,j; | |
for(i = 2; i <= L.length; i++){ | |
if(L.r[i].key < L.r[i-1].key){ | |
L.r[0] = L.r[i]; | |
for(j = i - 1; L.r[0].key < L.r[j].key; --j){ | |
L.r[j+1] = L.r[j]; | |
} | |
L.r[j+1] = L.r[0]; | |
} | |
} | |
} |
# 折半插入排序
# 定义
对于前半部分排序好的部分,进行插入位置查询时,使用折半查找
# 希尔排序(Donald Shell)
# 基本思想
- 先将整个待排记录序列分割成若干个子序列,分别进行直接插入排序,待整个序列中的记录基本有序时,再对全体记录进行一次直接插入排序
- 特点
- 缩小增量
- 多遍插入排序
# 图解
# 交换排序
# 基本思想
- 两两比较,如果发生逆序则交换,直接所有记录都排好序为止
- 交换排序分类
- 冒泡排序:
- 快速排序:
# 冒泡排序
# 基本思想
每次不断将记录两两比较,并按前小后大规则交换
# 快速排序
# 基本思想
- 任取一个元素为中心
- 所有比它小的元素一律前放,比它大的元素一律后放,形成左右两个子表
- 对各个子表重新原则的中心元素并依次规则调整
- 直到每个子表的元素只剩一个
# 图解
# 选择排序
# 简单选择排序
# 基本思想
在待排序的数据中选出最大(小)的元素放在其最终位置
# 基本操作
- 首先通过 n-1 次关键字比较,从 n 个记录中找出关键字最小的记录,将它与第一个记录交换
- 再通过 n-2 次比较,从剩余的 n-1 个记录中找出关键字次小的记录,将它与第二个记录交换
- 重复上述操作,工进行 n-1 躺排序后,排序结束
# 堆排序
# 堆的定义
堆实质是满足完全二叉树的性质:二叉树中任一非叶子节点均小于(大于)它的孩子节点
# 大根堆小根堆图解
# 堆调整
对一个无序序列返回筛选,就可以得到一个堆,即从一个无序序列建堆的过程就是一个反复筛选的过程
# 归并排序
# 基本思想
将两个或两个以上的有序序列归并成一个有序序列
# 基数排序
# 基本思想
分配 + 收集(模拟按顺序给扑卡牌)
# 基数排序实例
数字范围是有范围的,均有 0-9 这十个数字组成,则只需设置十个箱子,相继按个、十、百... 进行排序