我正在实现一个算法，使用快速选择找到未排序数组中的第K个最小元素。 我不知道我在哪里弄错了。 我使用快速排序版本来找到第k个最小元素。 而不是通过两个分区递归，我只是通过一个递归。 谁能帮我这个。
public class quickselect { public static void main(String[] args){ int[] a={1,5,3,4,8,11}; int ans=quick_select(a, 4, 0, a.length-1); System.out.println(ans); } private static int quick_select(int[] a, int k, int left, int right) { int pivot=findpivot(a,left,right); if(pivot==k-1){ return a[pivot]; } if(k-1<pivot){ return quick_select(a, k, left, pivot-1); } else { return quick_select(a, k, pivot+1, right); } } private static int findpivot(int[] a, int left, int right) { int pivot = a[(left+right)/2]; while(left<=right){ while(a[left]<pivot){ left++; } while(a[right]>pivot){ right--; } if(left<=right){ swap(a,left,right); left++; right--; } } return left; } private static void swap(int[] a, int i, int j) { int temp=a[i]; a[i]=a[j]; a[j]=temp; } }如果有人能解释我的错误将会在哪里，我真的很感激。
I am implementing an algorithm to find the Kth smallest element in an unsorted array using quick select. I am not sure where I am making a mistake. I am using the version of quick sort to find the kth smallest element. Rather than recursing through both partition , I am only recursing through one. Can anyone help me with this.
public class quickselect { public static void main(String[] args){ int[] a={1,5,3,4,8,11}; int ans=quick_select(a, 4, 0, a.length-1); System.out.println(ans); } private static int quick_select(int[] a, int k, int left, int right) { int pivot=findpivot(a,left,right); if(pivot==k-1){ return a[pivot]; } if(k-1<pivot){ return quick_select(a, k, left, pivot-1); } else { return quick_select(a, k, pivot+1, right); } } private static int findpivot(int[] a, int left, int right) { int pivot = a[(left+right)/2]; while(left<=right){ while(a[left]<pivot){ left++; } while(a[right]>pivot){ right--; } if(left<=right){ swap(a,left,right); left++; right--; } } return left; } private static void swap(int[] a, int i, int j) { int temp=a[i]; a[i]=a[j]; a[j]=temp; } }I would really appreciate if anyone could give an explanation of where my mistake would be.
最满意答案
问题出在findpivot （在CamelCase中应该是findPivot ）：
while(left <= right)应该
while(left < right)另外，您可以以更好的方式编写quick_select方法：
private static int quick_select(int[] a, int k, int left, int right) { int pivot = findpivot(a,left,right); return pivot == k - 1 ? a[pivot] : k - 1 < pivot ? quick_select(a, k, left, pivot - 1) : quick_select(a, k, pivot + 1, right); }The problem is in findpivot (which should be findPivot in CamelCase) :
while(left <= right)should be
while(left < right)Plus, you can write your quick_selectmethod in a nicer fashion :
private static int quick_select(int[] a, int k, int left, int right) { int pivot = findpivot(a,left,right); return pivot == k - 1 ? a[pivot] : k - 1 < pivot ? quick_select(a, k, left, pivot - 1) : quick_select(a, k, pivot + 1, right); }更多推荐
发布评论