Java String Quicksort零星地工作？

Question

我正在完成一個我在這裏看到的任務，但是在我審查了他們之後，我仍然無法看到我做錯了什麼。我的代碼快速排列字符串數組似乎工作 - 大部分時間。但是，如果我運行了很多次，它有時會輸出錯誤的結果。任何意見，我應該看看解決這個問題將不勝感激。

import java.util.Random; 
public class QuickSortStrings { 

    static String[] strings; 

    public static void main(String[] args) { 

     strings = new String[args.length]; 

     for (int i = 0; i < args.length; i++) { 
      strings[i] = args[i]; 
     } 

     qsort(0, strings.length-1); 

     System.out.print("The array, quicksorted: "); 
     for (int i = 0; i < strings.length; i++) 
     { 
      System.out.print(strings[i] + " "); 
     } 
     System.out.println("\n"); 
    } 

    static void qsort(int low, int high) { 
     int i = low, j = high; 

     // Get the pivot element 
     Random r = new Random(); 
     int pivot = r.nextInt(high-low+1)+low; 

     // Divide into two lists 
     while (i <= j) { 

      while (strings[i].compareTo(strings[pivot]) < 0) i++; 

      while (strings[j].compareTo(strings[pivot]) > 0) j--; 

      if (i <= j) { 
      exchange(i, j); 
      i++; 
      j--; 
      } 
     } 

     // Recursion 
     if (low < j) qsort(low, j); 
     if (i < high) qsort(i, high); 
     } 

    static void exchange(int i, int j) { 
     String temp = strings[i]; 
     strings[i] = strings[j]; 
     strings[j] = temp; 
    } 
} 

Answer 1

不是一個解決方案，而是一個提示。 如果我有這樣一個不確定性的行爲，我想：

1. 添加函數返回一個布爾檢查，如果排序的數組
2. 在每次迭代調用它，只有當它失敗（您斑點一個輸入數據數組，它不起作用），則打印或序列化有罪數據。
3. 現在，以這些數據作爲輸入啓動調試器，並希望追蹤錯誤。

Answer 2

這種排序的每次迭代都假設減少可排序的範圍。基本上，這是一個分而治之的算法。

的pivot找到您所指定

問題是，你將隨機化的pivot範圍的「中」點，所以每次經過排序運行時，它比較一些隨機的部分，大概包括一些部分，您已經整理...

因此，而不是使用...

int pivot = r.nextInt(high-low+1)+low; 

您應該使用...

int pivot = low + (high - low)/2; 

例如...

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

public class QuickSort { 

    static String[] strings; 

    public static void main(String[] args) { 

     List<String> values = new ArrayList<>(26); 
     for (int index = 0; index < 26; index++) { 
      values.add(new String(new char[]{(char)(65 + index)})); 
     } 
     Collections.shuffle(values); 

     strings = values.toArray(new String[values.size()]); 
     System.out.println("Before"); 
     for (int i = 0; i < strings.length; i++) { 
      System.out.print(strings[i] + " "); 
     } 
     System.out.println(""); 

     qsort(0, strings.length - 1); 

     System.out.println("The array, quicksorted: "); 
     for (int i = 0; i < strings.length; i++) { 
      System.out.print(strings[i] + " "); 
     } 
     System.out.println("\n"); 
    } 

    static void qsort(int low, int high) { 
     int i = low, j = high; 

     // Get the pivot element 
     int pivot = low + (high - low)/2; 
     String value = strings[pivot]; 

     // Divide into two lists 
     while (i <= j) { 

      while (strings[i].compareTo(value) < 0) { 
       i++; 
      } 

      while (strings[j].compareTo(value) > 0) { 
       j--; 
      } 

      if (i <= j) { 
       exchange(i, j); 
       i++; 
       j--; 
      } 
     } 

     // Recursion 
     if (low < j) { 
      qsort(low, j); 
     } 
     if (i < high) { 
      qsort(i, high); 
     } 
    } 

    static void exchange(int i, int j) { 
     String temp = strings[i]; 
     strings[i] = strings[j]; 
     strings[j] = temp; 
    } 

} 

將會產生...

Before 
N S B A F Z X J Q K V C L R W E H Y M U G I D P T O 
The array, quicksorted: 
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 

Before 
G U P Q D A W T R M E O X J S C I V Y F H L B N Z K 
The array, quicksorted: 
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 

Before 
D Z C B Q O K W X F V G R S A U P T H Y I E N L M J 
The array, quicksorted: 
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 

Before 
Q K H B W N J V C Y U O R P G I F D Z E L S A X M T 
The array, quicksorted: 
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 

Before 
R V P G E S C A H W X I T D Z B K Q F M U Y L J N O 
The array, quicksorted: 
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 

Before 
L O T E U D H N P J V I Q C X S Z W A R F K G Y B M 
The array, quicksorted: 
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 

Before 
I E J F U X P K R Q L S C O Y W G A Z B V M D H N T 
The array, quicksorted: 
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 

Before 
X L K T W E V J N Y G H O Q I M C P A R B F S U Z D 
The array, quicksorted: 
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 

Before 
U X N T K Q S V P F W C G Y O L A B E H J R D M Z I 
The array, quicksorted: 
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 

Before 
A J Z C M Y O Q F L K D P S X W N T I B H E R U V G 
The array, quicksorted: 
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 

NB-不要使用List的壓力，我只是產生了一些隨機String S;）