c++ - C++中的插入排序实现导致多个错误

Question

这是 CodeBlocks 13.12 上的控制台应用程序。

运行此插入排序时出现各种错误。

有时它会打印原始数组中没有的大得离谱的值。或者有时它会运行并对数组进行完美排序。

任何人都可以指出什么可能是错误的吗？对不起，我是菜鸟。

#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;    

void insertionSort(int arr[], int size);

int main()
{
    int size;
    srand(time(NULL));
    cout << "Specify the size of your array: ";
    cin >> size;
    int theArray[size]; // creates an array of a size the user chooses

    cout << endl << "Your current array: {";

    for (int i = 0; i < size; i++) //prints out the original array
    {
        theArray[i] = rand() % 10000;
        cout << theArray[i];

        if (i != size - 1) // to beautify output
        {
            cout << ", ";
        }
        if (i % 10 == 0 && i != 0)
        {
            cout << endl;
        }
    }
    cout << "}" << endl << endl;

    insertionSort(theArray, size);
}

void insertionSort(int arr[], int size)
{
    int begin = clock(); // are for timing the sort
    for (int i = 0; i < size; i++) //does the sorting
    {
        int j = i + 1;
        int temp = arr[j];

        while (arr[i] > arr[j])
        {
            arr[j] = arr[i];
            arr[i] = temp;
            j--;
            i--;
        }
    }
    int end = clock(); // are for timing the sort

    cout << endl << "Your sorted array is: {";

    for (int i = 0; i < size; i++) // prints out sorted array
    {
        cout << arr[i];
        if (i != size - 1)
        {
            cout << ", ";
        }
        if (i % 10 == 0 && i != 0)
        {
            cout << endl;
        }
    }

    cout << "}" << endl << endl << "Your sort took: " << end - begin << " milliseconds" << endl << endl;
}

Answer 1

除了@marom 的回答，在你的 while 循环中，你没有对 i 或 j 施加限制，因此你尝试访问 arr[-1] , arr[-2] 等等。此外，您返回到排序数组的开头，因为您递减了 i。看看这段代码，用 g++ 4.8.1 编译没有错误。此外，尝试使用 header 中定义的 std::swap <utility>自 c++11 或标题 <algorithm>直到 C++11。

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <utility>

using namespace std;    

void insertionSort(int arr[], int size);

int main()
{
    int size;
    srand(time(NULL));
    cout << "Specify the size of your array: ";
    cin >> size;
    int theArray[size]; // creates an array of a size the user chooses

    cout << endl << "Your current array: {";

    for (int i = 0; i < size; i++) //prints out the original array
    {
        theArray[i] = rand() % 10000;
        cout << theArray[i];

        if (i != size - 1) // to beautify output
        {
            cout << ", ";
        }
        if (i % 10 == 0 && i != 0)
        {
            cout << endl;
        }
    }
    cout << "}" << endl << endl;

    insertionSort(theArray, size);
}

void insertionSort(int arr[], int size)
{
    int begin = clock(); // are for timing the sort
    for (int i = 0; i < size - 1; i++) //does the sorting
    {
        int j = i + 1;
        int temp = arr[j];

        while (j > 0 && arr[j] < arr[j - 1])
        {
            // ^^ this ensures that we don't try to access arr[-1]
            swap(arr[j], arr[j-1]); //prefer std functions if they do the job you want
            j--;//we don't go back
        }
    }
    int end = clock(); // are for timing the sort

    cout << endl << "Your sorted array is: {";

    for (int i = 0; i < size; i++) // prints out sorted array
    {
        cout << arr[i];
        if (i != size - 1)
        {
            cout << ", ";
        }
        if (i % 10 == 0 && i != 0)
        {
            cout << endl;
        }
    }

    cout << "}" << endl << endl << "Your sort took: " << end - begin << " milliseconds" << endl << endl;
}