Quicksort:wikipedia-implementation 不工作
Quicksort: wikipedia-implementation not working out
我刚刚尝试实现来自维基百科 (https://en.wikipedia.org/wiki/Quicksort) 的快速排序算法,但缺少一些东西。这是我的代码:
public static void quicksort(int[] a, int lo, int hi) {
if(lo < hi) {
int p = partition(a, lo, hi);
quicksort(a, lo, p - 1);
quicksort(a, p + 1, hi);
}
}
public static int partition(int[] a, int lo, int hi) {
//choose pivot element
int pivotIndex = 0;
int pivotVal = a[pivotIndex];
//put pivot at the end of array
swap(a, pivotIndex, hi);
//compare other elements to pivot and swap accordingly
int storeindex = lo;
for(int i = lo; i < hi; i++) {
if(a[i] <= pivotVal) {
swap(a, i, storeindex);
storeindex++;
}
//set pivot in right place of array
swap(a, storeindex, hi);
}
return storeindex; //return
}
public static void swap(int[] a, int place1, int place2) {
int temp = a[place1];
a[place1] = a[place2];
a[place2] = temp;
}
这是一个错误的例子:
int[] a = {1,2,3,4,5};
quicksort(a, 0, a.length - 1);
returns: 1, 2, 3, 5, 4
而不是它应该:
1, 2, 3, 4, 5
我已经盯着这个看了很长一段时间,如果有人能帮我找出我哪里出错了,我将不胜感激:)谢谢!
两个问题:
您需要从分区中选择枢轴值,而不仅仅是取数组的第一个元素
最后一次交换应该在循环之外,您是在遍历分区后将枢轴元素放到它所在的位置。请参阅最后两行:
固定分区方式:
public static int partition(int[] a, int lo, int hi) {
//choose pivot element
int pivotIndex = lo; // ERROR 1 fixed
int pivotVal = a[pivotIndex];
//put pivot at the end of array
swap(a, pivotIndex, hi);
//compare other elements to pivot and swap accordingly
int storeindex = lo;
for (int i = lo; i < hi; i++) {
if (a[i] <= pivotVal) {
swap(a, i, storeindex);
storeindex++;
}
}
//set pivot in right place of array
swap(a, storeindex, hi); // ERROR 2 fixed
return storeindex; //return
}
我刚刚尝试实现来自维基百科 (https://en.wikipedia.org/wiki/Quicksort) 的快速排序算法,但缺少一些东西。这是我的代码:
public static void quicksort(int[] a, int lo, int hi) {
if(lo < hi) {
int p = partition(a, lo, hi);
quicksort(a, lo, p - 1);
quicksort(a, p + 1, hi);
}
}
public static int partition(int[] a, int lo, int hi) {
//choose pivot element
int pivotIndex = 0;
int pivotVal = a[pivotIndex];
//put pivot at the end of array
swap(a, pivotIndex, hi);
//compare other elements to pivot and swap accordingly
int storeindex = lo;
for(int i = lo; i < hi; i++) {
if(a[i] <= pivotVal) {
swap(a, i, storeindex);
storeindex++;
}
//set pivot in right place of array
swap(a, storeindex, hi);
}
return storeindex; //return
}
public static void swap(int[] a, int place1, int place2) {
int temp = a[place1];
a[place1] = a[place2];
a[place2] = temp;
}
这是一个错误的例子:
int[] a = {1,2,3,4,5};
quicksort(a, 0, a.length - 1);
returns: 1, 2, 3, 5, 4
而不是它应该:
1, 2, 3, 4, 5
我已经盯着这个看了很长一段时间,如果有人能帮我找出我哪里出错了,我将不胜感激:)谢谢!
两个问题:
您需要从分区中选择枢轴值,而不仅仅是取数组的第一个元素
最后一次交换应该在循环之外,您是在遍历分区后将枢轴元素放到它所在的位置。请参阅最后两行:
固定分区方式:
public static int partition(int[] a, int lo, int hi) {
//choose pivot element
int pivotIndex = lo; // ERROR 1 fixed
int pivotVal = a[pivotIndex];
//put pivot at the end of array
swap(a, pivotIndex, hi);
//compare other elements to pivot and swap accordingly
int storeindex = lo;
for (int i = lo; i < hi; i++) {
if (a[i] <= pivotVal) {
swap(a, i, storeindex);
storeindex++;
}
}
//set pivot in right place of array
swap(a, storeindex, hi); // ERROR 2 fixed
return storeindex; //return
}