快速排序 java arraylist 实现

Question

我正在努力解决 java 中的一个非常简单的问题。我在 java 中实现了快速排序，它适用于数组列表并且可以取任何值。问题是它只适用于大小小于 8000 的数组列表。谁能告诉我我的程序有什么问题？我认为它可能与递归深度限制有关，但我不确定（因为有时它适用于更大的尺寸，有时则不然）。我怎样才能改进我的快速排序实现，以便它适用于更大尺寸的 Arraylist，如 100000？

import java.util.ArrayList;
import java.util.Random;


public class QuickSort {
Random gener;
int temporary,genertype,NInts,flag;
ArrayList<Integer> mylist;

public QuickSort(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);
        }
    }
}

int count1(ArrayList<Integer> list,int counter1,int counter2){
    while(list.get(0)<list.get(counter1)){

        if(counter1==counter2){
            flag=1;
            return counter1;
        }
        counter1++;
    }
    flag=0;
    return counter1;
}
int count2(ArrayList<Integer> list,int counter1,int counter2){
    while(list.get(0)>list.get(counter2)){
        if(counter1==counter2){
            flag=1;
            return counter2;
        }
        counter2--;
    }
    flag=0;
    return counter2;
}


public ArrayList<Integer> sorting(ArrayList<Integer> list) {
    ArrayList<Integer> left = new ArrayList<Integer>();
    ArrayList<Integer> right = new ArrayList<Integer>();
    int counter1,counter2;

    if (list.size() == 1) {
        return list;
    }else {
        counter1=1;
        counter2=list.size()-1;

        while(counter1!=counter2) {

            counter1=count1(list,counter1,counter2);
            if(flag==1)
                break;
            counter2=count2(list,counter1,counter2);
            if(flag==1)
                break;

            temporary = list.get(counter1);
            list.set(counter1, list.get(counter2));
            list.set(counter2, temporary);
        }

        for (int i = 0; i < counter1; i++) {
            left.add(list.get(i));
        }

        for (int i = counter1; i < list.size(); i++) {
            right.add(list.get(i));
        }

        left = sorting(left);
        right = sorting(right);
        list=merge(left, right);
    }
    return list;
}

ArrayList<Integer> merge(ArrayList<Integer> left, ArrayList<Integer> right) {

    if(left.get(0)>right.get(right.size()-1)){
    right.addAll(left);
        return right;
    }
    else{
        left.addAll(right);
        return left;
    }

}

void printing(){
    for(int k=0;k<NInts;k++){
        System.out.print(" "+mylist.get(k));
    }
}

public static void main(String[] args){

    QuickSort instance = new QuickSort(1,1000);
    instance.generate();
    instance.mylist=instance.sorting(instance.mylist);
    instance.printing();
    }
}

Ps.If 如果您发现我的代码有任何问题，请告诉我，以便我改进它:)

Answer 1

您的代码无法运行大量输入的原因可能有很多。主要是因为为您的应用程序指定的堆大小容量溢出。这可以通过增加应用程序的堆大小来解决（查看此 Whosebug link，了解如何增加应用程序的堆大小）

快速排序 java arraylist 实现

Quicksort java arraylist implementation

java

arraylist

quicksort