3

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

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

            return x;
        }
    }

但这还不够,因为它不是二传手。任何想法男孩/女孩?

4

1 回答 1

0

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

快速排序也是如此http://en.wikipedia.org/wiki/Quicksort#Simple_version

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

Shell 排序是基于插入排序的,基于这个想法应该不会太难实现。

于 2011-12-12T06:45:07.443 回答