java - 使用冒泡排序实现双向链表

Question

我正在使用以下实现一个 Dobly 链接列表： import java.util.LinkedList; 使用冒泡排序进行作业。在研究了排序和链表之后，我了解到我不应该使用索引对链表进行冒泡排序，因为链表中不存在索引，否则执行成功太麻烦。

因此，读完之后，我编写了以下代码，但我仍然不确定我是否走在正确的道路上。

我需要一些帮助来理解带有 dobly 链表​​的冒泡排序实现背后的逻辑。

此外，我需要确信我是否正在有效地走在正确的道路上，或者我在尝试这个编码练习时是否完全错误。

 //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);
                }
            }
        }
    }

我用这个在main方法中输出这个方法来输出排序后的结果：

bubbleSort(cars);

我是正确的，还是我在所有代码中都做错了什么？

Answer 1

在数组或向量中，您可以通过索引访问存储的变量，即在项目列表中的位置。

在链接列表中，您可以通过从一个项目跳到下一个项目来访问特定项目。

由于您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.prev在行a.prev.next = b中，等等。但是，嘿...无论如何，您不想让其他人为您做作业， 正确的？;)

基本上，在双向链表中，每个元素都知道如何到达下一个元素（a.next）和前一个元素（a.prev）。冒泡排序是对这种链表进行排序的一个很好的候选者，因为它只比较相邻元素。否则，快速排序或合并排序或它们的组合可能会快得多，但它们确实需要对元素进行索引访问，而链表通常不提供这种访问。

希望这可以帮助。

顺便说一句：Youtube 有一大堆很酷的视频很好地解释了这些事情。

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

还有一个更不寻常的：http ://www.youtube.com/watch?v=lyZQPjUT5B4 （其中一个用于快速排序的音乐要好得多：）

Answer 2

它看起来不像你在正确的道路上。您需要完全消除索引的使用，而是使用节点引用。首先开发代码以从列表中删除一个元素，仅给出对该元素的引用。然后开发代码以在列表中已有元素之前将元素插入列表中，仅给出对这两个元素的引用。然后，您可以在这两种方法之上构建排序算法。

例如，以下是删除元素的方法：

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

您应该充分了解双向链表的工作原理，以了解为什么此代码应适用于列表中间的元素。根据您表示列表的方式，您可能需要测试结束条件（element.previous()和/或element.next()存在null）。

Answer 3

想想冒泡排序在常规数组上的工作方式。一个简单的冒泡排序实现如下所示：

   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);
            }
        }    

不同之处在于，您必须将对下一个和上一个 Node 的引用存储在 List 中，而不是使用 temp int

Answer 4

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