我如何在 algoritimo quicksort 中解决这个错误
how i could fix this wrong in algoritimo quicksort
好吧,我一直在做一个需要对单词进行排序的程序,一个数组 String。我正在使用算法快速排序,当我第一次排序时它工作得很好。但是当我尝试对已经订购的 self 数组进行排序时,它会抛出错误 java.lang.WhosebugError.
这是算法。
protected String[] ordenar(String[] array) {
return executeQuickSort(array, 0, array.length - 1);
}
private String[] executeQuickSort(String[] array, int inicio, int fim){
if(inicio < fim)
{
int posicaoPivo = partition(array, inicio, fim);
if (posicaoPivo == fim) {
posicaoPivo--;
}
executeQuickSort(array, inicio, posicaoPivo);
executeQuickSort(array, posicaoPivo + 1, fim);
}
return array;
}
private int partition(String[] array, int inicio, int fim) {
String pivo = array[inicio];
int i = inicio - 1 ;
int j = fim + 1 ;
while (true)
{
i++;
while ( i < fim && array[i].compareTo(pivo) < 0)
i++;
j--;
while (j > inicio && array[j].compareTo(pivo) > 0)
j--;
if (i < j)
swap(array, i, j);
else
return j;
}
}
private void swap(String[] array, int i, int j) {
String temp = array[i];
array[i] = array[j];
array[j] = temp;
}
我发现类似 mv java 的东西正在使用大内存,然后抛出错误。有人说我需要增加这个过程的内存,但我在代码行中还有其他选择吗?如果我进行此更改,它会在我 运行 这个程序所在的所有电脑上运行吗?
您的分区方法需要改进。您可以使用 while(pointL < pointR) 而不是 while(true),它将减少问题 space。如果您需要了解快速排序,请参阅此 example .
private int partition(int left,int right,String[] array){
int pointL = left-1;
int pointR = right;
String[] a = array;
// normally pivot is selected as middle elements..
// if pivot is median of array performance going to high
String pivot = a[left+(left+right)/2];
while(pointL < pointR){
while(a[++pointL].compareTo(pivot) < 0);
while(pointR> 0 && a[--pointR].compareTo(pivot) > 0);
if(pointL >= pointR){
break;
}else{
a = swap(pointL, pointR, a);
}
}
a = swap(pointL, right, a);
return pointL;
}
public String[] swap(int pointL, int pointR, String[] a){
String tmp = a[pointL];
a[pointL] = a[pointR];
a[pointR] = tmp;
return a;
}
你的分区看起来很奇怪,试试这个
private int partition(String[] array, int inicio, int fim) {
String pivo = array[(inicio + fim) / 2];
int i = inicio;
int j = fim;
while (true) {
while (array[i].compareTo(pivo) < 0) {
i++;
}
while (array[j].compareTo(pivo) > 0) {
j--;
}
if (i < j) {
swap(array, i, j);
i++;
j--;
} else {
return i;
}
}
}
好吧,我一直在做一个需要对单词进行排序的程序,一个数组 String。我正在使用算法快速排序,当我第一次排序时它工作得很好。但是当我尝试对已经订购的 self 数组进行排序时,它会抛出错误 java.lang.WhosebugError.
这是算法。
protected String[] ordenar(String[] array) {
return executeQuickSort(array, 0, array.length - 1);
}
private String[] executeQuickSort(String[] array, int inicio, int fim){
if(inicio < fim)
{
int posicaoPivo = partition(array, inicio, fim);
if (posicaoPivo == fim) {
posicaoPivo--;
}
executeQuickSort(array, inicio, posicaoPivo);
executeQuickSort(array, posicaoPivo + 1, fim);
}
return array;
}
private int partition(String[] array, int inicio, int fim) {
String pivo = array[inicio];
int i = inicio - 1 ;
int j = fim + 1 ;
while (true)
{
i++;
while ( i < fim && array[i].compareTo(pivo) < 0)
i++;
j--;
while (j > inicio && array[j].compareTo(pivo) > 0)
j--;
if (i < j)
swap(array, i, j);
else
return j;
}
}
private void swap(String[] array, int i, int j) {
String temp = array[i];
array[i] = array[j];
array[j] = temp;
}
我发现类似 mv java 的东西正在使用大内存,然后抛出错误。有人说我需要增加这个过程的内存,但我在代码行中还有其他选择吗?如果我进行此更改,它会在我 运行 这个程序所在的所有电脑上运行吗?
您的分区方法需要改进。您可以使用 while(pointL < pointR) 而不是 while(true),它将减少问题 space。如果您需要了解快速排序,请参阅此 example .
private int partition(int left,int right,String[] array){
int pointL = left-1;
int pointR = right;
String[] a = array;
// normally pivot is selected as middle elements..
// if pivot is median of array performance going to high
String pivot = a[left+(left+right)/2];
while(pointL < pointR){
while(a[++pointL].compareTo(pivot) < 0);
while(pointR> 0 && a[--pointR].compareTo(pivot) > 0);
if(pointL >= pointR){
break;
}else{
a = swap(pointL, pointR, a);
}
}
a = swap(pointL, right, a);
return pointL;
}
public String[] swap(int pointL, int pointR, String[] a){
String tmp = a[pointL];
a[pointL] = a[pointR];
a[pointR] = tmp;
return a;
}
你的分区看起来很奇怪,试试这个
private int partition(String[] array, int inicio, int fim) {
String pivo = array[(inicio + fim) / 2];
int i = inicio;
int j = fim;
while (true) {
while (array[i].compareTo(pivo) < 0) {
i++;
}
while (array[j].compareTo(pivo) > 0) {
j--;
}
if (i < j) {
swap(array, i, j);
i++;
j--;
} else {
return i;
}
}
}