插入排序（Insertion Sort）的算法描写叙述是一种简单直观的排序算法。

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到对应位置并插入。插入排序在实现上，通常採用in-place排序（即仅仅需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，须要重复把已排序元素逐步向后挪位。为最新元素提供插入空间。

通俗解释：

①如果初始序列的第一个元素是有序的（当一个序列仅仅有1个元素时，我们能够觉得其是有序的）。

②从第二个元素開始与前面的元素进行比較，假设比前面的大就不动位置。假设比其小就换位置

③再从第三个位置继续往前比較。重复操作，直到整个序列有序为止。

源码：

#include "stdafx.h"

#include <stdlib.h>

void Insert_Sort()

{

	int arr[10];

	for ( int i=0; i<10; i++)  //初始化数据

	{

		arr[i] = rand()%33;  //随机生成数据

	}

	printf("Before sort:\n");  //打印排序前的数据

	for (int i = 0; i < 10; i++)

	{

		printf("%d ",arr[i]);

	}

	//開始排序

	int k = 0;

	int temp = 0 ; //记录要插入的数据

	for (int i = 1; i < 10; i++) //从第二个一直比到最后一个元素

	{

		k = i;

		temp = arr[k];

		for (int j = i-1; (j>=0)&&(arr[j] > temp); j--)//从要插入的元素的上一个元素開始,一直往前，																			//直到要插入的元素遇到不比它大的元素为止

		{

			arr[j+1] = arr[j];

			k = j; //k的位置就是要插入的位置

		}

		arr[k]  = temp; //将要插入的元素插到k的位置

	}

	printf("\nAfter sort:\n"); //打印排序后的数据

	for (int i = 0; i < 10; i++)

	{

		printf("%d ",arr[i]);

	}

}

int _tmain(int argc, _TCHAR* argv[])

{

	Insert_Sort();

	printf("\n");

	system("pause");

	return 0;

}

执行结果：

Before sort:

8 20 31 1 29 16 27 21 1 11

After sort:

1 1 8 11 16 20 21 27 29 31

请按随意键继续. . .

如有错误，望不吝指出。