基本泡泡排序與Java ArrayList

Question

我正在實施比較，它不工作，所以我想我會寫一個基本的氣泡排序。

int[] numbers = { 5, 8, 14, 1, 5678 }; 
int tempVar; 
for (int i = 0; i < numbers.length; i++) 
{ 
    for(int j = 0; j < numbers.length; j++) 
    { 
      if(numbers[i] > numbers[j + 1]) 
      { 
        tempVar = numbers [j + 1]; 
        numbers [j + 1]= numbers [i]; 
        numbers [i] = tempVar; 
      } 
    } 
} 
for (int i = 0; i < numbers.length; i++) 
{ 
    System.out.println(numbers[i].toString()); 
} 

本教程是否正確？ https://blog.udemy.com/bubble-sort-java/

我跟着這個例子，並將它應用到arraylist中的Last Names，但結果有點怪異。

String a; 
String b; 
Person c; 
Person d; 

for (int i=0; i< list.size(); i++){ 

    for(int j=0; j< list.size()-1; j++){ 

     a = list.get(i).getLastName(); 
     b = list.get(j+1).getLastName(); 
     c = list.get(i); 
     d = list.get(j+1); 

     if (a.compareTo(b) < 0) { 

      Person temp = d; 
      list.set(j+1, c);   
      list.set(i, temp); 
     } 
    } 
} 

我真的很想得到一些方法握（像弄清楚爲什麼我比較沒有工作），但現在我只是想獲得一個冒泡排序才能正常工作。謝謝。

Answer 1

感謝大家的指點我朝着正確的方向發展。 一個問題是我忘了.trim（），所以compareTo不工作，也沒有與charAt（0）進行比較。

此外，我發現更好地實現了Bubble-Sort循環。

這是現在工作：

