{"id":223076,"date":"2011-01-16T16:20:23","date_gmt":"2011-01-16T08:20:23","guid":{"rendered":"http:\/\/blog.yangzhe1991.org\/?p=223076"},"modified":"2014-03-14T19:08:15","modified_gmt":"2014-03-14T11:08:15","slug":"listsort","status":"publish","type":"post","link":"https:\/\/yangzhe1991.org\/blog\/2011\/01\/listsort\/","title":{"rendered":"list::sort"},"content":{"rendered":"

\u624d\u77e5\u9053STL\u7684\u94fe\u8868\u4e5f\u662f\u652f\u6301\u6392\u5e8f\u7684\uff0c\u5f53\u7136\u4e0d\u80fd\u7528<algorithm>\u91cc\u7684sort\uff0c\u800c\u662f<list>\u91cc\u7684\u3002\u800c\u4e14\u5b9e\u73b0\u7684\u5f88\u5de7\u5999\u3002\u540e\u6765\u770b\u4e86\u773cjava.util.LinkedList\uff0c\u679c\u7136\u4e0d\u80fd\u6392\u5e8f\u3002<\/p>\n

template <class T, class Alloc>
\nvoid list<T, Alloc>::sort() {
\nif (node->next == node || link_type(node->next)->next == node) return;
\nlist<T, Alloc> carry;
\nlist<T, Alloc> counter[64];
\nint fill = 0;
\nwhile (!empty()) {
\ncarry.splice(carry.begin(), *this, begin());
\nint i = 0;
\nwhile(i < fill && !counter[i].empty()) {
\ncounter[i].merge(carry);
\ncarry.swap(counter[i++]);
\n}
\ncarry.swap(counter[i]);
\nif (i == fill) ++fill;
\n}<\/p>\n

for (int i = 1; i < fill; ++i)
\ncounter[i].merge(counter[i-1]);
\nswap(counter[fill-1]);
\n}<\/p>\n

\u8c8c\u4f3c\u662f\u5206\u6cbb\u6392\u5e8f\uff0c\u867d\u7136\u6709\u7684\u5730\u65b9\u8bf4\u662f\u5feb\u6392\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"

\u624d\u77e5\u9053STL\u7684\u94fe\u8868\u4e5f\u662f\u652f\u6301\u6392\u5e8f\u7684\uff0c\u5f53\u7136\u4e0d\u80fd\u7528<algorithm>\u91cc\u7684sort\uff0c\u800c\u662f<lis […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[12],"_links":{"self":[{"href":"https:\/\/yangzhe1991.org\/blog\/wp-json\/wp\/v2\/posts\/223076"}],"collection":[{"href":"https:\/\/yangzhe1991.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/yangzhe1991.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/yangzhe1991.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/yangzhe1991.org\/blog\/wp-json\/wp\/v2\/comments?post=223076"}],"version-history":[{"count":1,"href":"https:\/\/yangzhe1991.org\/blog\/wp-json\/wp\/v2\/posts\/223076\/revisions"}],"predecessor-version":[{"id":224558,"href":"https:\/\/yangzhe1991.org\/blog\/wp-json\/wp\/v2\/posts\/223076\/revisions\/224558"}],"wp:attachment":[{"href":"https:\/\/yangzhe1991.org\/blog\/wp-json\/wp\/v2\/media?parent=223076"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/yangzhe1991.org\/blog\/wp-json\/wp\/v2\/categories?post=223076"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/yangzhe1991.org\/blog\/wp-json\/wp\/v2\/tags?post=223076"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}