忽略第一个元素的插入排序算法

Question

我在C++中实现了一个简单的插入排序，如下所示：

void insertion_sort(int a[], int size)
{
    int temp;
    for (int i = 2; i < size; i++)
    {
        temp = a[i];
        int j = i - 1;
        while (j > 0 && a[j] > temp)
        {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = temp;
        print_array(a, size);
    }
    cout << "Final:" << endl;
    print_array(a, size);
}

但是，这会对数组中除第一个元素以外的所有元素进行排序。输出如下所示：

Original array:
5 2 4 1 3 0 
Insertion Sorted array:
5 2 4 1 3 0 
5 1 2 4 3 0 
5 1 2 3 4 0 
5 0 1 2 3 4 
Final:
5 0 1 2 3 4 

如果我改变了

j > 0 

至

j >= 0

然后,

Original array:
5 2 4 1 3 0 
Insertion Sorted array:
5 2 4 1 3 0 
1 5 2 4 3 0 
1 5 2 3 4 0 
0 1 5 2 3 4 
Final:
0 1 5 2 3 4 

Answer 1

你只需要保持条件( j >= 0 )，并且改变你在i上循环的起点，你应该从1开始，而不是从2开始。

Answer 2

您的代码适用于从1开始索引的数组。c++中数组的第一个元素始终为0。无需更改任何运算符，您只需在for循环的开始和while循环中向下移动时，将数组移至0的start(或end)即可：

void insertion_sort(int a[], int size)
{
int temp;
for (int i = 1; i < size; i++)
{
    temp = a[i];
    int j = i - 1;
    while (j > -1 && a[j] > temp)
    {
        a[j + 1] = a[j];
        j--;
    }
    a[j + 1] = temp;
    print_array(a, size);
}
cout << "Final:" << endl;
print_array(a, size);
}

关于这段代码还需要注意的是：&&是短路的。如果在本例中为j = -1，则j > -1为false，并且a[-1]不会在while (j > -1 && a[j] > temp)中求值，因为j为> -1会使其变得不相关。无论a[j]是什么，都不会使结果为真。