Quicksort java arraylist實現

Question

我在Java中遇到了一個非常簡單的問題。我已經在java中實現了快速排序，可以處理arraylist，並且可以帶來任何價值。問題是它只適用於低於8000的大小的數組列表。 任何人都可以告訴我我的程序有什麼問題嗎？我認爲它可能與遞歸深度限制有關，但我不確定（因爲它有時適用於較大的尺寸，有時不適用）。我怎樣才能改進我的快速排序實現，以便它能像100000這樣的更大規模的Arraylist工作？

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

可能有很多原因，你的代碼不能用於大量投入運行。大多數情況下，這可能是因爲爲應用程序指定的堆大小容量溢出了。這可以通過增加應用程序的堆大小來解決（請查看stackoverflow link關於如何增加應用程序的堆大小）