C# 实现插入排序

假设现有一数组，如下

基本排序代码，如下

static void Main(string[] args)
{
    int[] myArray = new int[] { 6, 4, 2, 6, 3, 9};//替换代码
    BaseSort(myArray, 1);//替换代码

    for (int i = 0; i < myArray.Length; i++)
    {
        Console.Write(myArray[i] + " ");
    }

    Console.WriteLine();
    Console.ReadLine();
}

public static void BaseSort(int[] array, int end)
{
    int endValue = array[end];
    for(int i = end - 1; i >= 0; i--)
    {
        if(endValue < array[i])
        {
            array[i + 1] = array[i];
            array[i] = endValue;
        }
        else//到达位置，不需要再进行比较
        {
            break;
        }
    }
}

1. 将替换代码换成下列代码，运行并分析

int[] myArray = new int[] { 6, 4, 2, 6, 3, 9};//替换代码
BaseSort(myArray, 1);//替换代码
//将下标 1 与之前的数值进行比较，并插入

下标 1 的数值 小于 下标 0 的数值，插入到下标 0

2. 将替换代码换成下列代码，运行并分析

int[] myArray = new int[] { 4, 6, 2, 6, 3, 9};//替换代码
BaseSort(myArray, 2);//替换代码
//将下标 2 与之前的数值进行比较，并插入

下标 2 的数值 小于 下标 1、0 的数值，插入到下标 0

3. 将替换代码换成下列代码，运行并分析

int[] myArray = new int[] { 2, 4, 6, 6, 3, 9};//替换代码
BaseSort(myArray, 3);//替换代码
//将下标 3 与之前的数值进行比较，并插入

下标 3 的数值 不小于 下标 2 的数值，不插入

4. 将替换代码换成下列代码，运行并分析

int[] myArray = new int[] { 2, 4, 6, 6, 3, 9};//替换代码
BaseSort(myArray, 4);//替换代码
//将下标 4 与之前的数值进行比较，并插入

下标 4 的数值 小于 下标 3、2、1的数值，插入到下标 1

5. 将替换代码换成下列代码，运行并分析

int[] myArray = new int[] { 2, 3, 4, 6, 6, 9 };//替换代码
BaseSort(myArray, 5);//替换代码
//将下标 5 与之前的数值进行比较，并插入

下标 5 的数值 不小于 下标 4 的数值，不插入

1. 插入排序按顺序依次从下标 1 开始，将该数值依次与前面排好序的数值进行依次比较
2. 如果该数值小于比较的数值，则将比较数值往后移动，并将该数值插入空缺位置
3. 当该数值大于/等于比较的数值时，不再进行任何操作，跳出循环，避免多余的比较

代码如下

static void Main(string[] args)
{
    int[] myArray = new int[] { 6, 4, 2, 6, 3, 9 };//替换代码
    InsertionSort(myArray);

    for (int i = 0; i < myArray.Length; i++)
    {
        Console.Write(myArray[i] + " ");
    }

    Console.WriteLine();
    Console.ReadLine();
}

//插入排序
public static void InsertionSort(int[] array)
{
    for (int i = 1; i < array.Length; i++)
    {
        int currentValue = array[i];
        for (int j = i - 1; j >= 0; j--)
        {
            if (currentValue < array[j])
            {
                array[j + 1] = array[j];
                array[j] = currentValue;
            }
            else
            {
                break;
            }
        }
    }
}

• 最优时间复杂度：数组已经排序完成，虽然要经过两个 for循环 ，但是里面的 for循环 只执行一次，最后相当于只执行一个 for循环
• 最差时间复杂度：数组倒序排序，需要进行两个 for循环 将小的数值移动到最前面
• 平均时间复杂度：一般情况下要进行两个 for循环
• 空间复杂度：需要借助 currentValue 变量用来记录进行比较的数值
• 稳定性：经过排序算法后，后面相同的数字依旧排在后面(例如：6)

因为作者精力有限，文章中难免出现一些错漏，敬请广大专家和网友批评、指正。