c++ - 在 C++ 中快速排序 boolean 数组

Question

美好的一天!我们被要求对一个 boolean 数组进行排序，但问题是当我运行我的程序时，它总是停止工作。我尝试打印 boolean 数组中的值并且打印了它们但是当我尝试注入(inject)快速排序函数时，未排序的值不再打印，数组也没有排序。此代码对除 Boolean 之外的不同数据类型进行排序。我希望你能帮我找到问题所在。谢谢。

void swap(bool &a, bool &b)
{
  int temp;
  temp = a;
  a = b;
  b = temp;
}

void sortArray(bool* arr, int start, int end)
{
   int pivot = arr[start];
   int p;

   if(end > start)
   {
     p = partition(arr, pivot, start, end);
     arr[p] = pivot;
     sortArray(arr, start, p);
     sortArray(arr, p+1, end);
   }

}

int partition(bool* arr, int pivot, int start, int end)
{
  int header = start;
  int p = end;

  while(header < p)        
  {
    while( pivot < arr[p] && p > header)   
    {
        p=p-1;            
    }
    swap(arr[header], arr[p]);


    while( pivot >= arr[header] && header < p)    
    {
       header++;            
    }
    swap(arr[p], arr[header]);

   }
   return header;
}

Answer 1

boolean 类型在这里有优势。您可以简单地计算 true 的数量。

在这种情况下排序函数应该是这样的:

void sortArray(bool* arr, int start, int end)
{
    int true_count = 0;
    for (int i = start; i != end; ++i) {
        if (arr[i]) {
            ++true_count;
        }
    }

    int true_range_end = start + true_count;

    // Here go true
    for (int i = start; i != true_range_end; ++i) {
        arr[i] = true;
    }

    // Here go false
    for (int i = true_range_end; i != end; ++i) {
        arr[i] = false;
    }
}

请注意这是一个降序(true 在前)。