基本思想:将原来的无序数列看成含有一个元素的有序序列和一个无序序列,将无序序列中的值依次插入到有序序列中,完成排序。

C#算法实现:

public static void InsertionSort(int[] arr) 
{ 
	int n = arr.Length; //数组长度
	for (int i = 1; i < n; i++)//外层循环
	{ 
		int key = arr[i]; //左侧有序数组最大值
		int j = i - 1; //有序数组最大下标
		while (j >= 0 && arr[j] > key) //判断是否遍历到左侧有序数组第一个元素,并且,右侧无序数组第一个元素大于有序数组最大值
		{ 
			arr[j + 1] = arr[j]; //有序数组添加一个位子,每遍历一此都会判断当前有序数组位子对应的值是否比无序数组第一个值大
			j = j - 1; 
		} 
			arr[j + 1] = key;//有序数组对应位子的值小于无序数组第一个值,对应位置加1的索引处添加右侧无序数组第一个值
	} 
}