【数据结构】排序：插入排序（直接插入排序、希尔排序、折半插入排序、2-路插入排序等）详解与实现（C++）

刺骨的言语ヽ痛彻心扉 2021-12-09 23:51 192阅读 0赞

\#笔记整理

***内部排序分类目录：***  
***-[\->插入排序][-]**  
\- [交换排序][Link 1]  
\- [选择排序][Link 2]  
\- [归并排序][Link 3]  
\- 计数排序*

### 插入排序：(Insertion Sort) ###

插入排序的基本思想是：每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子表中的适当位置,直到全部记录插入完成为止。

**共有5种插入排序方法：**  
(1) 直接插入排序;  
(2) 折半插入排序;  
(3) 2-路插入排序;  
(4) 表插入排序;  
(5) 希尔排序。

##### （1）直接插入排序（Straight Insertion Sort）： #####

一种最简单的排序方法，它的思路是将待插记录逐一与有序部分进行比较以确定插入的位置。

**算法C++实现如下：**

// 直接插入排序法，对容器 nums 进行排序
        void sInsertion(vector<int> &nums){
        
            int len = nums.size();
    
            for(int i = 1; i < len; i++){
                       // 以第一个数（nums[0]）为已排好序的部分，将之后的记录进行插入
                if(nums[i] < nums[i-1]){
        
                    int temp = nums[i];                 // 临时变量，用于存储 nums[i]
                    int j = i - 2;
                    nums[i]  = nums[i-1];
    
                    while(j >= 0 && temp < nums[j]){
            // 从后往前，寻找 temp 应插入的位置
                        nums[j+1] = nums[j];            // 记录后移
                        j--;
                    }
                    nums[j+1] = temp;                   // 插入正确的位置
                }
            }
        }

[github源码][github]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]  
直接插入排序所需进行关键字间的比较次数和记录移动次数约为： n 2 / 4 n^2 / 4 n2/4，  
算法时间复杂度为： O ( n 2 ) O(n^2) O(n2)。

**直接插入排序是一个稳定的排序方法。**

#### (2) 折半插入排序（Binary Insertion Sort） ####

先找出有序部分中位于中间的记录，与待插记录做比较，每比较一次，就可将有序部分的一半记录排除而不需比较，在数据量大时效率很高。

**算法实现如下：**

// 折半插入排序法，对容器或数组nums进行排序
        void bInsertSort(vector<int> &nums){
        
            int len = nums.size();
    
            for(int i = 1; i < len; i++){
        
                int temp = nums[i];
                int low = 0, high = i - 1;
    
                while(low <= high){
                         // 寻找 0 ~ i-1 中， nums[i]应插入的位置
                    int m = (low + high) / 2;
                    if(nums[m] > temp){
                     // 插入位置在低半区
                        high = m - 1;
                    }else {
        
                        low  = m + 1;               // 插入位置在高半区
                    }
                }
    
                for(int j = i - 1; j >= low; j--){
          // 记录后移，插入位置为 high+1 或 low
                    nums[j+1] = nums[j];
                }
                nums[low] = temp;                   // 插入
            }
        }

[github源码][github]  
![在这里插入图片描述][20190714221124361.png]  
**折半插入排序的时间复杂度为  O ( n 2 ) O(n^2) O(n2)。  
和直接插入排序相比，仅减少了记录之间的比较次数，记录的移动次数不变。因此，时间复杂度变化不大。**

**折半插入排序是一个稳定的排序方法。**

#### (3) 2-路插入排序： ####

是在折半插入排序的基础上再进行改进的算法，其目的是减少排序过程中移动记录的次数。但为此需要 n 个记录的辅助空间。  
先找出有序部分中位于中间的记录，与待插记录做比较，若插在前半部分，则把待插位置前面的记录向前移（一路），反之，把后面的数据向后移（另一路），这样可以减少移动次数（移动的记录少于有序部分记录的二分之一），但需要额外的数组。  
**算法思路：**  
假设原数组为 nums，另设一个相同类型的数组 d，先将 nums\[0\] 赋值给 d\[0\]，并将 d\[0\] 看成是在排好序的序列中处于中间位置的记录，然后从 nums\[1\] 起一次插入到 d\[1\] 之前或之后的有序序列中。先将待插记录和 d\[0\] 做比较，若小于 d\[0\]，则插入 d\[0\] 之前的有序表中；反之，将其插入 d\[0\] 之后的有序表中。在实现算法时，可将 d 看成一个循环向量（循环数组），并设 first 和 final 分别指向排序过程中得到的有序序列中的第一个记录和最后一个记录在 d 中的位置。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 1]

**算法实现如下：**

