概要
插入排序属于内部排序法，是对需要排序的元素以插入的方式寻找该元素适当位置，以达到排序的目的。.
算法思想
插入排序（insertion sorting）的基本思想是：把n个待待续的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码一次与有序表元素的排序码进行比较，将他插入到有序表中的适当位置，使之成为新的有序表。
详细内容
应用实例：
有一群学生，考试成绩分别是101,34,119,1请从小到大排序。
分解代码：
public class InsertSort
{
public static void Sort(int[] arr)
{
//第一轮：{101,34,119,1} --> {34,101,119,1}
//定义待插入的数
int insertVal = arr[1];
//即arr[1]的前面这个数的下标
int insertIndex = 1 - 1;
//给insertval找到插入的位置
//1.insertindex >0 保证在给 insertval找到插入位置，不越界
//2.insertVal < arr[insertIndex] 待插入的数，还没有找到插入位置
//3.就需要将arr[insertIndex]后移
while (insertIndex >= 0 && insertVal < arr[insertIndex])
{
arr[insertIndex + 1] = arr[insertIndex];
insertIndex--;
}
//当推出while循环时，说明插入的位置找到，insertindex+1
arr[insertIndex + 1] = insertVal;
Console.WriteLine("第一轮插入后");
Console.WriteLine(string.Join(' ', arr));
}
}
static void Main(string[] args)
{
int[] array = { 101,34,119,1 };
InsertSort.Sort(array);
Console.Read();
}
基于以上逻辑分解之后，再看看完整代码演示：
public class InsertSort
{
public static void Sort(int[] arr)
{
for (int i = 1; i < arr.Length; i++)
{
//定义待插入的数
int insertVal = arr[i];
//即arr[1]的前面这个数的下标
int insertIndex = i - 1;
//给insertval找到插入的位置
//1.insertindex >0 保证在给 insertval找到插入位置，不越界
//2.insertVal < arr[insertIndex] 待插入的数，还没有找到插入位置
//3.就需要将arr[insertIndex]后移
while (insertIndex >= 0 && insertVal < arr[insertIndex])
{
arr[insertIndex + 1] = arr[insertIndex];
insertIndex--;
}
//当推出while循环时，说明插入的位置找到，insertindex+1
//举例：
arr[insertIndex + 1] = insertVal;
Console.WriteLine(string.Join(' ', arr));
}
}
}
static void Main(string[] args)
{
int[] array = { 101,34,119,1 ,-1 , 89};
InsertSort.Sort(array);
Console.Read();
}
