[TL][排序]如何在不修改链表的情况下获得一个排序后的指针数组？

[Xpol Wan]

大家好，本人算法盲，请教一下：

我有一个双向链表，里面存储了若干元素。

现在想获得一个这些元素的排序后的引用（指针）数组。

要求不能修改原来的链表，或者至少最后要还原原来的链表。

而且算法要stable。

我能想到的就是n次循环，第k次取得第k大的元素。

有没有更好的解决办法啊？

另外，这类问题叫什么名字啊？就是原数据不变，仅仅获得排序后的索引（指针）数组。

Best Regards!

Xpol Wan
_G['China']['Human']['Male']['Software']['Programmer']['Embedded']['Gaming']['C/C++/Lua']

[Shuo Chen]

如果元素T复制的开销很小，那么就建一个 vector<pair<T, Node*> >，对它排序。
如果T比较大，那么对vector<Node*>用自定义的比较函数排序。

> _G['China']['Human']['Male']['Software']['Programmer']['Embedded']['Gaming'-]['C/C++/Lua']

[Li Ferdinand]

把这些元素复制到set里，按set迭代取出各指针就行了。

[emac...@gmail.com]

Index sort

[Xinyu LIU]

Knuth 在TAOCP第三卷的正文一上来就讲了这个问题。
我现在用这个问题的逆问题来做面试：
  已知某年超女的参赛选手名单：张靓颖，李宇春，....
  以及她们的获奖名次：3, 1, 10, ....
请按照名次顺序输出她们的名字，要求O(N)时间。

2012/2/9 <emac...@gmail.com>

--
Larry, LIU Xinyu
https://sites.google.com/site/algoxy/
https://github.com/liuxinyu95/AlgoXY

[rockeet febird]

感觉你这个问题很奇怪. 遍历链表，将指针存入指针数组，然后对指针数组(按指针指向的目标)排序，再返回，不行吗？

On Feb 9, 12:31 pm, Xpol Wan <xpol...@gmail.com> wrote:

[李坤]

