使用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

你为什么不转换链表一个数组，对数组进行排序，然后将内容复制回链表。