0

所以我正在实施快速排序，一旦我启动程序就会出错。我认为从逻辑上讲，一切都应该没问题。我认为问题出在交换函数内，因为如果我将其注释掉，它不会崩溃。

#include <iostream>

using namespace std;

void swap1(int& x, int& y)
{
    int tmp = x;
    x = y;
    y = x;
}

int partition(int arr[], int cof, int length)
{
    int x = arr[length];
    int j = cof -1;
    for(int i = cof; length-1; i++ )
    {
        if(arr[i] <= x)
        {
            i++;
            swap1(arr[i], arr[j]);

        }
        swap1(arr[i+1], arr[length]);
    }
    return j++;
}


void quick_sort(int arr[], int cof, int length)
{
    if(cof < length)
    {
        int q = partition(arr, cof, length);
        quick_sort(arr,cof, q-1);
        quick_sort(arr,q+1, length);
    }
}

int main()
{
    int arr[]={1, 3, 2, 5, 4};
    quick_sort(arr, 1, 5);
    for(int i = 0; i < 5; i++)
    {
        cout << arr[i] << endl;
    }
    return 0;
}
4

5 回答 5

8

崩溃的主要原因！

你的情况for很奇怪：

for(int i = cof; length-1; i++ )

应该

for(int i = cof; i<length-1; i++ )
                 ^^

并更正您的交换功能：

void swap1(int& x, int& y)
{
    int tmp = x;
    x = y;
    y = tmp; // <-- use tmp
}

和许多其他错误...

例如，您arr[length]多次触摸超出范围。

另外，数组从0not开始1（见quick_sort(arr, 1, 5);：）

于 2013-04-13T16:38:23.407 回答
3

好吧，你的交换函数是错误的，但它没有任何东西会导致崩溃。注释掉它时看不到任何崩溃的原因是您的程序在swap1不是程序的一部分时永远不会写入内存。

这是您的交换功能供参考：

void swap1(int& x, int& y)
{
    int tmp = x;
    x = y;
    y = x;
}

请注意，分配后不要使用。 tmp我想你希望最后一行是：

y = tmp;

编辑：您的程序也有其他错误。例如，arr[length]不是您创建的数组的元素。

于 2013-04-13T16:35:47.177 回答
2

我相信这条线导致你的崩溃 -

int partition(int arr[], int cof, int length)
{
    int x = arr[length];

您可能需要将其更改为

int partition(int arr[], int cof, int length)
{
    int x = arr[length-1];

在您的示例main函数中，您正在创建一个长度为 5 的数组，您将 5 传递给 quick_sort 函数，该函数调用长度为 5 的分区。然后您arr[5]在分区代码中执行，但数组的最后一个元素是 4，因为数组是基于零的索引。

于 2013-04-13T16:38:33.157 回答
1

你做错了交换。将其更改为：

void swap1(int& x, int& y)
{
    int tmp = x;
    x = y;
    y = tmp;
}

您也有错误arr[length]，索引错误。您的交换功能是非常特殊的交换，而不是此时交换元素导致x两者y具有相同的值y。

于 2013-04-13T16:37:01.627 回答
0

改变交换乐趣。至：

void swap1(int& x, int& y)

{
    int tmp = x;
    x = y;
    y = tmp;        <========= here
}

当然，这不是您问题的根源。这个循环：

for (int i = cof; length-1; i++ )

看起来像永无止境的故事.. 将条件更新为您想要的任何内容。

于 2013-04-13T16:43:44.497 回答