0

我正在尝试使用冒泡排序对项目列表进行排序。我知道这不是最有效的排序方法；但是，在继续做更好的事情之前，我需要这种方法起作用。我当前的代码对列表进行了部分排序，但我看不出我做错了什么。

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)

问题似乎与设置“当前”值有关，尽管我看不出这在哪里不起作用。

4

2 回答 2

13

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

当我还是初学者时，这就是我将如何解决此类问题的方法。首先在pseduo-code中编写代码：

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.
}

好的，我已经将一些英语翻译成代码。你能翻译剩下的吗？

于 2013-03-25T21:54:25.767 回答
0

另一个具有 2 个属性的简单类的示例。这不是用于数组，而是用于模拟指针的简单类......只是为了好玩！

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)

于 2014-08-02T01:30:33.740 回答