Yaroslavsky Dual-pivot Quicksort Java implementation

Question

我想问你是否可以告诉我我的代码可能是什么样子的，这样我可能不会在 100000 个整数期间得到 java.lang.StackOverflowError(我的实现很好，但只有 20000 个数字，更大的表格排序会产生该错误(。我已经尝试更改 InteliJ 中的堆大小，但这种方式似乎不起作用。此外，我花了大约 2 个小时试图修改它并通过网络阅读它，但我无法克服这个问题。这就是为什么我要求你们，告诉我在哪里可以更改我的实现中的代码，这样我就不会收到那个错误。

这是代码：

import java.util.ArrayList;
import java.util.Random;
public class YaroslawskiSort {
Random gener;
public int temporary,genertype,NInts;
ArrayList<Integer> mylist;
public YaroslawskiSort(int type,int ilosc){
    gener = new Random();
    mylist= new  ArrayList<>();
    this.genertype=type;
    this.NInts=ilosc;
}
void generate(){
    if(genertype==0){
        for(int i=0;i<NInts;i++){
            mylist.add(gener.nextInt(100000));
        }
    }else {
        for(int i=0;i<NInts;i++){
            mylist.add(NInts-i);
        }
    }
}
void sortingI(int left,int right) {
    for (int i=left+1;i<=right;i++)
    {
        int value = mylist.get(i);
        int j =i-1;
        while (j >= left && mylist.get(j)>value)
        {
            mylist.set(j+1,mylist.get(j));
            j--;
        }
        mylist.set(j+1,value);
    }
}
private void sorting( int left, int right) {
    if((right-left)>=17) {
        int[] index=new int[2];
        index = partition(left, right);
        if (left < index[0]) {
            sorting(left, index[0]);
        }
        if(index[0]<index[1]){
            sorting(index[0], index[1]);
        }
        if (index[1] < right) {
           sorting(index[1], right);
        }

    }
    if((right-left)<17 && (right-left)!=0){
    sortingI(left,right);                               //INSERTION SORT!
    }
}
private int[] partition( int left, int right) {
    int pivot1 = mylist.get(left);
    int pivot2 = mylist.get(right);
    if(pivot1>pivot2){
       mylist.set(left,pivot2);
        mylist.set(right,pivot1);
        temporary=pivot1;
        pivot1=pivot2;
        pivot2=temporary;
    }
    int L=left+1;
    while(mylist.get(L)<pivot1 && L<right){
        L++;
    }
    int K=L;
    while( K<=right&& mylist.get(K)>=pivot1 && mylist.get(K)<=pivot2 ){
        K++;
    }
    int G=right-1;
    while(mylist.get(G)>pivot2 && G>left){
        G--;
    }

    while (K <= G) {
        if(mylist.get(K)<pivot1){
            mylist.add(left+1,mylist.remove(K));
            L++;
            K++;
        }
        if(mylist.get(K)>=pivot1 && mylist.get(K)<=pivot2){
            mylist.add(L,mylist.remove(K));
            K++;
        }
        if(mylist.get(K)>pivot2){
            mylist.add(right,mylist.remove(K));
            G--;
        }
    }
    mylist.set(left,mylist.get(L-1));
    mylist.set(L-1,pivot1);
    mylist.set(right,mylist.get(G+1));
    mylist.set(G+1,pivot2);
    int[] table=new int[2];
    table[0]=L;
    table[1]=G;
    return table;
}
void printing(){
    for(int k=0;k<NInts;k++){
        System.out.print(" "+mylist.get(k));
    }
}
public static void main(String[] args){
            YaroslawskiSort instance = new YaroslawskiSort(1,100000);
            instance.generate();
            instance.sorting(0, instance.mylist.size() - 1);
            instance.printing();
    }
}

感谢您对:)的帮助

Answer 1

您的代码运行良好，要增加堆栈大小，请打开编辑配置...在 Intellij IDEA(右上角(和现场虚拟机选项中键入 -Xss16m 的项目。如果这样做，您将不会收到StackOverflowError。

在我看来，你会得到 StackOverflow，因为你正在递归调用排序方法，它反过来调用分区方法，其中总是创建一个新的 int[2]，并且所有这些数组都在堆栈上。

如果您可以重写分区方法，使其(例如(返回 int 并分别调用它以进行左绑定和右绑定，我认为这将解决问题。