为快速排序算法获取错误的输出

Question

我想实现快速排序并且输出不正确。我知道ArrayList被引用的价值，但我不明白为什么它没有给我正确的输出。谁能告诉我我做错了什么？

import java.util.ArrayList; 

public class Quicksort { 

static ArrayList<Integer> quicksort(ArrayList<Integer> place){ 
    if(place.size()<=1) 
     return place; 
    int median=place.size()/2; 

    int pivot=place.get(median); 
    place.remove(median); 

    ArrayList<Integer> place2=new ArrayList<>(); 
    ArrayList<Integer> place3=new ArrayList<>(); 

    for(int i=0;i<place.size();i++){ 
     if(place.get(i)<pivot){ 
      place2.add(place.get(i)); 
     }else if(place.get(i)>pivot){ 
      place3.add(place.get(i)); 
     }else if(place.get(i)==pivot){ 
      place3.add(place.get(i)); 
     } 
    } 
    return concatenate(quicksort(place2),pivot,quicksort(place3)); 
} 

static ArrayList<Integer> concatenate(ArrayList<Integer> first, int pivot, ArrayList<Integer> second){ 
    ArrayList<Integer> third=new ArrayList<>(); 

    for(int i=0;i<first.size();i++){ 
     third.add(first.get(i)); 
    } 

    third.add(pivot); 
    for(int i=0;i<second.size();i++){ 
     third.add(second.get(i)); 
    } 

    return third; 
} 

public static void main(String[] args) { 

ArrayList<Integer> arraylist=new ArrayList<>(); 

arraylist.add(20); 
arraylist.add(3); 
arraylist.add(8); 
arraylist.add(4); 
arraylist.add(7); 
arraylist.add(1); 
arraylist.add(9); 
arraylist.add(13); 

    quicksort(arraylist); 
    for(int n:arraylist){ 
     System.out.println(n); 
    } 
} 
} 

Answer 1

您的quicksort方法返回排序后的数组，但您不分配它。更改为

arraylist = quicksort(arraylist); 

它工作得很好。

---

这是事实，你可以修改你的快速排序法的ArrayList中，所以就没有必要为它分配，但是这不是你在做什么。你所要做的就是删除数据透视表，然后返回由concatenate创建的新列表。这就是为什么在你的算法中，你会得到缺少7的原始列表。

如果你不想再次分配列表中，你需要做的是这样的：

private static void quicksort(List<Integer> place) { 
    if (place.size() <= 1) 
     return; 

    int median=place.size()/2; 
    int pivot=place.get(median); 
    place.remove(median); 

    List<Integer> place2 = new ArrayList<>(); 
    List<Integer> place3 = new ArrayList<>(); 

    Iterator<Integer> it = place.iterator(); 
    while (it.hasNext()) { 
     int i = it.next(); 
     if (i < pivot) { 
      place2.add(i); 
     } else { 
      place3.add(i); 
     } 
     it.remove(); 
    } 

    quicksort(place2); 
    quicksort(place3); 

    for (Integer i : place2) { 
     place.add(i); 
    } 
    place.add(pivot); 
    for (Integer i : place3) { 
     place.add(i); 
    } 
}