目录

排序分类：（本章目录）

按数据存储介质：（学习内容）

内部排序：

外部排序：

按比较器个数：（学习内容）

串行排序：

并行排序：

按主要操作：（学习内容、里面的排序都会重点学）

比较排序：

基数排序：

按辅助空间：

原地排序：

非原地排序：

按稳定性：

稳定排序：

 非稳定排序：

按自然性：

插入排序

前置条件：

1. 直接插入排序

思绪脉络如下：

排序分类：（本章目录）

按数据存储介质：（学习内容）

内部排序：

数据量不大、数据在内存，无需内外存交换数据

外部排序：

数据量较大、数据在外存（文件排序）

外存排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，比较复杂

数据在内存当中放不下:

在内存当中排序一部分，排序完了以后把这些数据放进外存

在从外存当中再拿来一部分，在来进行（新一轮的）排序

按比较器个数：（学习内容）

串行排序：

单处理机（同一时刻比较一对元素）

并行排序：

多处理机（同一时刻比较多对元素）

按主要操作：（学习内容、里面的排序都会重点学）

比较排序：

插入排序、交换排序、选择排序、归并排序

基数排序：

不比较元素大小，仅根据元素本身的取值确定其有序位置

按辅助空间：

原地排序：

辅助空间用量为O(1)，与参加排序的数据量大小无关

非原地排序：

辅助空间用量超过O(1)，与参加排序的数据量大小有关

按稳定性：

稳定排序：

能使任何数值相等的元素，排序后相对次序不变

 非稳定排序：

数值相等的元素，排序后相对次序变化

按自然性：

自然排序：

输入数据越有序，排序的速度越快

非自然排序：

输入数据越有序，排序的速度越慢

插入排序

前置条件：

存储结构：以顺序表存储

#include<iostream>
using namespace std;

#define MAXSIZE 20  //记录最大个数
typedef int KeyType;  //关键字类型

typedef int InfoType;

//定义每个记录（数据元素）的结构
struct RecType
    //Record Type：每条记录的类型
{
    KeyType key;  //关键字
    InfoType otherinfo;  //其他数据项
};

struct SqList 
    //顺序表(的)结构
{
    RecType r[MAXSIZE + 1]; 
    //类型为【记录类型】的数组
    //r[0]一般做哨兵或缓冲区
    int length;  //顺序表长度
};

int main()
{

}

1. 直接插入排序

根据PPT，整理出

思绪脉络如下：

当然了，这里的“16”其实也只是一个虚指，他指向（代表）我们所有用来和7对比的数字（对象） 

根据PPT第23页所示意的，显然：

字母 i 用来表示的，是：每次循环之前有序表（顺序表）的队尾（序列尾部）

用字母 j 来表示（完成）“插入”的一整个流程/操作

再（又）根据PPT第27所提醒的，以及基于我们前面查找算法的前车之鉴：

我们这里需要使用哨兵

最终整理出程序的基本框架如下：

补充：加哨兵

对于诸多要插入的元素：
设立：

指针 i 指向顺序/有序序列队尾；
指针 j 指向新元素：

注：

原来设计的算法没有考虑到我们可以使用哨兵的便利性；
现在，我们已经不需要特别设立一个指针指向新插入的元素，只需要把新插入的元素放到哨兵里即可

那么现在，我们就确定了：

• 把要新插入的元素放到哨兵（位序为0的位置）里
•  j 指向我们在有序序列里的、拿来和新插入的元素比较的元素（的位置）

• 比较哨兵（位序为0的）元素和指针 j 指向的元素

1. 若大于等于：（哨兵元素大于等于指针 j 指向的元素）
   【交换元素】

   把所有 j 及 j 之后有序序列的元素全部往后移动一位

   （因为要插入的新元素已经放在哨兵里面了，我们不用担心后退一位会不会有数据丢失的影响）

   把哨兵元素插入到指针 j指向的位置

   注意：不要忘了（i++）！！！
    

2. 若小于：（哨兵元素小于指针 j 指向的元素）
   【继续比较，和前面一位比较】

   j--;

3. i++