c++ - 在 C++ 中多次运行按引用选择排序函数

Question

我的任务是用 C++ 创建一个递归选择排序函数。它在第一次调用 main 时按预期运行，但第二次在 while 循环主菜单中选择“选择排序”会产生一些奇怪的结果。我不确定它是否与引用传递、selectionSort() 中的静态变量或其他完全不同的东西有关。

#include <iostream>
#include <array>
#include <algorithm>
#include <stdlib.h>
#include <time.h>

using namespace std;

//Function Prototypes
void selectionSort(array<int, 10> &arrayRef, size_t size); //Passes a size 10 int array by ref
void rollDice(unsigned int numRolls); //Parameter is number of times the two die should roll

int main()
{
    int usrIn;

    cout << "Welcome to Program Assignment 2!";

    while (true) //Main Menu Loop
    {
        srand(time(NULL));
        cout << "\n\n1) Selection Sort\n2)Roll Dice Simulation\n3)End The Program\nSelect an Option."
            << endl;

        cin >> usrIn;

        if (usrIn == 1)
        {
            cout << "Maximum value for array variables to be sorted: " << endl;
            cin >> usrIn; //Retrieves the user input max int value for the array's number generator
            array<int, 10> arrayToSort; //Initializes the test array of size 10

            for (int &val : arrayToSort) //Generates values for the array
                val = rand() % usrIn + 1;

            cout << "\nbefore sort:\n";
            for (int val : arrayToSort) //Displays numbers before the array is sorted
                cout << val << " ";

            selectionSort(arrayToSort, 10); //Sorts the array in numerical order

            cout << "\nafter sort:\n";
            for (int val : arrayToSort) //Displays numbers after the array is sorted
                cout << val << " ";

        }
    }


    return 0;
}

void selectionSort(array<int, 10> &arrayRef, size_t size)
{
    static int counter = 0;

    if (size <= 1)
        return;

    for (int i = counter; i < arrayRef.size(); i++)
    {
        if (arrayRef[i] < arrayRef[counter])
        {
            swap(arrayRef[i], arrayRef[counter]);
        }
    }

    counter++;
    selectionSort(arrayRef, size - 1);
}

Answer 1

您的代码相当笨拙，所以我不会尝试重构它。相反，请考虑使用选择排序的这种通用递归实现(使用 C++11 默认函数模板参数)

template<class ForwardIterator, class Compare = std::less<typename std::iterator_traits<ForwardIterator>::value_type>>
void selection_sort(ForwardIterator first, ForwardIterator last, Compare cmp = Compare{})
{
        if (first == last) return;
        auto const selection = std::min_element(first, last, cmp);
        std::iter_swap(selection, first);
        selection_sort(++first, last, cmp);
}

这里的关键是递增 first 迭代器(指向程序中第一个数组元素的指针)，而不是递减 last 迭代器(程序中的大小) .

当然，这有一个尾递归，可以很容易地通过外部循环将其移除，从而返回通常的迭代实现。