英文:
Quick Sort not working as expected in java
问题
以下是翻译好的部分：
我学习了关于快速排序的理论。我尝试在Java中实现这个算法，但我发现并没有所有的数字都被排序。我无法指出我在哪里犯了错误。
QuickSort.java
public class QuickSort {
public void quicksort(int[] arr, int lb, int ub) {
// up=upper bound
// lb=lower bound
if (lb < ub) {
int loc = partition(arr, lb, ub);
quicksort(arr, lb, loc - 1);
quicksort(arr, loc + 1, ub);
}
}
public int partition(int[] arr, int lb, int ub) {
int pivot = arr[lb];
int start = lb;
int end = ub - 1;
while (start < end) {
while (arr[start] <= pivot && start < arr.length - 1) {
start++;
}
while (arr[end] > pivot) {
end--;
}
if (start < end) {
swap(start, end, arr);
}
}
swap(lb, end, arr); // 用末尾元素交换中心值（pivot）
return end;
}
public void swap(int start, int end, int[] arr) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
}
}
Main class:
import java.util.Arrays;
public class Program {
public static void main(String[] args) {
int[] arr = {7, 6, 10, 5, 9, 2, 1, 15, 7};
QuickSort q = new QuickSort();
q.quicksort(arr, 0, arr.length);
System.out.println(Arrays.toString(arr));
}
}
我的输出结果是：
[2, 5, 6, 7, 1, 7, 9, 10, 15]
我重新检查了我的代码并进行了一些调试，但在第一次通过时它运行得很好。我不知道，在哪个点上出错了？
英文:
I learned the theory about QuickSort. I tried to implement this algorithm in java but I am not seeing all the numbers are being sorted.I am not able to point out what mistake I am making.
QuickSort.java
public class QuickSort {
public void quicksort(int[] arr, int lb, int ub) {
//up=upper bound
//lb=lower bound
if(lb<ub) {
int loc=partition(arr,lb,ub);
quicksort(arr,lb,loc-1);
quicksort(arr,loc+1,ub);
}
}
public int partition(int[] arr,int lb,int ub) {
int pivot=arr[lb];
int start=lb;
int end=ub-1;
while(start<end) {
while(arr[start]<=pivot && start<arr.length-1) {
start++;
}
while(arr[end]>pivot) {
end--;
}
if(start<end) {
swap(start,end,arr);
}
}
swap(lb,end,arr); //swapping pivot value with end
return end;
}
public void swap(int start,int end,int[] arr) {
// System.out.println(end+" "+pivot);
int temp=arr[start];
arr[start]=arr[end];
arr[end]=temp;
}
}
Main class:
import java.util.Arrays;
public class Program {
public static void main(String[] args) {
int[] arr= {7,6,10,5,9,2,1,15,7};
QuickSort q=new QuickSort();
q.quicksort(arr,0,arr.length);
System.out.println(Arrays.toString(arr));
}
}
My output coming is:
[2, 5, 6, 7, 1, 7, 9, 10, 15]
I rechecked my code and done some debugging but for first pass it is working fine.I dont know,at what point it is being wrong?
答案1
得分: 1
这位仁兄恰好做了你要寻找的内容 
在这里查看他的 partition 函数：
https://stackoverflow.com/questions/13543843/random-pivot-quicksort-in-java
以下是你可以为辅助函数做的事情：
public static void sort(int arr[], int lb, int ub) {
if (lb < ub) {
int part = partition(arr, lb, ub);
// 对分区进行排序
sort(arr, lb, part - 1);
sort(arr, part + 1, ub);
}
}
public static void displayArray(int[] arr) {
System.out.print("[ ");
for (int x :
arr) {
System.out.print(x + " ");
}
System.out.print("]");
}
public static void main(String[] args) {
int[] arr = {7, 6, 10, 5, 9, 2, 1, 15, 7};
int len = arr.length;
displayArray(arr);
sort(arr, 0, len-1);
System.out.println();
displayArray(arr);
}
英文:
This dude made exactly what you are looking for take a look at his
partition function here:
https://stackoverflow.com/questions/13543843/random-pivot-quicksort-in-java
Here is what you can do for the helper functions:
public static void sort(int arr[], int lb, int ub) {
if (lb < ub) {
int part = partition(arr, lb, ub);
// Sorts the partitions
sort(arr, lb, part - 1);
sort(arr, part + 1, ub);
}
}
public static void displayArray(int[] arr) {
System.out.print("[ ");
for (int x :
arr) {
System.out.print(x + " ");
}
System.out.print("]");
}
public static void main(String[] args) {
int[] arr = {7, 6, 10, 5, 9, 2, 1, 15, 7};
int len = arr.length;
displayArray(arr);
sort(arr, 0, len-1);
System.out.println();
displayArray(arr);
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论