当数组中包含负数时，快速排序会引发堆栈溢出错误 (Dart)

Question

我正在尝试在 dart 中实现快速排序，当我不包含负数时，下面的代码工作正常。但是，每当我在数组中包含负数时，都会出现堆栈溢出错误。如果有人能指出我做错了什么的正确方向，我会很高兴。

main() {

  // The Partition Function

  int partitionArray(List array, int lowerbound, int upperbound) {
    int start = lowerbound;
    int end = upperbound;
    int pivotElement = array[lowerbound];

    while (start < end) {
      while (array[start] <= pivotElement) {
        start++;
      }

      while (array[end] > pivotElement) {
        end--;
      }

      // Swap the elements
      if (start < end) {            
        int swapHolder;
        swapHolder = array[start];
        array[start] = array[end];
        array[end] = swapHolder;
      }
    }

    // Swap Pivot element and current element at end
    int pivotSwapHolder;
    pivotSwapHolder = array[lowerbound];
    array[lowerbound] = array[end];
    array[end] = pivotSwapHolder;

    return end;
  }

  List arr = [ 7,5,6,3,7,-5,3,8,];

  

  quickSortElements(List arr, int lower, int upper) {
    if (lower < upper) {
      int midLocation = partitionArray(arr, lower, arr.length - 1);
      quickSortElements(arr, lower, midLocation - 1);
      quickSortElements(arr, midLocation + 1, upper);
    }
    print(arr);
  }

  quickSortElements(arr, 0, arr.length - 1);
}

Answer 1

您的错误不是由于数组中的负值引起的，它可能是任何低值，您也会遇到同样的问题。您犯的错误是在对 quickSortElements 的递归调用中将 arr.length - 1 作为上限值传递。见下文，我在评论中已更正的行：

quickSortElements(List arr, int lower, int upper) {
  if (lower < upper) {
    //int midLocation = partitionArray(arr, lower, arr.length - 1);
    int midLocation = partitionArray(arr, lower, upper); // corrected line
    quickSortElements(arr, lower, midLocation - 1);
    quickSortElements(arr, midLocation + 1, upper);
  }
}

当数组中包含负数时，快速排序会引发堆栈溢出错误 (Dart)

Quick Sort throws a Stack Overflow error when negative number is included in the array (Dart)

dart

data-structures

quicksort