基础算法之插入排序（insetion sorting）

一时失言乱红尘 2022-05-29 05:24 128阅读 0赞

**1，算法名称：**升序插入排序（insertion sorting）

**2，时间复杂度：**O(n^2)

**3，实现方式：**C语言

**4，空间复杂度：**O(1)

**5，稳定性：**稳定

**6，算法思想：**

插入排序原理很简单，将一组数据分成两组，我分别将其称为有序组与待插入组。每次从待插入组中取出一个元素，与有序组的元素进行比较，并找到合适的位置，将该元素插到有序组当中。就这样，每次插入一个元素，有序组增加，待插入组减少。直到待插入组元素个数为0。当然，插入过程中涉及到了元素的移动（此时变可以通过增加新的空间开销来实现时间复杂度的降低，喜欢的童鞋们可以自己去试着做一下，我同时也把优化代码放在文章末尾**Example1**）

为了排序方便，我们一般将数据第一个元素视为有序组，其他均为待插入组。

**7，代码展示**

#include<stdio.h>  
    #include<stdlib.h>
    
    swap(int *a,int *b){
    	int temp;
    	temp = *a;
    	*a = *b;
    	*b = temp;
    }
    //升序插入排序 
    insertsortAsc(int *a, int n){
    	int i,j;
    	//i=1是因为第一个元素不需要考虑，因为我们默认第一个元素有序 
    	for(i = 1;i < n;i++){
    		//寻找a[]合适的插入位置 
    		for(j = i;j > 0;j--){
    			if(a[j] < a[j-1])
    				swap(&a[j],&a[j-1]);	
    			else
    				break;  
    		}
    	}
    }
    
    int main()  
    {  
    	int num[5]={3,1,5,6,2};  
    	int i=0;  
    	insertsortAsc(num,5);  
    	for(i=0;i<5;i++)  
    	{  
    		printf("%d ",num[i]);  
    	}	  
    	return 0;  
    }

\---------------------**END**\------------------

**Example1实现插入排序的优化**

#include<stdio.h>  
    #include<stdlib.h>
    
    swap(int *a,int *b){
    	int temp;
    	temp = *a;
    	*a = *b;
    	*b = temp;
    }
    //升序插入排序 
    insertsortAsc(int *a, int n){
    	int i,j;
    	//i=1是因为第一个元素不需要考虑，因为我们默认第一个元素有序 
    	for(i = 1;i < n;i++){
    		int e = a[i]; 
    		for(j = i;j > 0 && a[j-1] > e;j--)
    			//在这发现使用了赋值操作，明显比以前的交换值的方法快的多 
    			a[j] = a[j-1];
    		a[j] = e;
    	}
    }
    
    int main()  
    {  
    	int num[5]={3,1,5,6,2};  
    	int i=0;  
    	insertsortAsc(num,5);  
    	for(i=0;i<5;i++)  
    	{  
    		printf("%d ",num[i]);  
    	}	  
    	return 0;  
    }

**参考：  [插入排序算法详解与实现][Link 1]**

**            [基础算法大全][Link 2]**

[Link 1]: http://blog.csdn.net/llzk_/article/details/51628574
[Link 2]: http://blog.csdn.net/zzzzlei123123123/article/details/79592504