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);
    }
}

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

c++ ceil() in stooge sort not working

c++

sorting

ceil