基础算法之插入排序(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;  
}   

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

            基础算法大全

    

上一篇:CF1500C - Matrix Sorting


下一篇:PAT A1052 Linked List Sorting