# 基本概念和排序方法的概述

# 排序

将一组杂乱无章的数据按一定规律顺次排列起来，即，将无序序列排列成一个有序序列的运算

# 排序方法分类

# 按存储介质分类

1. 内部排序：数据量不大，数据在内存，无需内外存交换数据
2. 外部排序：数据量较大，数据在外存

# 按比较器的个数分类

1. 串行排序：单机处理
2. 并行排序：多处理器

# 按主要操作分类

1. 比较排序：用比较的方法
   1. 插入排序、交换排序、选择排序、归并排序
2. 基数排序：不比较元素的大小，仅仅根据元素本身的取值确定其有序位置

# 按辅助空间可分为

1. 原地排序：辅助空间用量$O(1)$ 的排序方法
2. 非原地排序：辅助空间用量超过$O(1)$ 的排序方法

# 按稳定性排序

1. 稳定排序：能够使任何数值相等的元素，排序以后相对次序不变
2. 非稳定排序：不是稳定排序的方法

# 按自然性可分为

1. 自然排序：输入数据越有序，排序速度越快的排序方法
2. 非自然排序：不是自然排序的方法

# 插入排序

# 基本思想

每步将一个待排序的对象，按其关键码的大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止

# 直接插入排序

# 定义

采用顺序查找法查找插入位置

# 步骤

1. 普通方式
   1. 复制插入位置
   2. 记录后移，查找插入位置
   3. 插入到正确位置
2. 哨兵
   1. 复制为哨兵
   2. 记录后移，查找插入位置
   3. 插入到正确位置

# 算法

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）

# 基本思想

1. 先将整个待排记录序列分割成若干个子序列，分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序
2. 特点
   1. 缩小增量
   2. 多遍插入排序

# 图解

# 交换排序

# 基本思想

1. 两两比较，如果发生逆序则交换，直接所有记录都排好序为止
2. 交换排序分类
   1. 冒泡排序：$O(n^2)$
   2. 快速排序：$O(n\log_2^n)$

# 冒泡排序

# 基本思想

每次不断将记录两两比较，并按前小后大规则交换

# 快速排序

# 基本思想

1. 任取一个元素为中心
2. 所有比它小的元素一律前放，比它大的元素一律后放，形成左右两个子表
3. 对各个子表重新原则的中心元素并依次规则调整
4. 直到每个子表的元素只剩一个

# 图解

# 选择排序

# 简单选择排序

# 基本思想

在待排序的数据中选出最大（小）的元素放在其最终位置

# 基本操作

1. 首先通过 n-1 次关键字比较，从 n 个记录中找出关键字最小的记录，将它与第一个记录交换
2. 再通过 n-2 次比较，从剩余的 n-1 个记录中找出关键字次小的记录，将它与第二个记录交换
3. 重复上述操作，工进行 n-1 躺排序后，排序结束

# 堆排序

# 堆的定义

堆实质是满足完全二叉树的性质：二叉树中任一非叶子节点均小于（大于）它的孩子节点

# 大根堆小根堆图解

# 堆调整

对一个无序序列返回筛选，就可以得到一个堆，即从一个无序序列建堆的过程就是一个反复筛选的过程

# 归并排序

# 基本思想

将两个或两个以上的有序序列归并成一个有序序列

# 基数排序

# 基本思想

分配 + 收集（模拟按顺序给扑卡牌）

# 基数排序实例

数字范围是有范围的，均有 0-9 这十个数字组成，则只需设置十个箱子，相继按个、十、百... 进行排序