c++ - 插入排序算法在放入函数时表现不同

Question

我有以下代码来实现插入排序:

int main()
{   
    const int SIZE = 10;
    int a[SIZE] = {8, 6, 10, 2, 16, 4, 18, 14, 12, 10};

    //insertionSort(a, SIZE);

    // The following code is used in the insertionSort() function call above. To use the function, uncomment the function call above, and comment out the code below

    // Start of code used by insertionSort() function
    int temp;
    for (int i=1; i < SIZE; i++)
    {
        for (int j=i; a[j] < a[j-1]; j--)
        {
            temp = a[j];
            a[j] = a[j-1];
            a[j-1] = temp;
        }
    }
    // End of code used by insertionSort() function

    return 0;   
}

void insertionSort(int a[], const int SIZE)
{
    int temp;
    for (int i=1; i < SIZE; i++)
    {
        for (int j=i; a[j] < a[j-1]; j--)
        {
            temp = a[j];
            a[j] = a[j-1];
            a[j-1] = temp;
        }
    }
}

当代码在 main() 中使用时，该算法工作正常，但当通过 insertionSort() 调用时，它会产生错误的结果。

我确定问题是这样的:内部循环条件 (a[j] < a[j-1]) 在 j 达到 0 时不会停止循环，因此它继续使用负数访问数组指数。将条件更改为 (j > 0 && a[j] < a[j-1]) 按预期工作。

我想知道为什么只有当循环在 insertionSort() 中运行时才会出现这种行为，而在 main() 中运行时不会出现这种行为。

Answer 1

这个循环

    for (int j=i; a[j] < a[j-1]; j--)
    {
        temp = a[j];
        a[j] = a[j-1];
        a[j-1] = temp;
    }

调用未定义的行为，因为没有检查 j 应大于 0。

否则，例如当 j 等于 0 时，可以使用索引 -1 访问数组之外​​的内容

a[0] < a[-1]

这是一个带有更新循环的演示程序

#include <iostream>
#include <utility>

int main() 
{
    int a[] = { 8, 6, 10, 2, 16, 4, 18, 14, 12, 10 };
    const size_t SIZE = sizeof( a ) / sizeof( *a );

    for ( const auto &item : a ) std::cout << item << ' ';
    std::cout << '\n';

    for ( size_t i = 1; i < SIZE; i++ )
    {
        for ( size_t j = i; j != 0 && a[j] < a[j-1]; --j )
        {
            std::swap( a[j-1], a[j] );
        }
    }

    for ( const auto &item : a ) std::cout << item << ' ';
    std::cout << '\n';

    return 0;
}

它的输出是

8 6 10 2 16 4 18 14 12 10 
2 4 6 8 10 10 12 14 16 18 

并将算法包含在一个函数中

#include <iostream>
#include <utility>

void insertionSort( int a[], size_t n )
{
    for ( size_t i = 1; i < n; i++ )
    {
        for ( size_t j = i; j != 0 && a[j] < a[j-1]; --j )
        {
            std::swap( a[j-1], a[j] );
        }
    }
}

int main() 
{
    int a[] = { 8, 6, 10, 2, 16, 4, 18, 14, 12, 10 };
    const size_t SIZE = sizeof( a ) / sizeof( *a );

    for ( const auto &item : a ) std::cout << item << ' ';
    std::cout << '\n';

    insertionSort( a, SIZE );

    for ( const auto &item : a ) std::cout << item << ' ';
    std::cout << '\n';

    return 0;
}

输出与上图相同

8 6 10 2 16 4 18 14 12 10 
2 4 6 8 10 10 12 14 16 18