为什么我在快速排序时遇到分段错误

Question

我在运行快速排序算法时遇到分段错误。这是我的代码

排序.h

    class Sortings {
     public:
      static void QuickSort(int* array, int size);
     private:
      static int partition(int* array, int l, int r);
      static void Quicksort_helper(int* array, int l, int r);
    };

排序.cpp

#include "Sortings.h"
void Sortings::QuickSort(int* array, int size){
  Quicksort_helper(array, 0, size);
}
int Sortings::partition(int* array, int l, int r){
  int p = array[l];
  int i = l;
  int j = r + 1;
  while (!(i <= j)){
    while (!(array[i] >= p))
      i = i+1;
    while (!(array[j] <=  p))
      j = j-1;
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }
  int temp2 = array[i];
  array[i] = array[j];
  array[j] = temp2;
  int temp3 = array[l];
  array[l] = array[j];
  array[j] = temp3;
  return j;
}
void Sortings::Quicksort_helper(int* array, int l, int r){
  if (l < r){
    int s = partition(array, l, r);
    Quicksort_helper(array, l, (s-1));
    Quicksort_helper(array, (s+1), r);
  }
}

在主.cpp我使用输入数组和大小变量调用快速排序。为什么在运行主.cpp时出现分段错误？

Answer 1

您将大小作为 r 传递。 你设置 j=r+1。 你循环 i=l 到 j。 这超出了您的阵列范围。 有效边界为 [0，r-1]。 你循环到 r+1。 那是你的问题。

Answer 2

大小传递给 r，然后有索引 #

 int j = r + 1;
 ...
 while (!(array[j] <=  p))
     j = j-1;

如果大小真的是"大小"，那么你就不在数组中了。

或：

Quicksort_helper(array, 0, size - 1);