doubly-linked-list - 使用双向链表的排序算法

Question

作为作业，我必须用双向链表实现四种排序算法(Insertion、Selection、Shell、Quicksort)，但我完全迷路了，因为我在网上找到的所有排序算法的解释都需要使用数组。我试图将此代码用作我的 DLL 的伪索引:

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

            return x;
        }
    }

但这还不够，因为它不是二传手。有什么想法吗？

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

选择排序在列表上实现起来很简单——你使用两个指针，一个(我称之为头)指向下一个未排序的位置(从列表的开头开始，每次向前移动一步)另一个搜索从列表头到尾的最小元素。

Shell 排序基于插入排序，基于该思想实现应该不难。