数据结构七大排序算法图解——插入排序动图展示

朴灿烈づ我的快乐病毒、 2023-09-29 12:08 3阅读 0赞

# 系列文章目录 #

`提示：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作`

紧接上一篇[排序的概念及其运用][Link 1]

--------------------

### 文章目录 ###

*  系列文章目录
 *  前言
 *  二、插入排序动图演示
 *   *  基本思想：
 *  1、直接插入排序（基于顺序查找）
 *   *  不带监视哨的算法
     *   *  思想：
         *  代码部分
         *  例题：
     *  带监视哨的算法
     *   *  思想：
         *  代码部分
         *  例题：
     *  性能分析
 *  2、希尔排序（基于逐趟缩小增量）
 *   *  思想：
     *  代码部分
     *  例题：
     *  性能分析
 *  3、总结
 *   *  插入排序
     *  希尔排序

--------------------

# 前言 #

`提示：提示：本人不喜欢用专业术语来记录知识点，所以接下来会用例题+白话文的方式记录：`

归并排序(Merging Sort)是与插人排序、交换排序、选择排序不同的另一类排序方法。归并的含义是将两个或两个以上的有序表合并成一个新的有序表。

--------------------

`提示：以下是本篇文章正文内容，下面案例可供参考`

# 二、插入排序动图演示 #

在日常生活中,经常需要对所收集到的各种数据进行处理,其中排序是数据处理中一种非常重要的操作。排序的目的是为了提高查找的效率  
排序就是将一组“无序”的记录调整为“有序”记录的一种操作，可以从小到大排也可以从大到小排，一般都是从小到大排序（升序）

## 基本思想： ##

就是一个有序一个无序，从无序那里面取第一个往有序里面也就是（）里面插入，插入之后仍然保证有序，让所有记录都变成有序的  
换句话说就是  
插入排序的基本思想就是往一个有序区间插入一个数据，依旧保持他有序。

此处引用网上一张比较经典的gif来展示插入排序的整个过程：  
![在这里插入图片描述][5add98a0c9624d26bab3d9a4976b5de6.gif_pic_center]

# 1、直接插入排序（基于顺序查找） #

每次将一个待排序的记录，按其关键字值的大小插入到前面已排序好的记录序列中的适当位置，直到全部记录插入完成为止。

## 不带监视哨的算法 ##

### 思想： ###

可以先将第 0 个记录看成一个有序的子表，然后将后面的记录不断地往这个有序序列中插入，必须不断保证这个有序序列一直是有序的\*\*

### 代码部分 ###

public void insertSort() {
        
           RecordNode temp;
           int i, j;
           for (i = 1; i < this.curlen; i++) {
           //n-1趟扫描
               temp = r[i];    //将待插入的第i条记录暂存在temp中
               for(j = i - 1; j >= 0 && temp.key.compareTo(r[j].key) < 0 ; j--){
                      
                     r[j + 1] = r[j];   //将前面比r[i]大的记录后移
               }
               r[j + 1] = temp;  //r[i]插入到第j+1个位置
         } 
     }

### 例题： ###

r0 r1 r2 r3 r4  
43 21 89 15 43

在排之前看到 r0 在 r4 前面，在排完之后看 r0 是否还在 r4 前面，如果 r0 还在 r4 前面就说明这个算法是稳定的，如果排完后 r0 在 r4 后面，则说明这种算法是不稳定的  
**解：**  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LqM5ZOI5ZaH5a2Q772e_size_18_color_FFFFFF_t_70_g_se_x_16]  
**步骤：**  
**首先把 r0 当成有序序列，用（）括起来，（）外面是无序，然后往（）里面插入，这样就能保证（）一直是有序的  
第一次在无序序列中取 21 ，然后把 21 插入到（）中，因为 21 比 43 小，所以21 在 43 前面  
第二次在无序序列中取 89 ，然后把 89 插入到（）中，因为 89 比 21、43 大，所以在他们后面  
然后在无序序列中再取 15 插入到（）中，然后依次比较，小的在前，大的在后；一个是比较，一个是移动，以此类推**

## 带监视哨的算法 ##

### 思想： ###

首先将待排序的 n 条记录从下标为 1 的存储单元开始依次存放在数组 r 中，再将顺序表的第 0 个存储单元设置为一个“监视哨”，即在查找之前把 r\[i\] 赋给 r\[0\] ，这样每循环一次只需要进行记录的比较，不需要比较下标是否越界

### 代码部分 ###

void insertSortWithGuard() {
        
      // 对顺序表  作直接插入排序。
          for ( i=2; i<this.curlen; ++i ) {
        
    		r[0] = r[i];   // 复制为监视哨
    		for (j = i - 1;  
    	    	r[0].key.compareTo(r[j].key) < 0; j--) 
            r[j+1] = r[j];     // 记录后移
    		r[j+1] = r[0];     // 插入到正确位置   
    	}
    } 
    //或者是：
    void insertSortWithGuard() {
        
    	int i, j;
    	for(1= 1; i<this.curlen; i++) {
           //n-1趟扫描
    		r[0] = r[i];	//将待插人的第i条记录暂存在r[0]中，同时r[0]为监视哨
    	for (j = i - 1; r[0].key.compareTo(r[j].key)<0; j--) {
        	//将前面较大的数据元素向后移动
    			r[j + 1] = r[j];
    		}	
    		r[j +1] = r[0];   // r[i]插人到第j+1个位置
    	}
    }

