C++中的递归选择不能完全正常工作

Question

我正在尝试编写一个递归函数，该函数按选择对小数组进行排序。我可以加载和运行所有内容，但是{3, 1, 8, 5}数组时的输出一直以{1, 3, 3, 3}的形式输出。我认为这与最小值的分配方式有关，但我被困在确切的位置上。有什么建议吗？

#include <iostream>
#include <conio.h>
#include <array>
using namespace std;
int arrLength = 4;
int minimum;
int counter = 0;
int sortedArr[];
int tempArr[];
void sortFunc(int, int);
int valueArr[4] = { 3,1,8,5 };
int tempArr[4] = {};
void main() {
    cout << "Before sorting..." << endl;
    for (int i = 0; i < 4; i++) {
        cout << valueArr[i] << " ";
    }
    cout << endl;
    sortFunc(4, counter);
    cout << "After sorting..." << endl;
    for (int i = 0; i < 4; i++) { //either broken here
        cout << tempArr[i] << " ";
    }
    _getch();
}
void sortFunc(int size, int counter) {
    minimum = valueArr[0];
    for (int i = 1 + (counter); i <  size; i++) { //or here
        if (valueArr[i] < minimum) {
            minimum = valueArr[i];
        }
    }
    tempArr[counter] = minimum;
    if (counter < size) {
        counter++;
        sortFunc(size, counter);
    }
}

Answer 1

我无法清楚地看到如何稍微调整您的策略以使您的函数正常工作。我认为您需要通过交换元素对数组进行排序。为此，您需要：

1. 首先将valueArr复制到tempArr。
2. tempArr排序到位。这使valueArr处于原始状态。我假设这是你的意图。

在main中，使用：

// Copy valueArr to tempArr
std::copy(valueArr, valueArr+4, tempArr);

在sortFunc中，使用：

void sortFunc(int size, int counter) {
   if ( size == counter )
   {
      return;
   }
    int minimum = tempArr[counter];
    for (int i = 1 + (counter); i <  size; i++) {
        if (tempArr[i] < minimum) {
            minimum = tempArr[i];
            std::swap(tempArr[counter], tempArr[i]); 
        }
    }
    sortFunc(size, counter+1);
}

---

进一步清理的建议。

1. 不要使用任何全局变量。
2. 将所有参数传递给 sortFunc 。
3. 将main的返回类型更改为 int 。

这是一个清理过的版本。

#include <iostream>
#include <algorithm>
using namespace std;
void sortFunc(int arr[], int, int);
int main() {
    cout << "Before sorting..." << endl;
    int valueArr[4] = { 3,1,8,5 };
    int tempArr[4] = {};
    for (int i = 0; i < 4; i++) {
        cout << valueArr[i] << " ";
    }
    cout << endl;
    // Copy valueArr to tempArr
    std::copy(valueArr, valueArr+4, tempArr);
    sortFunc(tempArr, 4, 0);
    cout << "After sorting..." << endl;
    for (int i = 0; i < 4; i++) { //either broken here
        cout << tempArr[i] << " ";
    }
    cout << endl;
}
void sortFunc(int arr[], int size, int counter) {
   if ( size == counter )
   {
      return;
   }
    int minimum = arr[counter];
    for (int i = 1 + (counter); i <  size; i++) {
        if (arr[i] < minimum) {
            minimum = arr[i];
            std::swap(arr[counter], arr[i]); 
        }
    }
    sortFunc(arr, size, counter+1);
}

Answer 2

我相信

你不应该在行初始化最小值

minimum = valueArr[0];

相反，只需将其分配给大量或使用valueArr[counter + 1]

这种奇怪行为的原因可能是 valueArr 中的第一个条目实际上比您稍后在数组中遇到的条目小，因此它不会正确初始化......

添加：请参阅INT_MAX或numeric_limits中的"大量">

---

ADD2：无论如何，仔细观察，你的递归有不正确的概念......如果您打算对数组进行排序，则必须始终将当前元素与您在每次迭代中选择的元素交换。否则，您将开始丢失元素，就像您一样。无论如何，递归可能不是解决排序的最佳方法......也许尝试两个嵌套循环

Answer 3

你的代码中有一些基本的逻辑错误，

void sortFunc(int size, int counter) {
    minimum = 2147483647; // Point 1
    int mytemp;
    for (int i = 0; i <  size; i++) { // Point 3
        if (valueArr[i] < minimum) {
            minimum = valueArr[i];  //Point 2
            mytemp = i;
        }
    }
    valueArr[mytemp] = 2147483647;
    tempArr[counter] = minimum;
    if (counter < size) {
        counter++;
        sortFunc(size, counter);
    }
}

1. minimum变量应始终是最大可能值，您需要跟踪valueArr中最小值的索引

2. 在valueArr中找到最小值后，您需要确保不会再次访问相同的值，因此请跟踪它的索引并在必要时更改其值

3. 循环可迭代从代码中的1+(counter)开始，如果最小值在那之前怎么办？这就是为什么你需要从头开始。

我希望你明白我的意思。干杯！

Answer 4

除了 R Sahu 的答案中提供的有用建议和技巧外，以下函数模板还可以用作选择排序算法的类似递归 STL 的实现：

#include <iterator>   // std::next
#include <algorithm>  // std::min_element
template<typename ForwardIt>
void sortFunc(ForwardIt first, ForwardIt last) {
    // base case
    if (first == last || std::next(first) == last)
        return; // empty range or range with a single element
    // recursive case
    auto selected_it = std::min_element(first, last);
    using std::swap;
    swap(*selected_it, *first);
    return selection_sort(++first, last);
}

这样，可以在实现operator<的任何类型上执行选择排序，并且不仅限于int(如在您的sortFunc()中(。

上面的实现允许进行尾递归优化，因此，如果您要对大型数组(或其他集合(进行排序，请不要忘记启用它。

---

您可以将上面的sortFunc函数模板与 C 样式数组一起使用(如示例中所示(：

// copy valueArr to tempArr
std::copy(valueArr, valueArr+4, tempArr);
// sort tempArr
sortFunc(tempArr, tempArr+4);

以及实现前向迭代器的任何 STL 容器：

std::vector<int> vec(valueArr, valueArr+4);
std::list<int> lst(valueArr, valueArr+4);
std::forward_list<int> fwdlst(valueArr, valueArr+4);
sortFunc(vec.begin(), vec.end());
sortFunc(lst.begin(), lst.end());
sortFunc(fwdlst.begin(), fwdlst.end());