快速排序算法不在Java中排序

Question

我編寫了一個快速排序算法，我從this網站獲得。

我跟着第一個算法，這是我的代碼是什麼樣子：

private static ArrayList<Integer> copy; 

public static ArrayList<Integer> concatenate(ArrayList<Integer> a, ArrayList<Integer> b, ArrayList<Integer> c) { 
    ArrayList<Integer> result = new ArrayList<Integer>(); 
    for(int i = 0; i < a.size(); i++) 
     result.add(a.get(i)); 
    for(int i = 0; i < b.size(); i++) 
     result.add(b.get(i)); 
    for(int i = 0; i < c.size(); i++) 
     result.add(c.get(i)); 
    return result; 
} 

public static void quickSort(ArrayList<Integer> a) { 
    ArrayList<Integer> less = new ArrayList<Integer>(); 
    ArrayList<Integer> greater = new ArrayList<Integer>(); 
    ArrayList<Integer> equal = new ArrayList<Integer>(); 
    Random rand = new Random(); 
    if(a.size() > 1) { 
     int pivot = a.get(rand.nextInt(a.size()-1)); 
     for(int i = 0; i < a.size(); i++) { 
      if(a.get(i) < pivot) 
       less.add(a.get(i)); 
      if(a.get(i) == pivot) 
       equal.add(a.get(i)); 
      if(a.get(i) > pivot) 
       greater.add(a.get(i)); 
     } 
     quickSort(less); 
     quickSort(greater); 
     a = concatenate(less, equal, greater); 
    } 
    copy = a; 
} 

出於某種原因，當我打印在主拷貝我得到了看起來像這樣：

Before: 2, 5, 9, 3, 3, 2, 0, 8, 1, 5 
After : 0, 1, 2, 5, 9, 3, 3, 2, 8, 5 

有我的代碼或算法的問題？

Answer 1

查看您提供的鏈接中的Java示例，您的代碼和示例之間有一些不同之處。

你的函數不返回列表，它返回void，試着讓函數返回一個列表，然後把這個返回分配給越來越少，而不是隻調用「quickSort（less）」或者「quickSort（more ）」。例如。在例如：

// Recursively sort sublists 
    less = quickSort(less); 
    more = quickSort(more); 

也許你只是調用sort一次，所以只有在排序列表中的一個組成部分，它肯定是從你的輸出顯得那麼無妨。確保每次都返回列表，而不是僅僅遞歸地對每個列表進行排序，然後不要將它鏈接到之前調用的列表。在完成quickSort的所有遞歸調用之後，它將返回到第一個調用的最後一行，並簡單地覆蓋a的值，並且連接更少，等於和更大的連接，忽略迭代中完成的所有工作，因此您只需要第一類的結果。

Answer 2

在quickSort函數的最後一行中，會覆蓋將在每次遞歸調用中執行的copy列表，因此會丟失所有更改。

copy = a; 

正如dahui所說，嘗試製作一個quickSort函數來返回排序列表。你可以在你的IDE中複製和粘貼這段代碼，希望它能工作:)（我抽出Random var以防止在每次遞歸調用中創建它）。

import java.util.Random; 
import java.util.List; 
import java.util.Arrays; 
import java.util.ArrayList; 

public class Quicksort { 

    // For selecting random pivot 
    private static Random rand = new Random(); 

    public static ArrayList<Integer> concatenate(ArrayList<Integer> a, ArrayList<Integer> b, ArrayList<Integer> c) { 
     ArrayList<Integer> result = new ArrayList<Integer>(); 
     for(int i = 0; i < a.size(); i++) 
      result.add(a.get(i)); 
     for(int i = 0; i < b.size(); i++) 
      result.add(b.get(i)); 
     for(int i = 0; i < c.size(); i++) 
      result.add(c.get(i)); 
     return result; 
    } 


    public static ArrayList<Integer> quickSort(ArrayList<Integer> a) { 
     ArrayList<Integer> less = new ArrayList<Integer>(); 
     ArrayList<Integer> greater = new ArrayList<Integer>(); 
     ArrayList<Integer> equal = new ArrayList<Integer>(); 

     if(a.size() > 1) { 
      int pivot = a.get(rand.nextInt(a.size()-1)); 

      for(int i = 0; i < a.size(); i++) { 
       if(a.get(i) < pivot) 
        less.add(a.get(i)); 
       if(a.get(i) == pivot) 
        equal.add(a.get(i)); 
       if(a.get(i) > pivot) 
        greater.add(a.get(i)); 
      } 
      less = quickSort(less); 
      greater = quickSort(greater); 
      a = concatenate(less, equal, greater); 
     } 

     return a; 
    } 

    public static void main(String args[]) { 
     System.out.println("*** Starting Quicksort ***\n"); 

     ArrayList<Integer> numbers = new ArrayList<Integer>(Arrays.asList(new Integer[]{2, 5, 9, 3, 3, 2, 0, 8, 1, 5})); 
     System.out.println("Unsorted:\t" + numbers); 
     System.out.println("Sorted: \t" + quickSort(numbers)); 


     System.out.println("\n*** Sorting finalized. Have a good day!"); 
    } 

}