Java中的递归Quicksort的分区实现不起作用

写了这个递归快速排序算法的Java实现，并且似乎出错了，因为我尝试排序的数组几乎完全排序，除了应该切换的两个元素（靠近数组的中间）。 我想要排序的整数数组是：4,77,98,30,20,50,77,22,49,2（10个元素）。 这是我的代码：

public static void quickSort(int[] array, int start, int end) { if (start < end) { int partition = partition(array, start, end); quickSort(array, start, partition - 1); quickSort(array, partition + 1, end); } } public static int partition(int[] array, int left, int right) { int pivotValue = array[(left + right) / 2]; //Value of middle element in array while (left <= right) { while (array[left]  pivotValue) { right++; } if (left <= right) { /* swap code */ int temporary = array[left] array[left] = array[right] array[right] = temporary; left++; right--; } } return left; } 

当我尝试这个算法时：

 int[] array = {4, 77, 98, 30, 20, 50, 77, 22, 49, 2}; quickSort(array, 0, array.length - 1); for (int i = 0; i < array.length; i++) { System.out.print(array[i] + " "); } 

打印出：2,4,20,30,22,49,50,77,77,98

任何帮助弄清楚为什么这两个元素没有正确分类将是高度赞赏。 我确信这是我在编写分区代码时遗漏的东西。 谢谢！

Answer 1

问题是你要留下1个要检查的元素
只需替换你的代码：

 quickSort(array, start, partition - 1); quickSort(array, partition + 1, end); 

有了这个 ：

 quickSort(array, start, partition - 1); quickSort(array, partition, end); 

或者用这个：

 quickSort(array, start, partition); quickSort(array, partition + 1, end); 

我现在假设原因很清楚，但请告诉我你是否需要一些解释。