使用链表的冒泡排序实现只能部分工作

本文关键字：能部 工作 实现 冒泡排序 链表 | 更新日期: 2023-09-27 18:05:43

我试图使用冒泡排序对项目列表进行排序。我知道这不是最有效的排序的方法;然而，我需要这种方法在转移到更好的事情之前工作。我目前的代码部分排序列表，但我不能看到我做错了什么。

public class ListComponents
{
    public int Priority;
    public string Name;
    public ListComponents Next;
}
public void bubblesort()
{
    ListComponents Current = Head; 
    int temp = 0;
    bool swapped = true;
    while (swapped)
    {
        Print(); // Debug Function to print each swap
        Current = Head.Next; // RESET CURRENT TO HEAD + 1 ON EACH ITERATION?
        swapped = false;
        for (int sort = 0; sort < (size - 1); sort++) //Size defined as # of items in list
        {
            if (Current != null && 
                Current.Next != null && 
                Current.Priority> Current.Next.Priority)
            {
                temp = Current.Priority;
                Current.Priority= Current.Next.Priority;
                Current.Next.Priority= temp;
                Current = Head; // POTENTIAL ISSUE?
                swapped = true;
            }
        }
    }
}

我的调试打印函数显示了以下内容，显示了这些值几乎是有序的:

List: 4 2 1 3  (Inital List Order)
List: 1 4 2 3  (First Swap)
List: 1 2 4 3  (Second Swap)

问题似乎是设置"当前"值，虽然我看不出这是不工作的地方。

使用链表的冒泡排序实现只能部分工作

我的建议:重新开始。这真是一团糟。

当我还是初学者的时候，我是这样处理这些问题的。首先用伪代码编写代码:

void BubbleSort(ListComponent head)
{
    if the list is of zero length then it is already sorted, so return
    if the list is of length one then it is already sorted, so return
    Otherwise, the list is of length two or more. Therefore we know that
    a first item exists and a second-last item exists.
    Our strategy is: run down the list starting with the first item
    and ending with the second-last item. If at any time the current
    item and the one following it are out of order, swap their elements.
    If we made no swaps then the list is sorted, return. 
    If we made one or more swaps then the list might not be sorted, so 
    run down the list again.
}

好了，现在我们可以开始把它翻译成代码了

void BubbleSort(ListComponent head)
{
    // if the list is of zero length then it is already sorted, so return
    if (head == null) return; 
    // if the list is of length one then it is already sorted, so return
    if (head.Next == null) return; 
    // Otherwise, the list is of length two or more. Therefore we know that
    // a first item exists and a second-last item exists.
    // Our strategy is: run down the list starting with the first item
    // and ending with the second-last item. 
    for (ListComponent current = head; 
        current.Next != null; 
        current = current.Next)
    {
        If at any time the current item and the one following it
        are out of order, swap their elements.
    }
    If we made no swaps then the list is sorted, return. 
    If we made one or more swaps then the list might not be sorted, so 
    run down the list again.
}

好的，我已经把一些英文翻译成代码了。你能把剩下的翻译一下吗?

另一个带有两个属性的简单类的例子。这不是为数组，而是为一个简单的类模拟指针…只是为了好玩!

class MyLinkedList
{
MyLinkedList nextNode;
int data;
public void OrderListBubbleAlgoritm(ref MyLinkedList head)
{
    bool needRestart = true;
    MyLinkedList actualNode = head; //node Im working with        
    int temp;
    while (needRestart)
    {
        needRestart = false;
        actualNode = head;
        while (!needRestart && actualNode.nextNode != null)
        {
            if (actualNode.nextNode.data >= actualNode.data) //is sorted
            {
                actualNode = actualNode.nextNode;
            }
            else
            {
                //swap the data
                temp = actualNode.data;
                actualNode.data = actualNode.nextNode.data;
                actualNode.nextNode.data = temp;
                needRestart = true;
            }
        }
    }
}
}

记住只对少量数据使用冒泡排序。
性能:O (n ^ 2)

相关文章：