2

我的任务是在 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);
}
4

1 回答 1

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迭代器（程序中的大小）。

当然，这有一个尾递归，可以很容易地被一个外部循环取出，返回通常的迭代实现。

于 2013-09-16T08:08:39.670 回答