单向链表的排序

Question

单向链表的排序

algorithmsorting

9

如何对单向链表进行排序。（这里的问题是单链表的属性+使用LinkedList进行排序比数组更难）我希望看到伪代码。

请尽可能使其在时间和空间上效率最高。

谢谢！

- user399950

作业？如果是，请说一下你目前完成了多少。 - Jon Skeet

1

可能是排序链表的重复问题。 - kennytm

5个回答

6

我认为使用归并排序可以满足O(n log(n))时间复杂度和O(1)空间复杂度的要求。具体实现如下：

首先，我们拿这个列表举例： 3 -> 2 -> 1 -> 5 -> 6 -> 4

第一次遍历：设定第一个、第二个和第三个节点指针将第一个和第二个节点中较小的那个指向较大的那个将最后一个节点指向原始列表的其余部分重复以上步骤直到列表末尾结果是：2 -> 3 -> 1 -> 5 -> 4 -> 6

此时，每对节点都已经排好序。

第n次遍历：设定第一个、第2^(N-1)个和(2^N)+1个节点指针比较这两个节点中较小的一个，并移动它的指针重复以上步骤直到两个长度为2^N的列表都被遍历完，每次追加较小的节点到之前较小的节点的后面将指针指向原始列表的其余部分重复以上步骤直到列表末尾

0次遍历：3 -> 2 -> 1 -> 5 -> 6 -> 4 （每个单独的节点都已经排好序）（显然） 1次遍历：2 -> 3 -> 1 -> 5 -> 4 -> 6 （每对两个节点都已经排好序） 2次遍历：1 -> 2 -> 3 -> 5 -> 4 -> 6 （每个四个节点的块都已经排好序） 3次遍历：1 -> 2 -> 3 -> 4 -> 5 -> 6 （每个八个节点的块都已经排好序）

时间复杂度：log(n)次遍历，每次需要n次比较 O(n log(n))

空间复杂度：指针和整型变量 O(1)

- T.K.

5

由于链表仅是由其他项指向的一些项，因此您可以使用O(n)时间和O(n)空间构建指针数组，使用任何出色的排序算法进行排序，其时间复杂度为O(n log n)，空间复杂度为O(1)，然后使用O(n)时间和O(1)空间从头开始重构链表。

总体而言，这是O(n log n)时间和O(n)空间。

- paxdiablo

听起来很不错，能否使用O(1)空间和O(nlogn)时间进行排序？ - user399950

2

据我所知，不行。由于您无法在O(1)中访问任意列表节点，这使得这种情况变得不太可能。实际上，正是O(n)的空间允许O(1)的单个访问时间，进而使得O(n log n)的总排序时间成为可能。 - paxdiablo

2

我原本认为可以用就地快排来完成，但我错了。这种方式无法在单向链表上实现，因为需要能够通过倒退浏览列表。

所以真正的问题变成了如何进行就地快速排序。

操作如下：

1. 取一个指针指向链表的第一个、第二个和最后一个节点。 2. 将第二个指针移动到一个大于第一个指针的节点。 3. 将第三个指针向后移动，直到找到一个小于第一个指针的节点。此步骤无法在单向链表中使用。 4. 交换第二个和第三个指针的值。 5. 重复执行步骤2-5，直到第二和第三个指针相等。 6. 将第一个节点插入第二个指针之后。

此时，链表被分为以下两部分：

[小于x的节点] x [大于x的节点]

7. 对“小于x的节点”和“大于x的节点”的块重复执行步骤2-7，直到“小于x的节点”的大小为1。

空间：每层3个指针。时间：与快速排序相同，一般情况下为O(nlogn)，最坏情况下为O(n^2)（如果列表已经排序或按相反顺序）。

- 格式和愚蠢错误已经修复。

- T.K.

我喜欢阅读这篇文章，经过简短的查看，我认为算法是可靠的。然而，我认为它不是O(1)空间复杂度，而是O(log n)空间复杂度。请记住，每个递归“堆栈帧”都需要3个指针（即使您没有使用实际递归）。在分治时，您不能仅仅放弃它们的旧值。 - Mark Peters

在这里描述：http://en.wikipedia.org/wiki/In-place_algorithm。快速排序通常被描述为一种原地算法，但实际上并不是。大多数实现需要O(log n)的空间来支持其分治递归。尽管如此，仍然比O(n)好，所以+1。 - Mark Peters

@Mark Peters - 啊，你说得对。我没想到栈帧上的指针，这显然是需要考虑的，因为它是伪递归。我的错。我会再花一点时间想想能够在 O(n log(n)) 中运行的原地排序算法。 - T.K.

问题不是规定了单向链表吗？而这个算法不需要双向链表吗？ - Jeffrey L Whitledge

@Jeffrey L Whitledge - 嗯，这太尴尬了。我无法通过单向链表向后移动。我真是太蠢了。 - T.K.

0

插入排序和快速排序在单链表上的效率与数组相同。

- James Curran

1

谢谢您的快速回答，能否请您解释一下如何实现呢？似乎这些排序算法利用随机访问属性来实现效率例如，在归并排序中，如何访问列表的中间元素？您需要运行n/2步。 - user399950

快速排序在单向链表上的效率不能像在数组上一样高。 - Cam

@incrediman：为什么不呢？从列表中取出第一个作为枢轴，然后遍历其余部分，构建两个新列表。对这两个列表进行排序。将它们拼接在一起。使用链表比使用数组更容易。（我承认我关于归并排序的想法是错误的） - James Curran

难道拼接不是O(n)吗？如果不是，你必须在列表中跟踪每个列表的长度，这肯定也不会有效率。如果您能编写单链表的快速排序伪代码实现，并演示其效率与数组上的快速排序相等，那将非常有用。 - Cam

你必须跟踪列表中每个列表的尾部。 - Cam

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

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

- keiter · Accepted Answer

合并排序只涉及几个简单的步骤：

检查列表是否为空或只有一个元素。如果是，则返回未更改的列表。
将列表分成两半。对两部分进行合并排序。
通过重复从两个列表中取出较小的元素来合并列表。由于部分列表已经排序，因此这只是查看两个列表中的第一个元素并选择较小的元素的问题。
返回合并后的列表。

结果将得到一个按最小元素顺序排序的链接列表。

Haskell中的代码示例：

import Data.List(splitAt)

--Mergesorts a list by smallest element first.
sort :: Ord a => [a] -> [a]
sort = sortBy (<)

--Generic sort that can sort in any order.
sortBy :: (a -> a -> Bool) -> [a] -> [a]
sortBy _ [] = []
sortBy _ [x] = [x]
sortBy f xs = merge f (sortBy f first) (sortBy f second)
    where
        (first,second) = split xs

--Splits a list in half.
split :: [a] -> ([a],[a])
split xs = splitAt (halfLength xs) xs

--Returns a lists length divided by two as a whole number (rounded).
halfLength :: [a] -> Int
halfLength = round . (/2) . fromIntegral . length

--Merges two lists in the provided order.
merge :: (a -> a -> Bool) -> [a] -> [a] -> [a]
merge _ [] [] = []
merge _ [] (y:ys) = y:ys
merge _ (x:xs) [] = x:xs
merge f (x:xs) (y:ys) =
    if f x y
        then x : merge f xs (y:ys)
        else y : merge f (x:xs) ys