// 二路插入排序法，对容器或数组nums进行排序
        void p2_InsertSort(vector<int> &nums){
        
            int len = nums.size();
            int i, j, first, last, mid;
            vector<int> d;
            d.resize(len);          // 生成 len 个记录的临时空间
            d[0] = nums[0];
            first = last = 0;       // first和last分别指示 d 中排好序的记录的第一个和最后一个位置
    
            for(i = 1; i < len; i++){
        
                if(first > last){
        
                    j = len;        // j 是调整系数
                }else{
        
                    j = 0;
                }
                mid = ( (first + last + j) / 2 ) % len;  // d 的中间记录的位置
                if(nums[i] < d[mid]){
                            // -- 待插记录应插在 d 的前半部分
                    j = first;                           // j 指向 d 的第一个记录
                    first = (first - 1 + len) % len;     // first 前移，取余是为了实现循环数组效果
                    while(nums[i] > d[j]){
                       // 待插记录大于 j 所指记录
                        d[(j - 1 + len) % len] = d[j];   // j 所指记录前移，取余是为了实现循环数组效果
                        j = (j + 1) % len;               // j 指向下一个记录
                    }
                    d[(j - 1 + len) % len] = nums[i];    // 移动结束，待插记录插在[j]前
                }else{
                                           // -- 待插记录应插在 d 的后半部分
                    j = last;                            // j 指向当前的最后一个记录
                    last++;                              // last后移， 指向插入后的最后一个记录
                    while(nums[i] < d[j]){
                       // 待插记录小于 j 所指记录
                        d[(j + 1 ) % len] = d[j];        // j 所指记录后移
                        j = (j - 1 + len) % len;         // j 指向上一个记录
                    }
                    d[(j + 1) % len] = nums[i];          // 待插记录不小于 j 所指记录，插在 j 后
                }// end else
            }// end for
            for(i = 0; i < len; i++){
                            // 把在 d 中排好序的记录依次赋给nums
                nums[i] = d[(first + i) % len];
            }
        }

[github源码][github]

**算法分析：**  
\- 为了减少记录的移动次数，需n个记录的辅助空间。  
\- 移动记录的次数约为 ( n 2 ) / 8 (n^2)/8 (n2)/8。  
\- 2-路插入排序的时间复杂度为  O ( n 2 ) O(n^2) O(n2)。

**2-路插入排序是一个稳定的排序方法。**

#### (4) 表插入排序（该算法不常用，先简单介绍一下） ####

表插入排序是求出一个有序链表，其基本操作仍是将一个记录插入到已排好序的有序表中。和直接插入排序相比，不同之处是以修改  2 n 2n 2n 次指针值代替移动记录，排序过程中所需进行的关键字间的比较次数相同。因此，表插入排序的时间复杂度仍是  O ( n 2 ) O(n^2) O(n2)。  
由于表插入排序的结果只是求得一个有序链表，则只能对它进行顺序查找，不能进行随机查找，为了能实现有序表的折半查找，尚需对记录进行重新排列。

#### (5) 希尔排序（Shell’s Sort） ####

希尔排序又称 **缩小增量排序（Diminishing Increment Sort）**，是 D.L.Shell 于1959年提出的，它也是一种属插入排序类的方法，但是在时间效率上较前述几种排序方法有较大的改进，在这之前排序算法的时间复杂度基本都是 O ( n 2 ) O(n^2) O(n2)，希尔排序算法是突破这个时间复杂度的第一批算法之一。  
在直接插入排序中，当记录本身就是基本有序的或者记录总数较少时，插入排序还是很高效的。希尔排序正式从这两点出发，对直接插入排序进行改进得到的一种插入排序方法。  
**算法思路：**  
待排记录“基本有序”。  
先将整个待排序列分割成若干子序列分别进行直接插入排序，待整个序列“基本有序”时，再对全体序列进行一次直接插入排序。  
子序列的构成不是简单地“逐段分割”，而是将相隔某个“增量”的记录组成一个子序列然后进行排序。  
**过程示例图：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 2]  
**算法实现：**

// 希尔排序法，对容器或数组nums进行排序
        void shellSort(vector<int> &nums){
        
            int len = nums.size();
            int gap = len;          // 增量，初始设为len
    
            do{
        
                gap = gap/3 + 1;    // 计算增量，形成增量序列
                for(int i = gap; i < len; i++){
        
                    if(nums[i] < nums[i-gap]){
                       // 当 nums[i] 比前一个记录小时
                        int j = i - gap;
                        while(j >= 0 && nums[i] < nums[j]){
          // 继续与前面的其他记录相比较（相距同一增量的其他记录），确定nums[i]应插入（交换）的位置
                            nums[j + gap] = nums[j];         // 大的记录后移
                            j -= gap;
                        }
                        nums[j + gap] = nums[i];             // 插入
                    }
                }
            }while(gap > 1);
        }

[github源码][github]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 3]

**由于记录是跳跃式的移动，因此希尔排序不是一种稳定的排序算法。**

部分内容来源：

1.  《数据结构（C语言版）》----严蔚敏
2.  《数据结构》课堂教学ppt ---- 刘立芳
3.  《数据结构算法与解析（STL版）》 ---- 高一凡
4.  《大话数据结构》 ---- 程杰
5.  《挑战程序设计竞赛2：算法和数据结构》 ---- 渡部有隆

[-]: https://steve.blog.csdn.net/article/details/95931848
[Link 1]: https://steve.blog.csdn.net/article/details/95934166
[Link 2]: https://steve.blog.csdn.net/article/details/95935599
[Link 3]: https://steve.blog.csdn.net/article/details/96337444
[github]: https://github.com/yohstone/data-structure/blob/master/sort.cpp
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]: /images/20211209/476bd55512b5406fae9a6dd51ace9fb3.png
[20190714221124361.png]: /images/20211209/b118bfb35798489a97b24cb2193fe1bd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 1]: /images/20211209/eed987dcf64849d28c471472fa8c837a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 2]: /images/20211209/2380ae9def144204b31c584ef4e9695b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 3]: /images/20211209/fc7ccdb49d9f445db3c7e17f3e4cd1d7.png