C++ 如何使用冒泡排序对链表进行排序？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/19522121/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to sort a linked list using bubble-sort?
提问by Reboot_87
I am trying to use bubble-sort in order to sort a linked list. I use curr and trail in order to traverse thru the list. curr is supposed to be one step ahead of trail always. This is my code so far:
我正在尝试使用冒泡排序来对链表进行排序。我使用 curr 和 trail 来遍历列表。curr 应该总是领先一步。到目前为止，这是我的代码：
void linked_list::sort ()
{
int i,j=0;
int counter=0;
node *curr=head;
node *trail=head;
node *temp=NULL;
while (curr !=NULL)
{
curr=curr->next; //couting the number of items I have in my list.
counter++; //this works fine.
}
curr=head->next; // reseting the curr value for the 2nd position.
for (i=0; i<counter; i++)
{
while (curr != NULL)
{
if (trail->data > curr->data)
{
temp=curr->next; //bubble sort for the pointers.
curr->next=trail;
trail->next=temp;
temp=curr; //reseting trail and curr. curr gets back to be infront.
curr=trail;
trail=temp;
if (j==0) //i'm using j to determine the start of the loop so i won't loose the head pointer.
{
head=trail;
}
}
j++;
trail=curr;
curr=curr->next; //traversing thru the list. nested loop.
}
trail=head;
curr=trail->next;
curr->next=trail->next->next; //traversing thru the list. outer loop.
j=0;
}
}
What am I missing here?
我在这里缺少什么？
回答by WhozCraig
You're missing several things; the most important being linked lists are not arrays, and as such you cannot easily do certain algorithms with both interchangeably. With that please consider the following:
你错过了几件事；最重要的是链表不是数组，因此您无法轻松地将某些算法互换使用。因此，请考虑以下事项：
- List length is determined by reaching the last node, but you don't need it for this algorithm.There should be no reason to scan the list just to find a count that you don't need in the first place. Your "finished" state is reached when the last segment of the bubble sort reaches a single node (i.e. it has no
nextto goto). - The secret to linked list (or any other node-pointer pattern) is the manipulation of the pointers. To that end, you can greatly utilize something you already use for manipulating your nodes: pointers, but not just any pointers. pointers to pointers.
- Never underestimate the power of a sheet of paper and a pencil to draw out how you want your algorithm to work. Especially for something like this:
- 列表长度由到达最后一个节点决定，但此算法不需要它。应该没有理由只是为了找到一个您不需要的计数而扫描列表。当冒泡排序的最后一段到达单个节点（即它不必
next转到）时，您的“完成”状态就达到了。 - 的秘密链表（或任何其它节点指针图案）是操纵指针。为此，您可以充分利用已经用于操作节点的东西：指针，但不仅仅是任何指针。指向指针的指针。
- 永远不要低估一张纸和一支铅笔的力量来描绘出你希望你的算法如何工作。特别是对于这样的事情：
Now take a look at the following considerably different approach. There is something within that is paramount to understanding the overall algorithm, but I'll save it for after the code :
现在来看看以下截然不同的方法。其中有一些东西对于理解整体算法至关重要，但我会在代码之后保存它：
void ll_bubblesort(struct node **pp)
{
// p always points to the head of the list
struct node *p = *pp;
*pp = nullptr;
while (p)
{
struct node **lhs = &p;
struct node **rhs = &p->next;
bool swapped = false;
// keep going until qq holds the address of a null pointer
while (*rhs)
{
// if the left side is greater than the right side
if ((*rhs)->data < (*lhs)->data)
{
// swap linked node ptrs, then swap *back* their next ptrs
std::swap(*lhs, *rhs);
std::swap((*lhs)->next, (*rhs)->next);
lhs = &(*lhs)->next;
swapped = true;
}
else
{ // no swap. advance both pointer-pointers
lhs = rhs;
rhs = &(*rhs)->next;
}
}
// link last node to the sorted segment
*rhs = *pp;
// if we swapped, detach the final node, terminate the list, and continue.
if (swapped)
{
// take the last node off the list and push it into the result.
*pp = *lhs;
*lhs = nullptr;
}
// otherwise we're done. since no swaps happened the list is sorted.
// set the output parameter and terminate the loop.
else
{
*pp = p;
break;
}
}
}
This is radically different than you probably expected. The purpose of this simple exercise is to establish that we're evaluatingdata, but we're actually sortingpointers. Notice that except for p, which is always the head of the list, we use no additional pointers to nodes. Instead we use pointers-to-pointers to manipulate the pointers buried in the list.
这与您可能预期的完全不同。这个简单练习的目的是确定我们正在评估数据，但我们实际上是在对指针进行排序。请注意，除了p始终是列表头的 之外，我们没有使用其他指向节点的指针。相反，我们使用指针到指针来操作埋在列表中的指针。
To demonstrate how this algorithm works I've written a small test app that makes a random list of integers, then turns the above loose on said list. I've also written a simple print-utility to print the list from any node to the end.
为了演示该算法的工作原理，我编写了一个小型测试应用程序，它生成一个随机的整数列表，然后在所述列表上将上述内容放散。我还编写了一个简单的打印实用程序来打印从任何节点到最后的列表。
void ll_print(struct node *lst)
{
while (lst)
{
std::cout << lst->data << ' ';
lst = lst->next;
}
std::cout << std::endl;
}
int main()
{
std::random_device rd;
std::default_random_engine rng(rd());
std::uniform_int_distribution<int> dist(1,99);
// fill basic linked list
struct node *head = nullptr, **pp = &head;
for (int i=0;i<20; ++i)
{
*pp = new node(dist(rng));
pp = &(*pp)->next;
}
*pp = NULL;
// print prior to sort.
ll_print(head);
ll_bubblesort(&head);
ll_print(head);
return 0;
}
I've also modified the original algorithm to include printing after each pass that swaps something:
我还修改了原始算法，以在每次交换某些内容后进行打印：
*pp = *lhs;
*lhs = nullptr;
ll_print(p);
Sample Output
样本输出
6 39 13 80 26 5 9 86 8 82 97 43 24 5 41 70 60 72 26 95
6 13 39 26 5 9 80 8 82 86 43 24 5 41 70 60 72 26 95
6 13 26 5 9 39 8 80 82 43 24 5 41 70 60 72 26 86
6 13 5 9 26 8 39 80 43 24 5 41 70 60 72 26 82
6 5 9 13 8 26 39 43 24 5 41 70 60 72 26 80
5 6 9 8 13 26 39 24 5 41 43 60 70 26 72
5 6 8 9 13 26 24 5 39 41 43 60 26 70
5 6 8 9 13 24 5 26 39 41 43 26 60
5 6 8 9 13 5 24 26 39 41 26 43
5 6 8 9 5 13 24 26 39 26 41
5 6 8 5 9 13 24 26 26 39
5 6 5 8 9 13 24 26 26
5 5 6 8 9 13 24 26
5 5 6 8 9 13 24 26 26 39 41 43 60 70 72 80 82 86 95 97
Another Sample
另一个样本
62 28 7 24 89 20 94 26 27 21 28 76 60 51 99 20 94 48 81 36
28 7 24 62 20 89 26 27 21 28 76 60 51 94 20 94 48 81 36
7 24 28 20 62 26 27 21 28 76 60 51 89 20 94 48 81 36
7 24 20 28 26 27 21 28 62 60 51 76 20 89 48 81 36
7 20 24 26 27 21 28 28 60 51 62 20 76 48 81 36
7 20 24 26 21 27 28 28 51 60 20 62 48 76 36
7 20 24 21 26 27 28 28 51 20 60 48 62 36
7 20 21 24 26 27 28 28 20 51 48 60 36
7 20 21 24 26 27 28 20 28 48 51 36
7 20 21 24 26 27 20 28 28 48 36
7 20 21 24 26 20 27 28 28 36
7 20 21 24 20 26 27 28 28
7 20 21 20 24 26 27 28
7 20 20 21 24 26 27
7 20 20 21 24 26 27 28 28 36 48 51 60 62 76 81 89 94 94 99
Notice how as soon as we have an already-sorted segment left in our ever-decreasing source list, we're done.
请注意，一旦我们在不断减少的源列表中留下一个已经排序的片段，我们就完成了。
Summary
概括
I stronglyadvise walking through the above algorithm with a debugger to understand better how it works. In fact, I advise that with most algorithms anyway, but algorithms that perform pointer-to-pointer actions can be a little daunting until you understand how powerful that really are. This is not the only way to do this task, but is an intuitive approach if you think about how linked lists are managed, and how all you're really doing is changing values stored in pointers in predictable places.
我强烈建议使用调试器遍历上述算法，以更好地了解它是如何工作的。事实上，我建议大多数算法无论如何，但是执行指针到指针操作的算法可能有点令人生畏，直到您了解它的真正强大之处。这不是完成此任务的唯一方法，但如果您考虑如何管理链表，以及您真正所做的只是更改存储在可预测位置的指针中的值，则这是一种直观的方法。
回答by pippin1289
Basically, here is a revised sort. You mostly had the right idea. Mainly you messed up the swapping of pointers for the nodes. Here is a revised algorithm that is slightly simpler. On the outer loop is a forthe number of elements in the list. Then the inner loop is the pushing of values to the end of the list progressively. We track two pointers trailand curr. And we compare currand curr->next.
基本上，这里是一个修改后的排序。你的想法大多是正确的。主要是你搞砸了节点的指针交换。这是一个稍微简单的修改后的算法。外循环是for列表中元素的数量。然后内循环是逐步将值推送到列表的末尾。我们跟踪两个指针trail和curr。我们比较curr和curr->next。
void linked_list::sort ()
{
int count = 0, i;
node *start = head;
node *curr = NULL;
node *trail = NULL;
node *temp = NULL;
while(start != NULL) { //grab count
count++;
start = start->next;
}
for(i = 0; i<count; ++i) { //for every element in the list
curr = trail = head; //set curr and trail at the start node
while (curr->next != NULL) { //for the rest of the elements in the list
if (curr->data > curr->next->data) { //compare curr and curr->next
temp = curr->next; //swap pointers for curr and curr->next
curr->next = curr->next->next;
temp->next = curr;
//now we need to setup pointers for trail and possibly head
if(curr == head) //this is the case of the first element swapping to preserve the head pointer
head = trail = temp;
else //setup trail correctly
trail->next = temp;
curr = temp; //update curr to be temp since the positions changed
}
//advance pointers
trail = curr;
curr = curr->next;
}
}
}
回答by Daniel Gi
I think this is what you looking for:
我想这就是你要找的：
void BubbledSort_linked_list(struct Node **head)
{
Node * curr = *head;
Node * next;
int temp;
while (curr && curr->next)
{
Node * next = curr->next;
while (next)
{
if (curr->data > next->data)
{
std::swap(next->data, curr->data);
}
next = next->next;
}
curr = curr->next;
}
}
回答by josepainumkal
Bubble sort using array can be easily modified to bubble sort using linked list
使用数组的冒泡排序可以很容易地修改为使用链表的冒泡排序
// Using array
for(int i=0;i<ar.length;i++){
for(int j=0;j<ar.length-1;j++){
if(ar[j]>ar[j+1]){
int temp = ar[j];
ar[j]=ar[j+1];
ar[j+1] = temp;
}
}
}
// Using linkedlist
void bubblesortlinkedlist(Node head){
Node i= head,j=head;
while(i!=null){
while(j.next!=null){
if(j.data>j.next.data){
int temp = j.data;
j.data = j.next.data;
j.next.data = temp;
}
j=j.next;
}
j=head;
i=i.next;
}
}
回答by Pratik Patil
Here is the Java Implementation of Bubble Sort on Linked List:
这是链表上冒泡排序的 Java 实现：
- Time Complexity: O(n^2)
- Space Complexity: O(1) - Bubble sort is In-Place sorting algorithm
- 时间复杂度：O(n^2)
- 空间复杂度：O(1) - 冒泡排序是就地排序算法
class Solution
{
public ListNode bubbleSortList(ListNode head)
{
boolean isSwapped = true;
for(ListNode current = head, tail = null; isSwapped && head != tail; tail = current, current = head)
{
for(isSwapped = false; current.next != tail; current = current.next)
{
if (current.val > current.next.val)
{
swap(current, current.next);
isSwapped = true;
}
}
}
return head;
}
private void swap(ListNode x, ListNode y)
{
if(x != y)
{
int temp = x.val;
x.val = y.val;
y.val = temp;
}
}
}