String a; 
    String b; 
    Person c; 
    Person d; 

    for (int i= 0; i< list.size() ; i++){ 

     for(int j=0; j< list.size() - i-1; j++){ 

      a = list.get(j).getLastName().toUpperCase().trim(); 
      b = list.get(j+1).getLastName().toUpperCase().trim(); 

      c = list.get(j); 
      d = list.get(j+1); 

      if (a.compareTo(b) > 0) { 

       Person temp = d; 
       list.set(j+1, c); 
       list.set(j, temp); 

      } 
     } 

Answer 2

這是一個奇怪而低效的實現，你將每個數字相互比較。像這樣的東西更直觀（可以提高一點性能，但這不是重點，你只需要節省大量時間而不會意外地在索引上犯錯，如果你真的關心性能而不是可讀性的使用歸併或快速排序爲Java並[Java的使用快速排序的基本類型和歸併爲對象，可能是因爲對原始類型並不重要，如果該算法是穩定與否）：

public void bubbleSort(int[] arr) { 
    boolean change; 
    do { 
     change = false; 
     for (int i = 0; i < arr.length - 1; i++) { 
      if (arr[i] > arr[i + 1]) { 
       int temp = arr[i]; 
       arr[i] = arr[i + 1]; 
       arr[i + 1] = temp; 
       change = true; 
      } 
     } 
    } while (change); 
} 

應用到你的代碼（升序排序）：

boolean change; 
do { 
    change = false; 
    for (int i = 0; i < list.size() - 1; i++) { 
     c = list.get(i); 
     d = list.get(i + 1); 
     a = c.getLastName(); 
     b = d.getLastName(); 
     // add special comparison for null values if a or b can be null ("" is ok) 
     // toLowerCase() is to compare case-insensitive ('a' != 'A') 
     if (a.toLowerCase().compareTo(b.toLowerCase()) > 0) { 
      list.set(i, d);   
      list.set(i + 1, c); 
      change = true; 
     } 
    } 
} while (change); 

旁註：s.toUpperCase().compareTo(s.toLowerCase()) == 0是true如果s只包含符號。

Answer 3

如果你寫，

for(int j = 0; j < numbers.length; j++) 

然後，你會得到ArrayIndexOutOfBoundsException以下行，

tempVar = numbers [j + 1]; 

因爲，陣列numbers具有長度5與去年指數4（如指數從開始0）。所以，當j = 4，環路破壞條件j < numbers.length或4 < 5是true，但你會得到異常訪問numbers [4 + 1]索引。

所以儘量

for(int j = 0; j < numbers.length -1; j++) 

或

for(int j = i; j < numbers.length -1; j++) // more efficient 

現在對於你的代碼的第二個片段，你能告訴我究竟是什麼問題你？

從百搭猜測，你的a.compareTo(b) < 0是不是像你想要的那樣工作。

請注意，如果字符串a是lexicographically小於字符串b，則compareTo返回的值小於0。

我很困惑你想要什麼，因此產生下面的代碼可以幫助你克服你的問題：

import java.util.ArrayList; 

public class Sort{ 
    private static ArrayList<String> list = new ArrayList<String>(); 

    public static ArrayList<String> sortByName(String [] input) { 
     String temp; 
     for (int i=0; i< input.length; i++){ 
      for(int j= i; j< input.length-1; j++){ 
       char first = input[i].charAt(0); 
       char sec = input[j +1].charAt(0); 
       if (first < sec) { 
        temp = input[j +1]; 
        input[j +1] = input[i];   
        input[i] = temp; 
       } 
      } 
      list.add(input[i]); 
     } 

     return list; 
    } 

    public static void main(String[] args) { 
     String string[] = {"Ezen", "Allen" , "Wilker", "Kruden", "Crocket"}; 
     bubbleSortByName(string); 
    } 
} 

輸出是list包含：

名單= [威爾克，Kruden，Ezen，Crocket，Allen]

Answer 4

在Bubble排序中，您只需比較相鄰元素並將它們交換（取決於cond銀行足球比賽）。

如果您按升序排列，則比較相鄰元素並調換if(arr[j]>arr[j+1])。 這會在第一次迭代中將最大的元素移動到最後。因此，外循環中有n-1次迭代可對數組進行排序，其中n是數組的長度。

首先閱讀本Bubble sort正如你所提到的教程是完全錯誤的

更正代碼

for (int i = 0; i < numbers.length-1; i++) 
{ 
    for(int j = 0; j < numbers.length-i-1; j++) 
    { 
      if(numbers[j] > numbers[j + 1]) 
      { 
        tempVar = numbers [j + 1]; 
        numbers [j + 1]= numbers [j]; 
        numbers [j] = tempVar; 
      } 
    } 
} 

這裏是working link

Answer 5

有一個小問題，您原來使用的排序程序。

int j=0 

應該

int j=i 

你也並沒有完全取代它的字符串排序。

a.compareTo(b) < 0 

應該

a.compareTo(b) > 0 

檢查：

import java.util.*; 

public class HelloWorld{ 
public static void main(String[] args){ 

    ArrayList<Person> list = new ArrayList<Person>(); 
    list.add(new Person("xyz")); 
    list.add(new Person("abc")); 
    list.add(new Person("pqr")); 
    list.add(new Person("lmn")); 

    String a; 
    String b; 
    Person c; 
    Person d; 
    for (int i=0; i< list.size(); i++){ 
     for(int j=i; j< list.size()-1; j++){ 
     a = list.get(i).getLastName(); 
     b = list.get(j+1).getLastName(); 
     c = list.get(i); 
     d = list.get(j+1); 

     if (a.compareTo(b) > 0) { 

      Person temp = d; 
      list.set(j+1, c);   
      list.set(i, temp); 
     } 
    } 
    } 
    for(Person person: list){ 
     System.out.println(person.lastName); 
    } 
} 
} 
class Person{ 

    String lastName; 
    Person(String str){ 
     lastName = str; 
    } 
    public String getLastName(){ 
     return lastName; 
    } 
}