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

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，您应该从1not from开始2。