插入排序：直接插入排序（稳定）

【 算法思想 】 直接插入排序是一种最基本的插入排序方法，其基本操作是将第 i 个记录插入到前面 i-1 个已排好序的记录中。具体过程为：将第 i 个记录的关键字 K i ，顺次与其前面记录的关键字 K i-1 ，K i-2 ，…, K 1 进行比较，将所有关键字大于 K i 的记录依次向后移动一个位置，直到遇见一个关键字小于或者等于 K i 的记录 K j ，此时 K j 后面必为空位置，将第 i 个记
录插入空位置即可。完整的直接插入排序是从 i=2 开始，也就是说，将第 1 个记录视为已排好序的单元素子集合，然后将第二个记录插入到单元素子集合中。i 从 2 循环到 n，即可实现完整的直接插入排序。

我们经常会到这样一类排序问题：把新的数据插入到已经排好的数据列中。将第一个数和第二个数排序，然后构成一个有序序列将第三个数插入进去，构成一个新的有序序列。对第四个数、第五个数……直到最后一个数，重复第二步。如题所示：

来自网络

直接插入排序（Straight Insertion Sorting）的基本思想：在要排序的一组数中，假设前面(n-1) [n>=2] 个数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。

---

C#实现：

/// <summary>
/// 自定义工具类
/// </summary>
public static class Utilit
{
    /// <summary>
    /// 辅助输出排序结果：
    /// </summary>
    /// <param name="a"></param>
    /// <param name="t"></param>
    public static void Print(int[] a, int t)
    {
        string str = null;
        for (int i = 0; i < a.Length; i++)
        {
            str += a[i].ToString() + " ";
        }
        Debug.Log("第" + t + "趟排序结果：" + str);
    }

    /// <summary>
    /// 辅助生成排序结果
    /// </summary>
    /// <param name="max"></param>
    /// <param name="length"></param>
    /// <returns></returns>
    public static int[] RandArray(int max, int length)
    {
        string str = null;
        int[] a = new int[length];
        for (int i = 0; i < a.Length; ++i)
        {
            a[i] = Random.Range(0, max);
            str += a[i].ToString() + " ";
        }
        Debug.Log("随机生成的数组：" + str);
        return a;
    }
}

上方为产生随机数组与打印排序数组的工具类

直接插入排序：

/// <summary>
/// 插入排序类
/// </summary>
public class InsertSort
{
    /// <summary>
    ///1、 直接插入排序法：
    /// </summary>
    /// <param name="a"></param>
    public static void StraightInsetSort(int[] a)
    {
        int insertNum;//要插入的数
        int len = a.Length;//数组长度

        for (int i = 1; i < len; i++) //从第2个数，进行插入排序
        {
            insertNum = a[i];

            int j = i - 1; //前一个数的索性值

            while (j >= 0 && insertNum < a[j])
            {
                a[j + 1] = a[j]; //把大的向后移动
                j--;
            }

            a[j + 1] = insertNum;//找到位置，插入当前元素

            Utilit.Print(a, i);//输出每趟的排序的结果
        }

    }

}

---

测试用例：

public class _012_InsertSort : MonoBehaviour
{


    void Start()
    {
        int[] a = Utilit.RandArray(20, 10); //max,lenght

        Debug.Log("------------直接插入排序----------------");
        InsertSort.StraightInsetSort(a); //直接插入排序

    }
}

---

输出结果：

插入排序：直接插入排序

注：

1、直接插入排序的时间复杂度为 T(n)=O(n 2 )，空间复杂度为 S(n)=O(1)。

2、稳定排序算法

3、直接插入排序算法简便，比较适用于待排序记录数目较少且基本有序的情况。当待排记录数目较大时，直接插入排序的性能就不好，因此可以对直接插入排序做进一步的改进。在直接插入排序法的基础上，从减少“比较关键字”和“移动记录”两种操作的次数着手来进行改进。

image.png