我如何使这个排序算法发挥作用？

Question

我正在尝试尝试一些迭代排序算法，我正在努力使这个算法发挥作用。当我在 20 个或更少的小列表上使用它时，实际上没问题，但是当我使用 200 个或更多元素时，它会给我一个运行时错误（未处理异常）。我猜这是一个记忆问题，但我真的不知道如何继续。

我想要得到的结果是一个函数，它接受一个列表，根据元素是否大于或小于平均值将其分成两部分。然后在创建的两个新列表上再次调用该函数。 当它需要一个空列表、只有一个元素或已经排序时，它不应该执行任何操作。

错误：ConsoleApplication4.exe 中 0x00007FFF05EE5469 (ucrtbased.dll) 处出现未处理的异常：0xC00000FD：堆栈溢出（参数：0x0000000000000001、0x000000B0AB403FF8）。

#include <list>
#include <iostream>

void mySort(std::list<int>& input_list) {

    if (input_list.begin() != input_list.end()) {
        
        std::list<int> listaMin;
        std::list<int> listaMaj;
        std::list<int>::iterator it;
        bool alreadySorted = true;
        int previousValue = 0;
        int avg = 0, counter = 0;


        for (it = input_list.begin(); it != input_list.end(); it++) {
            
            if (*it >= previousValue)previousValue = *it;
            else alreadySorted = false;
            avg += *it;
            counter++;
        }
        
        if (alreadySorted == false) {

            for (it = input_list.begin(); it != input_list.end(); it++) {
                
                if (*it < (avg / counter)) { listaMin.push_front(*it); }
                else listaMaj.push_front(*it);
            }

            mySort(listaMin);
            mySort(listaMaj);

            input_list.clear();
            input_list.merge(listaMaj);
            input_list.merge(listaMin);

        }
    }
}

之后：

int main() {

    srand(time(NULL));
    std::list<int> mainList;
    for (int i = 0; i < 100; i++) mainList.push_back(rand() % 100);

    mySort(mainList);

    return 0;
}

Answer 1

您的问题是您在计算用于将列表分成两部分的平均值时使用整数除法。

将元素视为包含 3 个元素 { 1, 2, 1 } 的列表。
这将导致 avg = 4 和 counter = 3。

然后，根据每个元素是 < 还是 >= avg / counter，将列表分成两部分。

在本例中，avg / counter = 4 / 3 = 1（使用整数除法）

由于所有 3 个元素 >= 1，最终会得到包含所有 3 个元素的 listaMaj elements 和 listaMin 包含 0。

调用 mysort(listaMaj) 会导致无限递归，因为同一个列表实际上会永远不变地传递。

将 avg 变量定义为 double 而不是 int 可以解决此问题。