### 例题： ###

r0 r1 r2 r3 r4 r5  
43 21 89 15 43

**解：**  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LqM5ZOI5ZaH5a2Q772e_size_20_color_FFFFFF_t_70_g_se_x_16]  
**步骤：**  
**第一步先把 r0 空着，r0 是不存数据的，把 r1 看成有序序列，  
第二步到 r2 ，21 的时候，把 21 赋值给 r0 ，其他操作不变，比大小，小的在前，大的在后  
第三步到 r3 ，89的时候，把 89 赋值给 r0 ，把 89 加到（）里面比大小  
第四步到 r4 ，15的时候，把 15 赋值给 r0 ，把 15 加到（）里面比大小  
后面的 43 也是一样**

## 性能分析 ##

(1)、时间复杂度：O(n2)

(2)、所需辅助空间：只需一个记录的辅助空间

(3)、算法稳定性：是稳定的排序方法

# 2、希尔排序（基于逐趟缩小增量） #

## 思想： ##

将记录序列分成若干子序列,分别对每个子序列进行插入排序。  
先进行分组，分完组再进行插入排序，小的在前

*  此处引用网上一张比较经典图来展示希尔排序的整个过程：  
    ![请添加图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LqM5ZOI5ZaH5a2Q772e_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
    经典动图展示：  
    ![请添加图片描述][267013fa2e2c4f06aecfec1791f62892.gif]

## 代码部分 ##

public void shellSort ( int[] d) {
            // d[]为增量数组
           RecordNode temp;
           int i, j;	//控制增量，增量减半，若干趟扫描
           for (int k = 0; k < d.length; k++) {
        
                int dk = d[k];
                for (i = dk; i < this.curlen; i++) {
        
                    temp = r[i];
                    for (j = i - dk; j >= 0 && temp.key.compareTo(r[j].key) < 0; j -= dk) {
        
                        r[j + dk] = r[j];
                    }
                    r[j + dk] = temp;
                }
            }

## 例题： ##

设排序表关键字序列 \{ 52，39 ，67，95，70 ，8，25，51，56，5 \}，增量 d 分别取为：5、3、1，则希尔排序过程如下图所示  
**以下数据，每一趟中颜色相同的为一组**  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LqM5ZOI5ZaH5a2Q772e_size_20_color_FFFFFF_t_70_g_se_x_16 2]

第一趟：d=5，中间隔4个分一组：（52，8）（39，25）（67，51）（95，56）（70，5）  
分完之后，对每一组进行插入排序，谁小谁在前面

写的时候对应每组的下标

第二趟：d=3，中间隔2个分一组：（8，56，39，70）（25，5，67）（51，52，95）  
分完后对每一组再进行插入排序，还是谁小谁在前面

写的时候对应每组的下标

第三趟：d=1，把这些数从小到大排就完了

## 性能分析 ##

(1)、时间复杂度：不确定，但在插入排序中，希尔排序的效能最高，最好情况可达O(nlog2n)

(2)、所需辅助空间：只需一个记录的辅助空间

(3)、算法稳定性：是不稳定的排序方法

# 3、总结 #

## 插入排序 ##

插入排序分为直接插入排序和希尔排序  
其中直接插入排序中无论是不带监视哨的算法还是带监视哨的算法其实都差不多

不带监视哨的算法无非就是一个有序一个无序，然后从无序那里面取第一个往有序里面也就是（）里面插入，插入之后仍然保证（）里面是有序就可以了，数字小的在前，大的在后，以此类推  
  
带监视哨的算法就是先把第一个数变成有序，用（）括起来， r0 是不存数据的，从 r1 开始，然后把后面那个数赋值给 r0，也是数字小的在前，大的在后，然后接着把（）后面的数赋值给 r0，放进（）里面比大小，以此类推

## 希尔排序 ##

希尔排序是【先进行宏观调整（分组），然后对每一组进行排序，排序的时候对应下标】。先看增量是几，也就是d，然后到第几个数停，比如说 d=n，那就到第 n 个数停，中间隔着 n-1 个数进行分组，然后对每一组进行插入排序，还是数字小的在前，大的在后，以此类推，当 d=1 的时候直接从小到大排就行

--------------------

[Link 1]: https://blog.csdn.net/rej177/article/details/124446028
[5add98a0c9624d26bab3d9a4976b5de6.gif_pic_center]: https://img-blog.csdnimg.cn/5add98a0c9624d26bab3d9a4976b5de6.gif#pic_center
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LqM5ZOI5ZaH5a2Q772e_size_18_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/48176c24450440a2bef0fa80edf3361d.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LqM5ZOI5ZaH5a2Q772e,size_18,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LqM5ZOI5ZaH5a2Q772e_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/4d5e0b86de034ed8bf9817daa45151db.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LqM5ZOI5ZaH5a2Q772e,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LqM5ZOI5ZaH5a2Q772e_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/ff7c9bfc34554be1932b44142730e895.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LqM5ZOI5ZaH5a2Q772e,size_20,color_FFFFFF,t_70,g_se,x_16
[267013fa2e2c4f06aecfec1791f62892.gif]: https://img-blog.csdnimg.cn/267013fa2e2c4f06aecfec1791f62892.gif
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LqM5ZOI5ZaH5a2Q772e_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/bf288d09ab11483ba82074ffed0dd1e9.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LqM5ZOI5ZaH5a2Q772e,size_20,color_FFFFFF,t_70,g_se,x_16