直接插入排序详解

客官°小女子只卖身不卖艺 2022-11-26 04:56 109阅读 0赞

**上一篇博客：**[归并排序详解][Link 1]

>  写在前面：大家好！我是`ACfun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。这篇博客来详解一下插入排序算法中的直接插入排序后面还会整理插入排序中的折半插入排序和希尔排序。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油，冲鸭！  
>  `用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง`

### 文章目录 ###

*  插入排序简介
 *  直接插入排序
 *   *  实现思路
     *  实现代码

# 插入排序简介 #

插入排序是一种简单直观的排序方法，其基本思路为每次将一个待排序的元素按照其关键字大小插入到前面已经排好序的子序列中，直到全部的记录插入完成。  
 由这一排序思想可以引申出三个重要的排序算法：`直接插入排序、折半插入排序、希尔排序`。

# 直接插入排序 #

## 实现思路 ##

**直接插入排序**是一种最简单的排序方法，他的基本操作就是不断地将一个记录插入到之前已经排好序的序列中直到完成所有的排序。进行插入排序首先我们应该明确什么是监视哨。在进行插入排序的时候我们的数据是从下标为 1 的地方开始存储，下标为 0 的位置不存储数据而作为监视哨。  
 监视哨 q\[0\] 主要有两个作用：

>  1.进行查找(插入位置)循环之前，它保存了待排序数据 q\[i\] 的副本（q\[0\] = q\[i\]），使会因为记录后移而丢失 q\[i\] 的内容；  
>  2.监视哨 q\[0\] 的主要作用是：防止在查找插入位置的过程中出现数组下标越界。引入监视哨可以避免很多不必要的判断语句，从而提高程序的效率。

明确了监视哨的作用之后，下面我们来看一下如何具体的实现插入排序：  
 1. 找出待排序元素 q\[i\] 应该插入的位置 k；  
 2.将待排序元素 q\[i\] 放到监视哨的位置 即使 q\[0\] = q\[i\]；  
 3.将 k 到 i 位置的元素依次向后移动一个位置；  
 4.将监视哨 q\[0\] 的数据复制到数据应该插入的位置 q\[k\]；  
![插入排序图解][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70_pic_center]

## 实现代码 ##

#include<iostream>
    using namespace std;
    
    const int N = 1e5 + 10;
    int q[N];
    
    int main() { 
    	int n;
    	cin >> n;
    	for (int i = 1; i <= n; i++) cin >> q[i];
    	
    	// 依次将 2 ~ n 插入到前面已经排好序的序列中 
    	for (int i = 2; i <= n; i++) { 
    		if (q[i] < q[i - 1]) { 
    			// 加一个判断条件判断一下待排数据是否需要进行比较 
    			q[0] = q[i];    // 将待插入数据放到监视哨的位置 
    			int j; 
    			for (j = i - 1; q[0] < q[j]; j--) { 
    				// 将数据依次向后移动，找到待排数据应该插入的位置 
    				q[j + 1] = q[j];
    			}
    			q[j + 1] = q[0];    // 将数据插入到应该插入的位置 
    		}
    	}
    	
    	// 输出结果 
    	for (int i = 1; i <= n; i++) cout << q[i] << " ";
    	
    	return 0;
    	
    }

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

> 未完待续，持续更新中……  
> ![冲鸭！][20200813205734888.png]

[Link 1]: https://blog.csdn.net/qq_41575507/article/details/107300891
[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/f449f3c9933641e2af282cbb8a61dc24.png
[20200813205734888.png]: /images/20221124/71b98f41177a4c73a2e2f4a4d81a52b3.png