[已解决]C++ 快速排序

清启牧

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

1. #include <iostream>
   
2. #include <cstdlib>
   
3. #include <ctime>
   
4. 
   
5. using namespace std;
   
6. 
   
7. void swap(int* arr, int a, int b)
   
8. {
   
9.   int temp = arr[a];
   
10.   arr[a] = arr[b];
    
11.   arr[b] = temp;
    
12. }
    
13. 
    
14. int partition(int* arr, int l, int r)
    
15. {
    
16.   int less = l - 1;
    
17.   int more = r;
    
18.   while(l < more)
    
19.   {
    
20.     if(arr[l] <= arr[r])
    
21.       swap(arr, ++less, l++);
    
22.     else
    
23.       swap(arr, --more, l);
    
24.   }
    
25.     swap(arr, less+1, r);
    
26.     int j = less + 1;
    
27.     return j;
    
28. 
    
29. }
    
30. 
    
31. void quickSort(int *arr, int l, int r)
    
32. {
    
33.   if(r - l < 1)
    
34.     return;
    
35.   if(l < r) //递归的条件很重要
    
36.   {
    
37.     srand(int (time(0)));
    
38.     swap(arr, l+int(rand()%10*0.1*(r-l+1)), r);
    
39.     int p = partition(arr, l, r);
    
40.     quickSort(arr, l, p);
    
41.     quickSort(arr, p+1, r);
    
42.   }
    
43. }
    
44. 
    
45. int main()
    
46. {
    
47.   int array[] = {1,4,6,8,2,3,5};
    
48.   quickSort(array, 0, 6);
    
49. 
    
50.   for(int i = 0; i < 7; i++)
    
51.     cout << array[i] <<" ";
    
52.   cout <<endl;
    
53.   return 0;
    
54. }
    

复制代码

最佳答案

月排行榜 / 总排行榜

Croper

2019-5-20 17:26:39

你的问题是快排根本就写错了。快排的轴值分割后是不参与二次排序的。而你的代码

1.     quickSort(arr, l, p);
   
2.     quickSort(arr, p+1, r);

复制代码

把轴值也拉进去参与二次排序，
那么轴值刚好就是最大的值呢？那么你此时
p==r,

1. quickSort(arr,l,p);

复制代码

就成了

1.     quickSort(arr, l, r);
   

复制代码

，
那你这根本就是个死循环了

跳转到最佳答案楼层

人造人

1. void quickSort(int *arr, int l, int r)
   
2. {
   
3.   if(r - l < 1)
   
4.     return;
   
5.   if(l < r) //递归的条件很重要
   
6.   {
   
7.     srand(int (time(0)));
   
8.     swap(arr, l+int(rand()%10*0.1*(r-l+1)), r);
   
9.     int p = partition(arr, l, r);
   
10.     quickSort(arr, l, p);
    
11.     quickSort(arr, p+1, r);
    
12.   }
    
13. }

复制代码

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

清启牧

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

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

人造人

清启牧 发表于 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[l] <= arr[r])
也就是if(arr[-1] <= arr[r])
对数组arr使用了索引 -1

清启牧

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

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

Croper

你的问题是快排根本就写错了。快排的轴值分割后是不参与二次排序的。而你的代码

1.     quickSort(arr, l, p);
   
2.     quickSort(arr, p+1, r);

复制代码

把轴值也拉进去参与二次排序，
那么轴值刚好就是最大的值呢？那么你此时
p==r,

1. quickSort(arr,l,p);

复制代码

就成了

1.     quickSort(arr, l, r);
   

复制代码

，
那你这根本就是个死循环了

Croper

改的话要把轴值剔出来

1.     quickSort(arr, l, p-1);
   
2.     quickSort(arr, p+1, r);

复制代码

另外。。我建议你还是使用左闭右开区间。。这左闭右闭区间一会多1一会少1，情况一复杂真的糟心

清启牧

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

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

人造人

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

嗯，你是正确的，我也不知道中午是怎么回事，我就把l和less弄混了
^_^