c++无法使选择排序正常工作

Question

我试图理解排序算法，因此基于 google 搜索示例/解释，我编写了以下代码。代码在 80% 的时间都有效。每隔一段时间它就无法正确排序，我不明白为什么。

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

using namespace std;

void setArray( int *, const int & );
void selectionSorting( int *, const int & );

int main()
{
    int numOfElem;
    cout << "Num of array elements: ";
    cin >> numOfElem;
    cout << '\n';

    int array[numOfElem];
    setArray(array, numOfElem);

    selectionSorting(array, numOfElem);

    cout << '\n';
    return 0;
}

void setArray( int *array, const int & numOfElem ){
    srand(time(0));
    cout << "Original array: " << '\n';
    for (int i=0; i<numOfElem; i++){
        array[i] = rand()%30;
        cout << array[i] << ' ';
    }
    cout << '\n';
}

void selectionSorting( int *array, const int &numOfElem ){
    int eff_size, swap;
    int maxpos = 0;
    for (eff_size = numOfElem; eff_size>1; eff_size--){
        // loop searching for a position of largest number in the array
        for (int i=0; i<eff_size; i++){
            maxpos = array[i] > array[maxpos] ? i : maxpos;
        }
        swap = array[maxpos];
        array[maxpos] = array[eff_size-1];
        array[eff_size-1] = swap;
    }
    cout << "Selection Sorting: " << '\n';
    for (int i=0; i<numOfElem; i++){
        cout << array[i] << ' ';
    }
}

示例输出:

Num of array elements: 5

Original array:
7 17 1 12 25
Selection Sorting:
1 7 17 25 12

我看不到排序失败的任何模式 - 它在不同的地方失败，天气有重复的数字，无论我提供多少数字等...

Answer 1

在外循环的每次迭代中(超过 eff_size)，您应该将 maxpos 重新设置为 0。否则您有机会 maxpos 超出了正在排序的有效部分(如果最大元素在有效部分中排在最后，即 maxpos==effsize)，就会发生这种情况。