我正在尝试使用插入排序在列表中以排序方式插入节点

Question

我正在尝试在链表上的C＃中实现存储桶排序算法，但是得到正确的结果。此函数应将List和Node用作参数，然后按正确的升序插入该节点。我有一个列表[4、7、12、15]，我希望将数据为20的新Node按升序插入，例如此列表变为[4,7,12,15,20]。但是结果是我得到了此列表[4,7,12,20,15]请帮助我，其中有什么问题。我想while循环内部存在一些问题。此函数调用的所有其他函数完全正常运行

    static public void InsertionSort(LinkedList list, Node s)
            {
                int data = s.getData();
                if (list.start.getNext() == null)
                    list.InsertAtEnd(data);
                else
                {
                    int key = 0; 
                    Node temp = list.start;
                    while (temp.getNext() != null)
                    {
                        temp = temp.getNext();
                        if (data >= temp.getData())
                            key++;

                    }
                    list.InsertAt(key, data);
                }
            }

派生函数（主函数）：

LinkedList list = new LinkedList();
            int[] array = { 4, 7, 12, 15 };
            for (int i = 0; i < array.Length; i++)
                list.InsertAtEnd(array[i]);
            System.Console.WriteLine("Before Insertion");
            list.Display();
            Node n = new Node(20);
            InsertionSort(list, n);
            System.Console.WriteLine("After Insertion");
            list.Display();

输出：

[1：Output of The Code

Answer 1

开始时的设置错误。

int[] array = { 4, 7, 12, 15 };
for (int i = 0; i < array.Length; i++)
    list.InsertAtBegin(array[i]);

因为您遍历了初始数组并在开始处添加了所有项目，所以结果列表的排序顺序错误。

要开始正确的排序，请在末尾添加：

int[] array = { 4, 7, 12, 15 };
for (int i = 0; i < array.Length; i++)
    list.InsertAtEnd(array[i]);

或在另一个方向上遍历初始数组：

int[] array = { 4, 7, 12, 15 };
for (int i = array.length - 1; i >= 0; i--)
    list.InsertAtBegin(array[i]);

---

此外，您的插入算法也不是最佳选择。

使用链接列表，到达列表中的某个元素很昂贵，因为您总是必须从头到正确的位置。

您的代码首先尝试找到正确的位置来插入新元素，然后调用另一个方法InsertAt，该方法必须重新开始从列表开始遍历列表才能再次找到相同的位置。

相反，请更改代码，以便在找到具有较高值的​​元素后立即直接插入新节点。