数据结构与算法分析之插入排序(Insertion Sort)学习

插入排序(英语:Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

如果目标是把n个元素的序列升序排列,那么采用插入排序存在最好情况和最坏情况。最好情况就是,序列已经是升序排列了,在这种情况下,需要进行的比较操作需(n-1)次即可。最坏情况就是,序列是降序排列,那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上 (n-1)次。平均来说插入排序算法的时间复杂度为O(n^2)。因而,插入排序不适合对于数据量比较大的排序应用。但是,如果需要排序的数据量很小,例如,量级小于千,那么插入排序还是一个不错的选择。

插入排序算法描述:
1、从第一个元素开始,该元素可以认为已经被排序;
2、取出下一个元素,在已经排序的元素序列中从后向前扫描;
3、如果该元素(已排序)大于新元素,将该元素移到下一位置;
4、重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
5、将新元素插入到该位置后;
6、重复步骤2~5。

一、 插入排序源码

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define NUM 10

// 插入排序函数实现
void insertion_sort(int a[], int n)
{
	for(int i=1; i<n; i++)
	{
		int j, temp = a[i];
		
		for(j=i; j>0&&a[j-1]>temp; j--)
		{
			a[j] = a[j-1];
		}
		
		a[j] = temp;
	}
}

int main(void)
{
	int array[NUM];
	
	srand((unsigned int)time(NULL));
	
	// 给数组赋随机值
	for(int i=0; i<NUM; i++)
	{
		array[i] = rand()%100;
	}
	
	// 打印排序前数组
	for(int i=0; i<NUM; i++)
	{
		printf("%5d", array[i]);
	}
	
	printf("\n");
	
	// 插入排序
	insertion_sort(array, NUM);
	
	// 打印排序后数组
	for(int i=0; i<NUM; i++)
	{
		printf("%5d", array[i]);
	}
	
	printf("\n");
	
	return 0;
}

二、 运行结果

[root@fedora Workspace]# gcc insertion_sort.c -o insertion_sort -Wall
[root@fedora Workspace]# ./insertion_sort
   45   71   94   18   64   66    3   49   59   27
    3   18   27   45   49   59   64   66   71   94
[root@fedora Workspace]# ./insertion_sort
    3   86   38   58   40    2   62   76   86   66
    2    3   38   40   58   62   66   76   86   86
[root@fedora Workspace]# ./insertion_sort
   86   49   90   46   95    5    0   85   79   11
    0    5   11   46   49   79   85   86   90   95
[root@fedora Workspace]# ./insertion_sort
   42   79   69   68   57   88   15   54   76   35
   15   35   42   54   57   68   69   76   79   88
[root@fedora Workspace]# ./insertion_sort
   41   91   14   74   22    4   69    3   66   82
    3    4   14   22   41   66   69   74   82   91
[root@fedora Workspace]# ./insertion_sort
   95   40   78   72   96   59    5   37   34   42
    5   34   37   40   42   59   72   78   95   96

Leave a Reply

Your email address will not be published. Required fields are marked *