（二十二）数据结构-排序

排序的定义：在重新排列表中的元素，使关键字按照有序递增或者递减
算法的稳定性：（稳定的）关键字相同的元素在排序之后相对位置不变

一、排序的分类

1. 内部排序：排序期间元素全部存放在内存中的排序
2. 外部排序：排序期间元素无法全部同时存放在内存中（数据太多），必须在排序的过程中根据要求不断的在内、外存之间移动的排序

二、插入排序

基本思想：每次将一个待排序的记录按其关键字大小插入前面已经排好序的子序列，直到全部插入完成。插入排序有三种重要的排序算法：直接插入排序、折半排序、希尔排序

2.1直接插入排序

算法思想：顺序查找 找到插入的位置，适用于顺序表、链表

2.2折半排序

折半查找找到应插入的位置，仅使用于顺序表

2.3希尔排序（仅适用于顺序表，不适用于链表）

算法思想：先将待排序表分割成若干形如L[i，i+d，…，i+kd]的“特殊”子表，分别进行直接插入排序。缩小增量d，重复上述过程，直到d=1为止

1. 首先，我们取增量d=2，一共有8个元素，将8/2=4，我们把相距距离为4的看作同一个子表。第一个子表为49（位置1）和76（位置为1+4=5）
   
   
   1. 对这些元素进行直接插入排序
   2. 将出现新的排序顺序结果
      
2. 进行第二趟排序，缩小增量d的值，在之前d1的基础上/2 = 4/2=2，会把相距距离为2的划分为同一个子表
   1. 划分完子表的结果如下
      
   2. 对子表进行插入排序的结果如下
      
3. 第三趟排序，继续缩小d增量的值，在第二趟的基础上/2=1
   1. 此时的序列已经“基本有序” ，只对整个表进行一趟直接插入排序
      
      

2.3.1 重要知识点回顾