英文:
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 boundif (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 boundif(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 endreturn 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 partitionssort(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);}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论