英文:
Java QuickSort algorithm
问题
以下是已翻译的代码部分：
import java.util.Arrays;
public class JavaFiddle {
static int[] myArray = new int[]{35, 12, 25, 1, 5, 33, 56};
public static void QuickSort(int[] array) {
QuickSort(array, 0, array.length - 1);
}
public static void QuickSort(int[] array, int left, int right) {
if (left < right) {
int pivot = left + ((right - left) / 2);
int index = partition(array, left, right, pivot);
QuickSort(array, left, index - 1);
QuickSort(array, index + 1, right);
}
}
public static int partition(int[] array, int left, int right, int pivot) {
while (left < right) {
while (array[left] < pivot) {
left++;
}
while (array[right] > pivot) {
right--;
}
if (left < right) {
swap(array, left, right);
left++;
right--;
}
}
return left;
}
public static void swap(int[] array, int left, int right) {
int temp = array[left];
array[left] = array[right];
array[right] = temp;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(myArray));
QuickSort(myArray);
System.out.println(Arrays.toString(myArray));
}
}
然而，这段代码给我错误的结果：
[35, 12, 25, 1, 5, 33, 56] - 排序前
[1, 12, 25, 35, 5, 33, 56] - 排序后
我在这里有什么问题？我无法找到逻辑上的错误。
英文:
I am trying to learn Quick Sort algorithm and this is my code so far:
import java.util.Arrays;
public class JavaFiddle {
static int[] myArray = new int[]{35, 12, 25, 1, 5, 33, 56};
public static void QuickSort(int[] array) {
QuickSort(array, 0, array.length - 1);
}
public static void QuickSort(int[] array, int left, int right) {
if (left < right) {
int pivot = left + ((right - left) / 2);
int index = partition(array, left, right, pivot);
QuickSort(array, left, index - 1);
QuickSort(array, index + 1, right);
}
}
public static int partition(int[] array, int left, int right, int pivot) {
while (left < right) {
while (array[left] < pivot) {
left++;
}
while (array[right] > pivot) {
right--;
}
if (left < right) {
swap(array, left, right);
left++;
right--;
}
}
return left;
}
public static void swap(int[] array, int left, int right) {
int temp = array[left];
array[left] = array[right];
array[right] = temp;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(myArray));
QuickSort(myArray);
System.out.println(Arrays.toString(myArray));
}
}
However, this code gives me an incorrect result:
[35, 12, 25, 1, 5, 33, 56] - before sort
[1, 12, 25, 35, 5, 33, 56] - after sort
What do I have wrong here? I cannot find the flaw in the logic.
答案1
得分: 1
多处错误，您在主方法中定义了pivot，但快速排序算法会将pivot从右侧元素交换到中间位置。您在while循环中编辑了左右值，这会导致右侧和左侧的值比pivot小/大，从而跳过一些交换。以下是正确的实现，去除了您的while { while { ... } }结构，并使用了正确的pivot（从右侧到中间位置）。
import java.util.Arrays;
public class Main {
static int[] myArray = new int[] {35, 12, 25, 1, 5, 56, 33};
public static void QuickSort(int[] array) {
QuickSort(array, 0, array.length - 1);
}
public static void QuickSort(int[] array, int left, int right) {
if (left < right) {
int index = partition(array, left, right);
QuickSort(array, left, index - 1);
QuickSort(array, index + 1, right);
}
}
public static int partition(int[] array, int left, int right) {
int pivotIndex = (left + right) / 2;
int pivotValue = array[pivotIndex];
swap(array, pivotIndex, right);
int first = left - 1;
for (int j = left; j <= right - 1; j++) {
if (array[j] < pivotValue) {
first++;
swap(array, first, j);
}
}
swap(array, first + 1, right);
return first + 1;
}
public static void swap(int[] array, int left, int right) {
int temp = array[left];
array[left] = array[right];
array[right] = temp;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(myArray));
QuickSort(myArray);
System.out.println(Arrays.toString(myArray));
}
}
此外，您在代码中比较了pivot（一个索引）与array[...]（一个值）。
英文:
Multiple errors here,
You define pivot in main method, but quick sort algorithm will swap pivot from right element to the middle.
You edit left and right values in your while loop in a while loop, which result right and left to be smaller/taller than your pivot and skipping some swaps.
Here's the correct implementation without your while { while { ... } } and a correct pivot (from right to middle)
import java.util.Arrays;
public class Main
{
static int[] myArray = new int[] {35, 12, 25, 1, 5, 56, 33};
public static void QuickSort(int[] array) {
QuickSort(array, 0, array.length - 1);
}
public static void QuickSort(int[] array, int left, int right){
if(left < right) {
int index = partition(array, left, right);
QuickSort(array, left, index - 1);
QuickSort(array, index + 1, right);
}
}
public static int partition(int[] array, int left, int right){
int pivot = array[right];
int first = left - 1;
for (int j = left; j <= right - 1; j++) {
if(array[j] < pivot) {
first ++;
swap(array, first, j);
}
}
swap(array, first + 1, right);
return first + 1;
}
public static void swap(int[] array, int left, int right) {
int temp = array[left];
array[left] = array[right];
array[right] = temp;
}
public static void main(String[] args)
{
System.out.println(Arrays.toString(myArray));
QuickSort(myArray);
System.out.println(Arrays.toString(myArray));
}
}
Also you compare pivot which is an index with array[...] which is a value
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论