C# 中通用列表的冒泡排序

Question

我正在使用 C# 中的通用列表，但是当我尝试使用冒泡排序方法对节点进行排序时遇到问题。

namespace ConsoleApplication1
{    

public class GenericList
{
    private class Node
    {
        // Each node has a reference to the next node in the list.
        public Node Next;           
        public int Data;
    }

    // The list is initially empty.
    private Node head = null;

    // Add a node at the beginning of the list with t as its data value.
    public void AddNode(int t)
    {
        Node newNode = new Node();
        newNode.Next = head;
        newNode.Data = t;
        head = newNode;
    }


//list length
        public int Size()
        {
            int listsize= 0;
            Node current = head;
            while (current != null)
            {
                listsize++;
                current = current.Next;
            }
            return listsize;            
        }

        //bubble sort
        public void bubblesort()
        {
            int size = Size();

            Node current = head;

            for (int i = 1; i < size; i++)
            {
                for (int j = 0; j < size - 1; j++)
                {


                    if (current.Data > current.Next.Data && current.Next!=null)
                    {
                        int temp = current.Data;
                        current.Data = current.Next.Data;
                        current.Next.Data = temp;
                    }

                }
            }

            head = current;
        }
     }
}

当我向列表中添加超过 5 个节点时，冒泡排序方法将停止工作（无法正确对列表进行排序）。 有人能帮我吗？

Answer 1

您需要澄清“停止工作”的含义......失败？核心转储？列表排序不正确？

问题是您需要在 i 的每次迭代中（在 j 之前）将 current 重置回 head+1 > 迭代）。

如果您希望将最大值向上移动，则 j 应该从 1 向上移动到 size-i （因为在第一次传递最大数字之后将位于顶部 - 无需再次检查）。或者将运行 j 的最小值从 size-1 降低到 i。

嵌套循环方法的替代方法：您可以使用 while / boolean /loop 方法（在 while 外部，布尔值指示是否进行更改，for 循环内部）。当数据已经排序时，这会带来轻微的性能优势 - 它会在嵌套的 for 方法之前停止处理（即使数据已经排序，该方法也会运行最大次数）。

Answer 2

来吧伙计们..让他放松一下..这是谷歌一代。

顺便说一句..

http://www.google.co.uk/search?q=C%23+bubble+sort

..会给你一些很好的例子。

现在，您的代码实际上出了什么问题：

此代码（从上面）

    Node current = head;

    for (int i = 1; i < size; i++)
    {
        for (int j = 0; j < size - 1; j++)
        {


            if (current.Data > current.Next.Data && current.Next!=null)
            {
                int temp = current.Data;
                current.Data = current.Next.Data;
                current.Next.Data = temp;
            }

        }
    }

与以下内容完全相同：

    Node current = head;
            if (current.Data > current.Next.Data && current.Next!=null)
            {
                int temp = current.Data;
                current.Data = current.Next.Data;
                current.Next.Data = temp;
            }

您不更改“当前”节点，即您始终对列表中的第一个和第二个项目进行排序。

我不会给你完整的解决方案，毕竟这就是家庭作业的目的。在循环中，确保当前的内容始终是列表中的第“j”项，当它开始是内部循环时，您将获得正确的结果。

此外，您的交换位略有不正确，您应该交换节点而不仅仅是数据。即节点的 Next 字段以及当前节点的哪个点需要更新。与仅仅交换数据相比，这应该会给你带来更多的印象分。

还有一些调试技巧：添加一个 Print() 函数，如下所示：

public void Print()
    {
        Node current = head;
        Console.Write("List: ");
        while (current != null)
        {
            Console.Write("{0} ", current.Data);
            current = current.Next;
        }
        Console.WriteLine("");
    }

并在排序循环中调用它，它将帮助您了解列表在每次迭代之间如何变化..这有助于您了解问题可能出在哪里。

List: 3 1 50 2 5 4
List: 3 1 50 2 5 4
List: 1 3 50 2 5 4
List: 1 3 50 2 5 4
List: 1 3 2 50 5 4
List: 1 3 2 5 50 4
List: 1 3 2 5 4 50
List: 1 2 3 5 4 50
List: 1 2 3 5 4 50
List: 1 2 3 4 5 50

哦！伙计..每次我阅读代码时，我都会发现一些新的错误！ ...

        if (current.Data > current.Next.Data && current.Next!=null)

应该是

        if (current != null && current.Next!=null && current.Data > current.Next.Data)

您的代码不会崩溃，因为它目前没有执行任何操作。

希望这有帮助。

Answer 3

您有两个声明 i 和 j 变量的嵌套循环，但您从未在循环内使用它们。这显然是错误的。

for (int i = 1; i < size; i++)
{
    for (int j = 0; j < size - 1; j++)
    {

您应该做的是使用 while 循环遍历列表，就像您在 Size 方法中所做的那样，如果相邻元素向后，则交换它们。您将在 bool 中跟踪是否实际执行了任何交换，如果是，则再次循环列表。这将重复，直到您没有执行任何交换。

这是假设您实际上需要实现冒泡排序来满足您的作业要求。否则，没有理由比框架中的内置集合类型和排序方法更喜欢它。

Answer 4

另一个例子是一个具有 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)