清启牧 发表于 2019-5-20 00:04:28

C++ 快速排序

自己写了一个C++的快排，有的时候程序能够正常执行，排序正确。有的时候程序不能执行。编译都没有问题，不能执行时返回的是， Process returned -1073741571(0xc00000FD)。请求大神帮忙看看是不是程序写得哪有问题。
#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

void swap(int* arr, int a, int b)
{
int temp = arr;
arr = arr;
arr = temp;
}

int partition(int* arr, int l, int r)
{
int less = l - 1;
int more = r;
while(l < more)
{
    if(arr <= arr)
      swap(arr, ++less, l++);
    else
      swap(arr, --more, l);
}
    swap(arr, less+1, r);
    int j = less + 1;
    return j;

}

void quickSort(int *arr, int l, int r)
{
if(r - l < 1)
    return;
if(l < r) //递归的条件很重要
{
    srand(int (time(0)));
    swap(arr, l+int(rand()%10*0.1*(r-l+1)), r);
    int p = partition(arr, l, r);
    quickSort(arr, l, p);
    quickSort(arr, p+1, r);
}
}

int main()
{
int array[] = {1,4,6,8,2,3,5};
quickSort(array, 0, 6);

for(int i = 0; i < 7; i++)
    cout << array <<" ";
cout <<endl;
return 0;
}

人造人 发表于 2019-5-20 00:10:58

void quickSort(int *arr, int l, int r)
{
if(r - l < 1)
    return;
if(l < r) //递归的条件很重要
{
    srand(int (time(0)));
    swap(arr, l+int(rand()%10*0.1*(r-l+1)), r);
    int p = partition(arr, l, r);
    quickSort(arr, l, p);
    quickSort(arr, p+1, r);
}
}

你这是要干嘛？
排序还需要srand和rand？

清启牧 发表于 2019-5-20 02:44:50

人造人 发表于 2019-5-20 00:10
你这是要干嘛？
排序还需要srand和rand？

这个地方是想随机选择比较的那个数，也可以不用。

人造人 发表于 2019-5-20 13:46:54

清启牧 发表于 2019-5-20 02:44
这个地方是想随机选择比较的那个数，也可以不用。

看这样一种情况
在main函数中调用quickSort函数传递的参数 l = 0，r = 6
在quickSort函数中调用partition函数时把 l = 0，r = 6 传给了partition
在partition函数中less = l - 1
因为l = 0，所以less = -1

第20行if(arr <= arr)
也就是if(arr[-1] <= arr)
对数组arr使用了索引 -1

清启牧 发表于 2019-5-20 17:00:32

人造人 发表于 2019-5-20 13:46
看这样一种情况
在main函数中调用quickSort函数传递的参数 l = 0，r = 6
在quickSort函数中调用partiti ...

唔，l是0呐，less才有可能是-1，arr不会索引到-1的吧？

Croper 发表于 2019-5-20 17:26:39

你的问题是快排根本就写错了。快排的轴值分割后是不参与二次排序的。而你的代码    quickSort(arr, l, p);
    quickSort(arr, p+1, r);
把轴值也拉进去参与二次排序，
那么轴值刚好就是最大的值呢？那么你此时
p==r,quickSort(arr,l,p);就成了    quickSort(arr, l, r);
，
那你这根本就是个死循环了

Croper 发表于 2019-5-20 17:28:46

改的话要把轴值剔出来    quickSort(arr, l, p-1);
    quickSort(arr, p+1, r);
另外。。我建议你还是使用左闭右开区间。。这左闭右闭区间一会多1一会少1，情况一复杂真的糟心

清启牧 发表于 2019-5-20 19:49:41

Croper 发表于 2019-5-20 17:26
你的问题是快排根本就写错了。快排的轴值分割后是不参与二次排序的。而你的代码
把轴值也拉进去参与二次排 ...

是的，我这里理解有问题，非常感谢！

人造人 发表于 2019-5-20 22:02:20

清启牧 发表于 2019-5-20 17:00
唔，l是0呐，less才有可能是-1，arr不会索引到-1的吧？

嗯，你是正确的，我也不知道中午是怎么回事，我就把l和less弄混了
^_^
页: [1]
查看完整版本: C++ 快速排序