插入排序未将数组首个元素纳入排序的原因排查

问题描述 #

尝试用插入排序对数组排序时，数组首个元素未被纳入排序范围，代码如下：

namespace InsertionSort
{
    class Program
    {
        static void Main(string[] args)
        {
            int min = 0, max = 40;
            int[] array1 = new int[10];
            Random randNum = new Random();
            for (int i = 0; i < array1.Length; i++)
            {
                array1[i] = randNum.Next(min, max);
            }
            foreach (var item in array1)
            {
                Console.WriteLine(item);
            }
            Console.WriteLine("***************");
            
            for (int j = 1; j < array1.Length; j++)
            {
                int key,i;
                key = array1[j];
                i = j - 1;
                while ((i>0)&&array1[i]>key )
                {
                    array1[i + 1] = array1[i];
                    i = i - 1;
                }
                array1[i + 1] = key;
            }
            foreach (var item in array1)
            {
                Console.WriteLine(item);
            }
        }
    }
}

输出表现为：数组首个元素仍处于无序状态，其余元素已按插入排序规则排列。

问题原因 #

问题出在while循环的条件判断上：
原代码中循环条件是(i>0)&&array1[i]>key，当i递减到0时，循环直接终止，不会将当前key与数组的第0个元素（首个元素）进行比较和交换。这就导致首个元素永远不会被后续的元素插入操作所覆盖或调整，相当于被排除在了排序逻辑之外。

修正方案 #

将while循环的条件从i>0改为i>=0，这样就能确保key可以和数组的所有前置元素（包括首个元素）进行比较：

for (int j = 1; j < array1.Length; j++)
{
    int key,i;
    key = array1[j];
    i = j - 1;
    // 修改此处的条件，将i>0改为i>=0
    while ((i>=0)&&array1[i]>key )
    {
        array1[i + 1] = array1[i];
        i = i - 1;
    }
    array1[i + 1] = key;
}

修改后，插入排序会正常处理首个元素，整个数组都能被正确排序。

内容的提问来源于stack exchange，提问作者Selcuk