list::sort

作者: yangzhe1991 分类: 我是搞技术的 发布时间: 2011-01-16 16:20 ė 62条评论

才知道STL的链表也是支持排序的,当然不能用<algorithm>里的sort,而是<list>里的。而且实现的很巧妙。后来看了眼java.util.LinkedList,果然不能排序。

template <class T, class Alloc>
void list<T, Alloc>::sort() {
if (node->next == node || link_type(node->next)->next == node) return;
list<T, Alloc> carry;
list<T, Alloc> counter[64];
int fill = 0;
while (!empty()) {
carry.splice(carry.begin(), *this, begin());
int i = 0;
while(i < fill && !counter[i].empty()) {
counter[i].merge(carry);
carry.swap(counter[i++]);
}
carry.swap(counter[i]);
if (i == fill) ++fill;
}

for (int i = 1; i < fill; ++i)
counter[i].merge(counter[i-1]);
swap(counter[fill-1]);
}

貌似是分治排序,虽然有的地方说是快排。

本文出自 杨肉的演讲台,转载时请注明出处及相应链接。

本文永久链接: https://yangzhe1991.org/blog/2011/01/listsort/

2条评论

  1. 战聆ARiA 2011 年 1 月 17 日 15:45 回复
    Unknown Unknown Unknown Unknown

    你这也莫人儿来啊 🙄

    1. yangzhe1991 2011 年 1 月 17 日 15:48 回复
      Unknown Unknown Unknown Unknown

      有人回和有人来是两码事……

yangzhe1991进行回复 取消回复

您的电子邮箱地址不会被公开。 必填项已用*标注

Ɣ回顶部