3

我正在使用 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 个节点时，bubblesort 方法停止工作（无法正确排序列表）。谁能帮我？

4

4 回答 4

2

您需要澄清“停止工作”的意思......失败了？核心转储？没有正确排序列表？

问题是您需要在（迭代之前）的每次迭代中current重新设置。 head+1ij

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

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

于 2011-03-18T17:04:11.343 回答
1

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

顺便提一句 ..

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 个项目，当它开始是内部循环时，您将获得正确的结果。

此外，您的交换位略有不正确，您应该交换节点而不仅仅是数据。即节点的下一个字段和当前节点的哪些点需要更新。这应该让您获得更多的布朗尼积分，而不仅仅是交换数据。

还有一些调试提示：添加一个 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)

您的代码不会崩溃，因为它目前没有做任何事情。

希望这可以帮助。

于 2011-03-18T17:12:45.853 回答
0

你有两个嵌套循环声明i和j变量，但你永远不会在循环中使用它们。这显然是错误的。

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

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

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

于 2011-03-18T17:04:38.563 回答
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-01T22:22:50.250 回答