c++ - 为什么我的快速排序对大于 ~35000 的数组不起作用？ (C++)

Question

这是我的拙劣实现:

void partition(people * arr, int size){
  if(size <= 1)
    return;

  people pivot = arr[rand() % size];
  int low = 0;
  int high = size - 1;

  while(low < high){
    while(  (arr[low].lname < pivot.lname) || (  (arr[low].fname <  pivot.fname) && (arr[low].lname == pivot.lname)  ) ||
    (  (arr[low].fname ==  pivot.fname) && (arr[low].lname == pivot.lname) && (arr[low].dob < pivot.dob)  )   )
        low += 1;

    while(arr[high].lname > pivot.lname  || ((arr[high].fname > pivot.fname)&&(arr[high].lname == pivot.lname)) ||
    ( (arr[high].fname ==  pivot.fname)&& (arr[high].lname == pivot.lname) && (arr[high].dob > pivot.dob) )   )
        high -= 1;

    people temp = arr[low];
    arr[low] = arr[high];
    arr[high] = temp;
   }

   partition(arr, low);
   partition(&(arr[low+1]), size - low - 1);
}



void kwiksort(people * arr, int size)
{  srand((unsigned int)time(0));
   partition(arr,size);
}

该程序的行为就好像它处于无限循环中并且基本上卡住了。另外，如果有人能指出一些优化快速排序的方法，那就太好了。

Answer 1

我怀疑问题在于您对变量 size 使用了 int 类型。

普通的 int 变量，如果我没记错的话，最多只能取 2^15-1 或 32767 的值。如果值更大，它将循环为负数.这在使用 if 语句等时可能会导致问题。

不要使用 int size 声明 size，尝试使用 long size 或 long long size。长整数和长长整数可以取比常规整数更大的值。