排序算法：直接插入排序

92 阅读 0 评论 61 点赞

我是靠谱客的博主端庄小虾米，最近开发中收集的这篇文章主要介绍排序算法：直接插入排序，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

直接插入排序基本思路：
对于给定的一组记录，初始时假定第一个数是有序序列，其余的按照无序序列；接着从第二个数开始，按照大小插入到之前的有序序列中，直到最后一个数插入到有序序列为止。

图示：
在这里插入图片描述
先假定29这个数是个有序序列，从18往后都是无序的。
这样先用18与29比较（18与有序序列的最后一个数比较），比29小，则先让29后移一位，移到18的位置，再把18移到29的位置，这样前两个就排序完毕。
我们直接跳到第四次比较，有代表性。3先和87比较，比他小，就先把3存起来，87后移一位，接着3和87的前一个数比较，还是小，56也后移一位；再和29比较，还是小；直到与18比完还是小，依旧18后移一位，把3插入到原来18的位置。
如此往后，排序完成。

可以借助下面动态图帮助理解：在这里插入图片描述
（动态图来自这位博主）

分析完毕，接下来上代码

#include <stdio.h>
void InsertSort(int *array, int length)
{
	int i, j, t;
	for(i = 1; i < length; i++)  //从第二个数开始
	{
		t = array[i];         //先把array[i]存起来
		for(j = i - 1; j >= 0; j--)    
		{
			if(array[j] > t)
			{
				array[j + 1] = array[j];  //往后移一个
			}
			else
			{
				break;        //如果if不成立。直接跳出本次for循环
			}
		}
		array[j + 1] = t;   //由于最后一次j循环自减了一次，所以要加一恢复到最后一个j位置。
	}
}

int main()
{
	int array[6] = {29,18,87,56,3,27};
	int i,length;
	length = sizeof(array)/sizeof(array[0]);
	InsertSort(array, length);

	for(i = 0; i < length; i++)
	{
		printf("%d ", array[i]
	}
	printf("n");
	return 0;
}