使用Bubble實現雙鏈表列表

Question

我使用以下方法實現Dobly鏈接列表：import java.util.LinkedList;帶有氣泡的對作業進行排序。在對排序和鏈接列表進行研究之後，我瞭解到我不應該使用索引對鏈表進行冒泡排序，因爲鏈接列表中不存在indeces，或者成功實施太麻煩。

所以，讀過之後，我寫了下面的代碼，但是我仍然不確定自己是否在正確的道路上。

我需要一些幫助來理解氣泡排序實現背後的邏輯，並使用一個鏈表。

另外，我需要確保我是否有效地走正確的路，或者如果我在這個編碼練習中嘗試完全錯誤。

//This for loop sorts the smaller part of the bubble sort. 
for(int i = 0; i < cars.size() - 1; i++) 
    {  //This part creates the second "larger" part of the bubble sort. 
     for(int j = i + 1; j < cars.size(); j++) 
     { 


//Did I do this part correctly? This is where the swap and sort of the bubble sort  takes //place. 
//Obviously, I am using the comparable interface, since I am using the compareTo method. 
// 

//with the bubblesort, all elements must be greater than zero because for the bubble   //sort, 0 is the smallest element in a set of integers. 


      if(cars.get(i).getName().compareTo(cars.get(j).getName()) > 0) 
      { 
       CarName cari = cars.get(i); 
       CarName CarNamej = cars.get(j); 
       cars.remove(i); 
       cars.add(i, carj); 
       cars.remove(j); 
       cars.add(j, cari); 
       } 
      } 
     } 
    } 

我使用它來輸出這種方法的主要方法輸出排序結果：

bubbleSort(cars); 

我是正確的，還是我做一些完全錯誤的在我所有的代碼？

Answer 1

它看起來並不像你在正確的道路上。您需要完全消除索引的使用，而是使用節點引用。首先開發代碼，從列表中刪除一個元素，只給出元素的引用。然後開發代碼，在元素已經在列表之前插入一個元素到列表中，只給出這兩個元素的引用。然後，您可以在這兩種方法的基礎上構建排序算法。

例如，這裏有一個如何可能刪除元素：

void remove(Element element) { 
    element.previous().setNext(element.next()); 
    element.next().setPrevious(element.previous()); 
} 

你應該明白一個雙向鏈表是如何工作的，足以看出爲什麼這個代碼應該在列表中間的單元工作。根據您代表列表的方式，您可能需要測試結束條件（element.previous()和/或element.next()爲null）。

Answer 2

想想Bubble Sort在常規數組上的工作方式。一個簡單的冒泡排序實現看起來喜歡這樣的：

for (int i = array.Length; i > 0; i--) 
     { 
      for (int j = 0; j < i-1; j++) 
      { 
       if (array[j] > array[j+1]) 
       { 
        int tmp = array[j]; 
        array[j] = array[j+1]; 
        array[j+1]=tmp; 
       } 
       DisplayElements(array); 
      } 
     }  

不同的是，而不是使用一個臨時的int你就必須引用到下一個和前一個節點在你的名單

Answer 3

存儲在陣列或矢量通過索引訪問存儲的變量，即在項目列表中的位置。

在鏈接列表中，您可以通過從一個項目跳到另一個項目來獲取特定項目。

由於您在代碼中使用get(i)，因此當您按列表中的某個位置編制索引時，您顯然正在使用數組或向量。所以，沒了......可惜你是一個完全錯誤的軌道......

一旦你越來越近，你的代碼看起來更象：

boolean changed = true; 
while (changed) { // keep going until we didn't make any more changes (not 
        // strictly the best condition for bubble sort, but it'll do) 

    a = first;     // grab first element 
    b = a.next;     // grab next element 
    changed = false; 
    while (b!=last) {   // run through all elements 
     if (a.value>b.value) { // compare the two elements; swap if out of order 
      a.prev.next = b; // update element before a to be followed by b 
      b.next.prev = a; // update element after b to be preceeded by a 
      a.prev = b;   // b is now before a 
      b.next = a;   // and a is after b 
      changed = true;  // we made a change, so we're not done 
     } else { 
      a = b;    // if we didn't swap them, move to next pair 
     } 
     b = a.next;    // second half of next pair is next after a 
    } 
} 

這只是給你一個粗略的想法。這絕不是完整的或無缺陷的。例如，如果你在列表的最開始，你需要更新first而不是a.preva.prev.next = b ......但是，嘿...你不想讓別人做你的功課無論如何，對嗎？ ;）

基本上，在一個雙向鏈表中，每個元素知道如何到達下一個元素（a.next）和前一個元素（a.prev）。泡泡排序是排序這種鏈表的好選擇，因爲它只是比較相鄰的元素。否則，快速排序或合併排序或其組合可能會快得多，但它們確實需要對鏈接列表通常不提供的元素進行索引訪問。

希望這會有所幫助。

BTW：Youtube有一大堆很酷的視頻，很好地解釋了各種各樣的東西。

一個更嚴重的一個：http://www.youtube.com/watch?v=P00xJgWzz2c

和更不尋常的：http://www.youtube.com/watch?v=lyZQPjUT5B4（這些都爲快速排序的一個具有更好的音樂:)

Answer 4

你爲什麼不轉換鏈表一個數組，對數組進行排序，然後將內容複製回鏈表。