C语言：直接插入排序图解

ゝ一世哀愁。 2023-06-16 08:11 20阅读 0赞

### C语言：直接插入排序图解 ###

*  一、背景
 *  二、做法
 *  三、图解
 *  四、源程序
 *  五、总结

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

# 一、背景 #

给定如下数组，使用直接插入排序的方法对其进行升序排列。

int data[6]={5,3,1,6,3,4};

# 二、做法 #

**在插入第i个记录时，R1, R2, …, Ri-1已经排好序，这时将Ri的关键字ki依次与关键字ki-1, ki-1等进行比较，从而找到应该插入的位置并将Ri插入，插入位置及其后的记录依次向后移动。**

# 三、图解 #

**符号解释：**  
**  i：数组序号，初值为1，data\[i\]指向将要排序的数。**  
**  j：数组序号，初值为i-1，用于确定data\[i\]插入位置。**  
**  temp：保存中间值data\[i\]。**  
**  data：数组，存放将要排序的数字。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center]  
**1、首先默认data\[0\]已排好序，从data\[1\]开始进行插入排序。从下图可发现，从data\[i\]的插入位置为0（紫色部分），故保存data\[i\]至temp，将data\[0\]右移1位，temp插入data\[0\]。如此data\[i\]便排好序，此轮循环结束，i++，j=i-1进入下一循环。**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 4]

**2、如下图，i=2， j=1。data\[i\]的插入位置为0（紫色部分），故保存data\[i\]至temp，将data\[1\]和data\[0\]右移1位，temp插入data\[0\]。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 7]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 8]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 9]  
**3、如下图，i=3， j=2，data\[i\]>data\[j\]。故无需排序，直接进入下一循环。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 10]  
**4、如下图，i=4， j=3，data\[i\]插入位置为2，保存data\[i\]至temp，将data\[3\]和data\[2\]右移1位，在data\[2\]插入temp。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 11]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 12]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 13]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 14]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 15]  
**5、如下图，i=5， j=4，data\[i\]插入位置为3，保存data\[i\]至temp，将data\[4\]和data\[3\]右移1位，在data\[3\]插入temp。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 16]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 17]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 18]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 19]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 20]  
**6、当i等于数组个数时，循环结束，排序完成。**

# 四、源程序 #

#include<stdio.h>
    #define N 6
    
    //输出中间过程的结果 
    void print_data(int i, int n, int data[]){
    	int k;
     	printf("i=%d: ", i);
     	for(k=0;k<n;k++){
     		printf("%d ", data[k]);
    	}
    	printf("\n");
    }
    
    //直接插入排序，升序 
    void Insertsort(int data[], int n){
     	int i,j,temp;
     	for(i=1;i<n;i++){
     		
     		print_data(i, n, data);//输出中间过程的结果
     		
     		j=i-1;
     		if(data[i]<data[j]){
     			temp=data[i];
     			data[i]=data[j];
     			for(j=j-1;j>=0 && temp<data[j];j--){
     				data[j+1]=data[j];
    			 }
    			data[j+1]=temp;
    			
    			print_data(i, n, data);//输出中间过程的结果
    		 }
    		 
    		 printf("\n");
    	 }
     }
    
    int main(){
    	int data[N]={5,3,1,6,3,4};
    	Insertsort(data, N);
    	return 0;
     }

# 五、总结 #

1、直接插入排序是**稳定**的排序方法，时间复杂度为**O(n2)**，空间复杂度为**O(1)**。  
2、理解算法思路比记代码更有效，因为不同人，不同书，对于同一算法，源代码肯定不一样。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20191126101713529.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20191126101832269.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/2019112610185087.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20191126101913601.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/20191126101954969.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 5]: https://img-blog.csdnimg.cn/20191126102110587.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 6]: https://img-blog.csdnimg.cn/20191126102122500.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 7]: https://img-blog.csdnimg.cn/20191126102130959.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 8]: https://img-blog.csdnimg.cn/20191126102153587.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 9]: https://img-blog.csdnimg.cn/2019112610222018.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 10]: https://img-blog.csdnimg.cn/20191126102323206.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 11]: https://img-blog.csdnimg.cn/20191126102717824.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 12]: https://img-blog.csdnimg.cn/20191126103042131.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 13]: https://img-blog.csdnimg.cn/20191126103439189.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 14]: https://img-blog.csdnimg.cn/20191126103449134.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 15]: https://img-blog.csdnimg.cn/20191126103503706.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 16]: https://img-blog.csdnimg.cn/20191126103602628.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 17]: https://img-blog.csdnimg.cn/20191126103614212.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 18]: https://img-blog.csdnimg.cn/20191126103624948.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 19]: https://img-blog.csdnimg.cn/20191126103636688.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center 20]: https://img-blog.csdnimg.cn/20191126103648791.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy,size_16,color_FFFFFF,t_70#pic_center