c++ ceil() in stooge sort 不工作

Question

我正在实现走狗排序。

void stoogeSort(int arr[], int low, int high)
{   
    int size = high - low + 1;

    if (size == 2 && arr[0] > arr[1])
    {
        int temp = arr[0];
        arr[0] = arr[1];
        arr[1] = temp;
    }

    else if (size > 2)
    {
        int mid = (int) ceil((2 * size) / 3);
        stoogeSort(arr, low, mid - 1);
        stoogeSort(arr, size - mid, high);
        stoogeSort(arr, low, mid - 1);
    }
}

int mid = (int) ceil((2 * size) / 3) 似乎有问题因为它没有返回正确的数字。例如，如果 size 计算为 4，则 mid 应为 3，因为 (2 * 4)/3 的上限为 3。但是，它为 2。

我有#include <cmath>和 using std::ceil在那之下。无论我进行何种类型转换，它要么持有错误的数字，要么最终在该函数的顶部抛出堆栈溢出错误。有任何想法吗？谢谢!

注意:将 3 更改为 3.0 会导致函数顶部发生堆栈溢出错误

Answer 1

int mid = (int) ceil((2 * size) / 3);

您正在进行整数除法并将结果传递给 ceil()。因此，ceil() 调用无效。

尝试这样的事情:

int mid = ((2 * size) + 2) / 3;

---

但这并不能解决您真正的问题。你的算法有几个错误。继续执行 Wikipedia这部分:

if (size == 2 && arr[0] > arr[1])
{
    int temp = arr[0];
    arr[0] = arr[1];
    arr[1] = temp;
}

应该是这样的:

if (arr[low] > arr[high])
{
    std::swap(arr[low], arr[high]);
}

这部分:

else if (size > 2)

应该是:

if (size > 2)

这个:

int mid = (int) ceil((2 * size) / 3);

应该是:

int mid = size / 3;

还有这个:

stoogeSort(arr, low, mid - 1);
stoogeSort(arr, size - mid, high);
stoogeSort(arr, low, mid - 1);

应该是:

stoogeSort(arr, low, high - mid);
stoogeSort(arr, low + mid, high);
stoogeSort(arr, low, high - mid);

您应该注意 mid 不是中间元素的索引。它是您添加到 low 或从 high 中减去的大小。它可能小于 low。因此，名称 mid 具有误导性。

---

将它们拼接在一起你会得到这个:

void stoogeSort(int arr[], int low, int high)
{   
    if (arr[low] > arr[high])
    {
        std::swap(arr[low], arr[high]);
    }
    int size = high - low + 1;
    if (size > 2)
    {
        int mid = size / 3;
        stoogeSort(arr, low, high - mid);
        stoogeSort(arr, low + mid, high);
        stoogeSort(arr, low, high - mid);
    }
}