双向链表排序算法

Question

双向链表排序算法

3

我需要用双向链表实现四种排序算法（插入排序、选择排序、希尔排序和快速排序），但是我完全不知道该怎么做，因为我在网上找到的所有解释都要求使用数组。我尝试使用以下代码作为我的双向链表的伪索引：

public DoubleNode this[int num]
    {
        get
        {
            DoubleNode x = head;
            for(int k = 0; k < num; k++)
                x = x.Next;

            return x;
        }
    }

但这还不够，因为它不是一个setter。有什么想法吗？

- Julian J. Tejera

可能是如何在C语言中对双向链表进行排序的最佳方法？的重复问题。 - rob mayoff

2

你正在走错方向 - 你不想模仿一个数组。你需要做的是先了解算法，以及它们如何在列表中应用。 - Ofir

@Ofir：问题是，它们中的大多数在实际应用中并不适用于链表。 - Michael Borgwardt

@MichaelBorgwardt 这正是我遇到的问题。唯一容易实现的是归并排序。我想我必须把所有信息放在一个数组中，进行排序，然后再将其放回双向链表中。 - Julian J. Tejera

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ofir · Answer 1

好的（根据我的评论），一个例子是插入排序 - 参见：http://en.wikipedia.org/wiki/Insertion_sort#List_insertion_sort_code_in_C.2B.2B - 插入排序实际上比数组更适合于列表（因为在数组中插入操作意味着移动元素）。

同样的，快速排序 http://en.wikipedia.org/wiki/Quicksort#Simple_version

选择排序在列表上很容易实现 - 你使用两个指针，一个（我称之为头部）指向下一个未排序的位置（从列表的开头开始，每次向前移动一步），另一个搜索从头到列表末尾的最小元素。

希尔排序基于插入排序，并且基于这个思想实现起来不应该太难。