链表自底向上的归并排序基于C中的list容器,基本思想和自底向上的数组归并排序在实质上没有区别即分组两两归并每一轮归并结束后分组大小扩大一倍。不熟悉自底向上归并排序的同学可以查阅相关资料这里不再赘述但需要注意的是链表自底向上的归并排序针对list的特殊存储结构进行少许优化以加快归并速度具体见以下代码#include iostream #include list #include random #include vector using std::cout; using std::list; using std::shuffle; using std::default_random_engine; using std::vector; template typename T void listSort(listT _list) { if (_list.empty()) return; size_t k 1; while (true) { typename listT::iterator first _list.begin(); typename listT::iterator second first; while (true) { size_t count 1; do { count; second; } while (second ! _list.end() count k); if (second _list.end()) { if (first _list.begin()) return; break; } count 1; while (first ! second second ! _list.end() count k) { if (*first *second) { first; } else { T temp *second; second _list.erase(second); _list.insert(first, temp); count; } } if (first second) { do { first; count; } while (first ! _list.end() count k); if (first _list.end()) { break; } second first; } else { if (second _list.end()) { break; } first second; } } k k 1; } } int main() { const size_t N 2000; for (size_t j 1; j N; j) { vectorsize_t sort_seq(j); for (size_t i 0; i sort_seq.size(); i) { sort_seq[i] i 1; } shuffle(sort_seq.begin(), sort_seq.end(), default_random_engine()); listsize_t test_obj; for (size_t i 0; i sort_seq.size(); i) { test_obj.push_back(sort_seq[i]); } cout 排序前序列: std::endl; for (const size_t run : test_obj) { cout run ; } cout std::endl; listSort(test_obj); size_t num 1; for (listsize_t::iterator run test_obj.begin(); run ! test_obj.end(); run) { if (*run ! num) { cout 排序结果错误! std::endl; return -1; } num; } cout 排序结果正确 std::endl; cout 排序结果: std::endl; for (const size_t run : test_obj) { cout run ; } cout std::endl; } return 0; }以上代码存在一个显而易见的问题,没有必要在改变节点相对顺序时调用erase,insert多做拷贝关键字和释放分配节点的额外操作对于双向链表只要改变链接指针即可只需将节点分离出来再插入新位置,这样避免了关键字拷贝和分配释放节点,但标准库list容器好像没有提供这样的函数,所以目前只能保持现状,没有更好的办法感兴趣的同学可尽情拷贝测试以上代码但引用代码务必注明来源以尊重作者的劳动成果