Quicksort 给出 StackOverFlow 错误

Question

我正在尝试编写快速排序算法。我按照在线教程进行了几乎相同的操作，但我遇到了 Whosebug 错误。

public void mysort(int[] g) {
    quickSort(g, 0, g.length - 1);

    System.out.println(Arrays.toString(g));
}

public void quickSort(int[] nums, int low, int high) {
    int i = low;
    int j = high;

    int pivot = nums[(low + (high - low)) / 2];

    while (i <= j) {

        while (nums[i] < nums[pivot]) {
            i++;
        }

        while (nums[j] > nums[pivot]) {
            j--;
        }

        while (i <= j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            i++;
            j--;
        }
    }

    System.out.println(Arrays.toString(nums));

    if (low < j) {
        quickSort(nums, low, j);
    }

    if (i < high) {
        quickSort(nums, i, high);
    }
}

我作为参数传递的数组是 [1, 2, 3, 4, 5, 5, 4, 3, 2, 1]。

在quicksort方法中，println语句在第一次循环后输出这个，[1, 4, 3, 2, 1, 2, 3, 4, 5, 5]。

这是怎么回事？

Answer 1

你计算的枢轴是错误的，不是：

int pivot = nums[(low + (high - low)) / 2];

是：

int pivot = nums[low +  ((high - low) / 2)];

数学中的

Division 比 sum 和 sub

具有更高的优先级

换句话说，你可以写成：

int pivot = nums[low +  (high - low) / 2];

还有一个问题你会发现，在你的while中，你不是在求pivot，你是在求pivotnums[pivot]位置的数，应该是：

  while (array[i] < pivot) {
    i++;
  }

  while (array[j] > pivot) {
    j--;
  }

最后，不是交流while i<=j是：

  if (i <= j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
    i++;
    j--;
  }

Quicksort 给出 StackOverFlow 错误

Quicksort giving StackOverFlow error

java

sorting

quicksort