[已解决]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[a];
  arr[a] = arr[b];
  arr[b] = temp;
}

int partition(int* arr, int l, int r)
{
  int less = l - 1;
  int more = r;
  while(l < more)
  {
    if(arr[l] <= arr[r])
      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[i] <<" ";
  cout <<endl;
  return 0;
}

最佳答案

月排行榜 / 总排行榜

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

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

跳转到最佳答案楼层

人造人

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 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

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

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

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

quickSort(arr,l,p);

就成了

    quickSort(arr, l, r);

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

Croper

改的话要把轴值剔出来

    quickSort(arr, l, p-1);
    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弄混了
^_^