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

本文主要是介绍基础算法之插入排序（insetion sorting），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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;  
}   

参考：  插入排序算法详解与实现

            基础算法大全

这篇关于基础算法之插入排序（insetion sorting）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！