直接插入排序算法详解之C语言版

一、算法原理

插入排序属于稳定排序法，是一种常用的排序算法。
其基本原理就是把一个数据插入到一组已经排好序的数列中，得到仍是有序的数列。
例如：已经有如下排好序的数组:

将数据15插入到该数组中得到新数组，即将15插入到数组下标为5的位置。

那么位置5是怎么得到的呢，且行且学习。
记待插入数据为data，则直接插入排序的基本思想是从数组的最后一个元素开始依次向前比较，如果data小，则数组元素后移，否则，插入到最后一次比较的元素之后。
为了提高算法的效率，可以启用哨兵位，即下标为0的位置，将data存入到该位置。
以上述待插入数据和数组为例演示直接插入排序的过程如下：
Step_1：将15存入哨兵位

Step_2：将哨兵位元素与数组最后一个元素19进行比较，15小，则19后移

Step_3：将哨兵位元素与数组元素18进行比较，15小，则18后移

Step_4：将哨兵位元素与数组元素14进行比较，15大，则存入元素且之后，插入 *** 作结束

二、算法

1.将一个数据使用直接插入法插入到一组排好序的数组的算法：
Step 1: 将待插入数据存入哨兵位，记数组最大下标为k，其位置上的元素为当前元素；
Step 2：将哨兵位元素与当前元素进行比较，
如果哨兵位元素大，则将哨兵位元素存入k+1位置，结束插入 *** 作；
否则转入Step 3；
Step 3：当前元素后移一位，然后k–，转Step 2.
2.对一组数据使用直接插入法排序，则循环调用上述算法即可，算法时间复杂度是O(n^2)。
三、C/C++程序

**1. 直接插入排序算法之C语言版**
/*
功能：使用直接插入排序法将数据data插入到数组arr中
输入参数：
	arr，按照元素值从小到大排序的数组
	data，待插入的数据
输出参数：
	arr，插入新数据且排好序的数组
返回值：无 
*/
void InsertSort( Array &arr, int data )
{
	int k;
	if( arr.length >= MaxLength )
	{
		printf( "数组已满，不能插入当前元素: %d", data );
		return;
	}
	arr.data[0] = data; 
	for( k = arr.length; ;k-- )
	{
		if( arr.data[0] < arr.data[k] )
		{
			arr.data[k+1] = arr.data[k];
		}
		else
		{
			arr.data[k+1] = arr.data[0];
			break;
		}
	}
	arr.length++;
}

2.完整的代码（仅供参考）

#include"stdio.h"
#define MaxLength 100

typedef struct
{
	int data[MaxLength];//排序数组 
	int length;         //数组的实际长度 
}Array;

void InputData( int &count, int arrt[] );
void InsertSort( Array &arr, int data );

int main()
{
	int count = 0, k, i;
	int arrt[MaxLength];
	InputData( count, arrt );
	Array arr;
	arr.length = 0;
	for( k = 1; k <= count; k++ )
	{
		InsertSort( arr, arrt[k] );
		printf( "No %d sorting( %3d ): ", k, arrt[k] );
		for( i = 1; i <= arr.length; i++ )
		{
			printf( "%5d", arr.data[i] );
		}
		printf( "\n" );
	}
	
	return 0;
} 
//功能：使用直接插入排序法将数据data插入到数组arr中
void InsertSort( Array &arr, int data )
{
	int k;
	if( arr.length >= MaxLength )
	{
		printf( "数组已满，不能插入当前元素: %d", data );
		return;
	}
	arr.data[0] = data; 
	for( k = arr.length; ;k-- )
	{
		if( arr.data[0] < arr.data[k] )
		{
			arr.data[k+1] = arr.data[k];
		}
		else
		{
			arr.data[k+1] = arr.data[0];
			break;
		}
	}
	arr.length++;
}
//从键盘获取数据，count表示数据个数，arrt是存储数据的数组
void InputData( int &count, int arrt[] )
{
	int i = 0, data;
	while( 1 )
	{
		printf( "input an positive integer(end of -1)" );
		scanf( "%d", &data );
		if( data == -1 )
		{
			break;
		}
		else
		{
			arrt[++i] = data;
		}
	}
	count = i;
}

3.测试用例
测试一：

测试二（有相同数据）：