插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。
原理：
⒈ 从第一个元素开始，该元素可以认为已经被排序
⒉ 取出下一个元素，在已经排序的元素序列中从后向前扫描
⒊ 如果该元素（已排序）大于新元素，将该元素移到下一位置
⒋ 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
⒌ 将新元素插入到下一位置中
⒍ 重复步骤2~5
代码语言：javascript复制 static int[] InsertSort(int[] arr)
{
//插入排序是把无序列的数一个一个插入到有序的数
//1.先默认下标为0这个数已经是有序
for (int i = 1; i < arr.Length; i )
{
int insertVal = arr[i]; //2.首先记住这个预备要插入的数
int insertIndex = i - 1; //找出它前一个数的下标（等下 准备插入的数 要跟这个数做比较）
//4.如果这个条件满足，说明，我们还没有找到适当的位置
while (insertIndex >= 0 && insertVal < arr[insertIndex]) //这里小于是升序，大于是降序
{
arr[insertIndex 1] = arr[insertIndex]; //3.同时把比插入数要大的数往后移
insertIndex--; //3.指针继续往后移，等下插入的数也要跟这个指针指向的数做比较
}
//5.插入(这时候给insertVal找到适当位置)
arr[insertIndex 1] = insertVal;
}
return arr;
}排序结果
代码语言：javascript复制 static void Main(string[] args)
{
Console.WriteLine($"数据算法");
var arr1 = GetArrayData(8, 1, 22);
Console.WriteLine($"生成未排序数据arr1：{ShowArray(arr1)}");
//var arr2 = BubbleSort(arr1);
//Console.WriteLine($"冒泡排序：{ShowArray(arr2)}");
//var arr3 = SelectSort(arr1);
//Console.WriteLine($"选择排序arr3：{ShowArray(arr3)}");
//var val = arr3[3];
var arr4= InsertSort(arr1);
Console.WriteLine($"插入排序arr4：{ShowArray(arr4)}");
//var index= BinarySearch(arr3, 0, arr1.Length - 1,val);
//Console.WriteLine($"{val}在 arr3中出现的索引位置是{index}");
//var val2 = arr3[4];
//var index2 = BinarySearch2(arr3, val2);
//Console.WriteLine($"{val2}在 arr3中出现的索引位置是{index2}");
Console.ReadLine();
}