选手名单和获奖名次是两个数组，分别为name[1..N]，rank[1..N]，数组下标相当于姓名索引。
我们新建一个数组new[]1..N]，然后将第k名的姓名索引放到数组new的k位置，一次循环搞定。
for (i=1; i<=N; i++) {
    new[rank[i]] = i;

[Xpol Wan]

是这样做的，我只是想知道这种情况下有没有更好的办法。

Best Regards!

Xpol Wan
_G['China']['Human']['Male']['Software']['Programmer']['Embedded']['Gaming']['C/C++/Lua']

2012/2/9 rockeet febird <roc...@gmail.com>

[Ronald Liu]

不太明白你说的问题。我的理解就是一般的排序，比较的时候比较指针指向的值，交换时交换指针的值就是了。

[Tux9]

显然不一样，链表排序跟数组排序一点都不一样

2012/2/9 Ronald Liu <lzs...@gmail.com>

[emac...@gmail.com]

附加要求 O(1) 空间
Huang Bing Chao's algorithm

至今未能查明他的中文名怎么写的

[Ronald Liu]

完全一样，链表元素不过是个卫星数据。不需要对卫星数据进行物理上的交换，只要交换他们的指针就可以了。

[Tux9]

交换指针跟数组交换元素能一样么。。。开销就不一样好么

2012/2/9 Ronald Liu <lzs...@gmail.com>

完全一样，链表元素不过是个卫星数据。不需要对卫星数据进行物理上的交换，只要交换他们的指针就可以了。

[Ronald Liu]

@李坤 的算法只对密布的数据有用，对于一般的键数据等价为计数排序。
@Tux9 交换指针和交换元素的开销必然不一样，但是对于排序是一样的。
这里先初始化一个数组，元素为键/元素指针 对。这需要对于链表进行一次扫描T(n) =
Big-Theta(n)。当排序时比较键，交换时同时交换键和元素指针，最后得到的就是楼主需要的指针数组。总的时间复杂度为O(nlgn)。
对于更一般的情况，只是初始化上述数组的步骤不一样。

[Xinyu LIU]

Hi,

本题可以O(N)时间， O(1)空间解决。

2012/2/9 李坤 <liku...@gmail.com>

[Tux9]

你分别用数组和链表写个快排，然后就知道哪儿不一样了

2012/2/10 Ronald Liu <lzs...@gmail.com>

[xiaokun]

怎么解阿？

[yinfei yang]

for i = 1 : n

    while rank[i] != i

        swap( name[ rank[ i ] ],  name[ i ] )

        swap( rank[ rank[ i ] ],    rank[ i ]  )

   

这样？

 

每一次swap 确定一个的位置， 总共N次swap能全部定位。 

Best regards!

Yinfei Yang 
Saint Joseph's University
5600 City Avenue, Philadelphia PA

2012/2/10 xiaokun <xiaok...@gmail.com>

[emac...@gmail.com]

name = [4,0,3,2,1]
rank = [1,4,3,2,0]

[XIN, Wang]

插入排序不就行了

2012/2/11 <emac...@gmail.com>

[Xinyu LIU]

Exactly! 正解

对应的python code:
for i in range(n):
        while cnt[i] != i:
            j = cnt[i]
            (xs[i], xs[j]) = (xs[j], xs[i])
            (cnt[i], cnt[j]) = (cnt[j], cnt[i])

这里xs和cnt分别对应name和rank。本题不需要排序，名次列表已经包含排序信息了。
一旦排序，复杂度就下降到O(N \lg N)了。

有人问，Knuth不是证明，任何基于比较的排序不可能小于O(N \lg N)么？此题之所以可以O(N)解决，是因为元素的特殊性：这里不是任意N个可比较的元素，而是1~N这N个数字。

2012/2/11 yinfei yang <yang...@gmail.com>

[jinhu wang]

-->map -->array

[Ronald Liu]

请再读一下楼主的要求，根本没有提供名次。

[Jawley]

是你没有看清，Xinyu LIU 一开始就提到了，这不是原问题，是逆问题。我的理解，这里的rank[]是指元素的原始排列顺序。因为楼主的问题要求“至少最后要还原原来的链表”，所以实际上这个还原过程就是已知rank[]来还原原有顺序的过程，也就是Xinyu LIU所讲的逆问题。而这个“还原”的需求一旦解决，那么剩下的排序就是普通的排序了。

Jawley

[Wu Zhenyu]

能否试试冒泡？

[Fansong Zeng]

不就是置换群嘛

在 2012年2月13日 下午1:23，Xinyu LIU <liuxi...@gmail.com>写道：

[赵帅]

把链表里的所有节点(数据加指针)放入数组，对数组排序不就行了？

在 2012年2月9日 下午12:31，Xpol Wan <xpo...@gmail.com>写道：

[Tux9]

赞想法。。。居然不考虑复杂度

[赵帅]

这个的时间复杂度就是普通的数组排序的复杂度

[赵帅]

这个链表里的元素的key没有你说这个问题的这种特殊性

在 2012年2月9日 下午4:26，Xinyu LIU <liuxi...@gmail.com>写道：

[Tux9]

对你无语了。。。

2012/6/26 赵帅 <rost...@gmail.com>

这个的时间复杂度就是普通的数组排序的复杂度

[赵帅]

你要不想好好讨论 可以闭嘴

2012/6/26 Tux9 <tux...@gmail.com>

[Tux9]

你这典型的就不是解决方案，没有人这么做的，如果可以这么做就没必要用链表了

2012/6/27 赵帅 <rost...@gmail.com>

你要不想好好讨论 可以闭嘴

[赵帅]

现在想获得一个这些元素的排序后的引用（指针）数组。

要求不能修改原来的链表，或者至少最后要还原原来的链表。

这是楼主的需求，

0.楼主一定需要一个数组盛放结果

1.我没改变原链表

2.我得到排序后的数组。

你能清楚的告诉我你无语在哪里了吗

此外:

       即使对原来链表本身进行排序，这样做也没有任何问题，只是会多出多余的空间消耗。

       用排序后的数组完全可以构造一个新的链表

       

[Tux9]

你这思路就完全不对

2012/6/28 赵帅 <rost...@gmail.com>

[赵帅]

8