1. 图解-直接插入排序

太过爱你忘了你带给我的痛 2022-04-15 00:09 155阅读 0赞

### 1.   思想 ###

直接插入排序就是  打牌中抓牌插入的过程。（一般人都会整理为从小到大的序列）

思想：按照数据的大小插入到有序队列的合适位置。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlbmd5dXBlbmc_size_16_color_FFFFFF_t_70][]

### 2.  图解过程 ###

例1

![1024555-20161126000335346-416319390.png][]

例2

![070957420354467.png][]

### 3. 算法分析 ###

<table style="margin-left:5.4pt;"> 
 <tbody> 
 <tr> 
 <td style="background-color:#4f81bd;border-color:#000000;"> 排序类别 </td> 
 <td style="background-color:#4f81bd;border-color:#000000 #c0c0c0;"> 排序方法 </td> 
 <td colspan="3" style="background-color:#4f81bd;border-color:#000000 #c0c0c0;"> 时间复杂度 </td> 
 <td style="background-color:#4f81bd;border-color:#000000 #c0c0c0;"> 空间复杂度 </td> 
 <td style="background-color:#4f81bd;border-color:#000000 #c0c0c0;"> 稳定性 </td> 
 <td style="background-color:#4f81bd;border-color:#000000 #c0c0c0;"> 复杂性 </td> 
 </tr> 
 <tr> 
 <td style="background-color:#4f81bd;border-color:#c0c0c0 #c0c0c0;"> 平均情况 </td> 
 <td style="background-color:#4f81bd;border-color:#c0c0c0 #c0c0c0;"> 最坏情况 </td> 
 <td style="background-color:#4f81bd;border-color:#c0c0c0 #c0c0c0;"> 最好情况 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#c0c0c0;"> 插入排序 </td> 
 <td style="border-color:#c0c0c0 #c0c0c0;"> 直接插入排序 </td> 
 <td style="border-color:#c0c0c0 #c0c0c0;"> O(N²) </td> 
 <td style="border-color:#c0c0c0 #c0c0c0;"> O(N²) </td> 
 <td style="border-color:#c0c0c0 #c0c0c0;"> O(N) </td> 
 <td style="border-color:#c0c0c0 #c0c0c0;"> O(1) </td> 
 <td style="border-color:#c0c0c0 #c0c0c0;"> 稳定 </td> 
 <td style="border-color:#c0c0c0 #c0c0c0;"> 简单 </td> 
 </tr> 
 </tbody> 
</table>

时间复杂度：

当数据正序时，执行效率最好，每次插入都不用移动前面的元素，时间复杂度为O(N)。

当数据反序时，执行效率最差，每次插入都要前面的元素后移，时间复杂度为O(N²)。

所以，数据越接近正序，直接插入排序的算法性能越好。

### 4. Code in JAVA ###

public class InsertSort {
 
 
 	//插入排序方法
 	public static void insertSort(int[] array){
 		for (int i = 1; i < array.length; i++) {
 		 //从第二位开始遍历数组,Key 对应图解过程红色数据
 		 int key = array[i];
 		 int j = i - 1;
 		 //遍历数组下标i之前的数据，如果大于当前值，则后移一位
 		 for(;j >= 0 && array[j] > key;j--){
 		 array[j + 1] = array[j];
 		 }
 		 
 		 //直至遍历到最前一位，或者当前值小于遍历值，将当前值插入当前位置的后一个位置
 		 array[j+1]=key;
 		}
 	
 	}
 	
 	public static void printArray(int[] array) {
 		System.out.print("{");
 		for (int i = 0; i < array.length; i++) {
 			System.out.print(array[i]);
 			if (i < array.length - 1) {
 				System.out.print(", ");
 			}
 		}
 		System.out.println("}");
 	}
 
 
 
 	
 	
 	public static void main(String[] args) {
 		int[] array = { 9,3, 1, 4,2,7,8,6,5 };
 		insertSort(array);
 		printArray(array);
 		
 	}
 
 
 
 	
 
 }

### 5. 参考引用 ###

图解过程引自  作者： [dreamcatcher-cx][]

[https://www.cnblogs.com/chengxiao/p/6103002.html][https_www.cnblogs.com_chengxiao_p_6103002.html]

和

[http://www.cnblogs.com/xwz0528/p/4557743.html][http_www.cnblogs.com_xwz0528_p_4557743.html]

分析引自  静默虚空

[https://www.cnblogs.com/jingmoxukong/p/4303270.html][https_www.cnblogs.com_jingmoxukong_p_4303270.html]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlbmd5dXBlbmc_size_16_color_FFFFFF_t_70]: /images/20220415/872be5ac7a2b4394943e126310997e63.png
[1024555-20161126000335346-416319390.png]: /images/20220415/838fb0f92e3a4b2295245793bab865f0.png
[070957420354467.png]: /images/20220415/32820fb3044f47fd9118ec241cccaff7.png
[dreamcatcher-cx]: http://www.cnblogs.com/chengxiao/
[https_www.cnblogs.com_chengxiao_p_6103002.html]: https://www.cnblogs.com/chengxiao/p/6103002.html
[http_www.cnblogs.com_xwz0528_p_4557743.html]: http://www.cnblogs.com/xwz0528/p/4557743.html
[https_www.cnblogs.com_jingmoxukong_p_4303270.html]: https://www.cnblogs.com/jingmoxukong/p/4303270.html