插入排序在原理上应该是最容易理解的，类似于打扑克，对扑克牌进行排序，从左到右升序排列。
算法原理：
通过构建有序序列，对于未排序序列数据，从已知排序序列中从后向前扫描，找到对应位置并插入。
算法步骤：

• 将待排序列第一个元素看作有序序列，第二个元素至最后一个元素看成是未排序序列
• 从头到尾依次扫描未排序序列，依次将抽出的元素插入到有序序列适当位置（如果比对元素相等，则将抽出的元素排在相等元素后面）

代码实现

// 插入排序
public void Sort(int[] arr)
{
    int selected;
    for (int i = 1; i < arr.Length; i += 1) // 遍历未排序列
    {
        selected = arr[i];                  // 抽出最左边没排序的哪张牌
        for (int j = i - 1; j >= 0; j -= 1) // 遍历已排序列
        {
            if (selected < arr[j])          // 依次和已排序列的元素进行比较
            {
                arr[j + 1] = arr[j];
                arr[j] = selected;
            }
            else
            {
                break;
            }
        }
    }
}

算法复杂度

	最好	最坏	平均	空间复杂度	稳定不？
插入排序					稳定

时间复杂度最好的情况：如果序列有序的，那么对未排序列的遍历就只会在第一次判断时就退出，相当于只会遍历一遍序列，时间复杂度为