请问如何用链表实现自顶向下归并排序

问题描述：

要求程序详实清楚

问题解答：

从最基本的递归算法开始琢磨,大致的算法过程如下 :
归并排序递归算法 R :
R1 : 如果待排序序列长度 len < 2, 则算法返回;
R2 : 将序列 list 划分成两个具有同样记录的子序列 list1,list2,
(这里可以从链表 list 中间断开而得到,而且不要求完全等长);
R3 : 分别对序列 list1 和 list2 调用这个算法(R);
R4 : 最后归并子序列 list1,list2, 得到的排序后的序列;

当时就想着如何将这个递归的过程用栈模拟出来,首先将序列 list,划分成
两个子序列 list1 和 list2,然后再将 list1 划分成两个等长的子序列,......
如果按照划分待排序序列成两个子序列来看,整个递归的过程不就是一个二叉树吗?
(没划分一次建立原来序列的两个子结点----两个新序列).而归并的过程就是对这个
二叉树进行后续遍历的过程(想像将后续遍历的动作替换为归并父节点的两个子节点).

这样一来,写链表的非递归归并排序就简单了,算法描述如下 :
归并排序非递归算法 N : 设链表类型为 List,算法使用一个大小为 log(len),
的栈 (len 为待排序链表的长度), 即
struct stack_node
{
List l;
int lev;
} stack[log(len)],栈中存储的是归并的中间结果,其中 lev 是该堆栈
节点存储的中间链表的归并层次,在归并过程中,逐步的读取原待排序
链表的记录( lev 为 1)和 stack 中栈顶记录进行相比,过程中总是保证
堆栈中链表的 lev 更高,而且每合并一次 结果的 lev 增加 1.
算法设待排序序列为 list ,结束后得到排序后的链表.
N1 : 如果链表的长度 len < 2 则算法退出;
N2 : 初始化 stack 为空,置 top <- 0;
N3 : 取 list 的第一个记录,构造新的 stack 节点 node <- {l1,0},
并压入堆栈中;
N4 : 如果 list 不空则执行步骤 N6 ,否则转到步骤 N7;
N5 : 取得 list 的首记录如上构造一个 stack 节点 node;
N6 : 如果 node.lev == stack[top - 1].lev, 则弹出栈顶节点到 node2
调用归并过程合并链表 node.l 和 node2.l (结果可以放在node中),
同时置 node.lev <-- node.lev + 1, 重复这一步直到
node.lev > stack[top - 1].lev;
N7 : 弹出栈顶记录到 node 中;
N8 : 如果 top > 0,则弹出栈顶记录 到 node2 中,归并 node.l 和node2.l,
并将结果存放在 node.l 中,重复这一步直到 top == 0,然后算法结束;
简单写了一下过程,有的地方没描述清楚,大致过程应该没有错(实现测试过).

巧的是后来看到 stl 中链表排序算法的实现,才发现本质也是这样,虽然它使用
的是 26 个list数组,而且也不是按照堆栈的 FILO 顺序进行归并,程序如下 :

#pragma once

＃i nclude <cassert>
using namespace std;

#ifndef NULL
#define NULL 0L
#endif

struct ListNode
{
int data;
ListNode* pNext;
};
class List
{
public:
List() : m_pFirst(NULL) {}
List( ListNode* p ) : m_pFirst(p){}
~List(){}
public:
void Sort();
private:
void Merge(List& rhs); //merge sorted list
void Swap(List& rhs);
bool IsEmpty() { return m_pFirst == NULL; }
private:
ListNode* m_pFirst;
};

void List::Merge(List& rhs)
{
ListNode* head1 = new ListNode;
head1->pNext = m_pFirst;

ListNode* first1 = head1;
ListNode* first2 = rhs.m_pFirst;

while (first1->pNext != NULL && first2 != NULL)
{
if (first2->data < first1->pNext->data)
{
ListNode* mid = first2;
first2 = first2->pNext;

mid->pNext = first1->pNext;
first1->pNext = mid;
}
else
{
first1 = first1->pNext;
}
}

if (first2 != NULL)
{
first1->pNext = first2;
}

m_pFirst = head1->pNext;

delete head1;

rhs.m_pFirst = NULL;
}
void List::Swap(List& rhs)
{
ListNode* tmp = m_pFirst;
m_pFirst = rhs.m_pFirst;
rhs.m_pFirst = tmp;
}
//merge sort
//use 26 List bins with 2^i nodes stored on each List.
//a carryList merge them up respectively.
void List::Sort()
{
//size < 2
if (m_pFirst == NULL || m_pFirst->pNext == NULL)
{
return;
}

const int BIN_SIZE = 25;
List carryList;
List binList[BIN_SIZE + 1];

int maxBin = 0;

while (!IsEmpty())
{
assert(carryList.IsEmpty());
//splice first node to carry
carryList.m_pFirst = m_pFirst;
m_pFirst = m_pFirst->pNext;
carryList.m_pFirst->pNext = NULL;

int bin;
for (bin = 0; bin < maxBin && !binList[bin].IsEmpty(); bin++)
{
// merge into ever larger bins
binList[bin].Merge(carryList);
binList[bin].Swap(carryList);

assert(!carryList.IsEmpty());
assert(binList[bin].IsEmpty());
}

if (bin == BIN_SIZE)
{
binList[bin - 1].Merge(carryList);
}
else
{
binList[bin].Swap(carryList);
if (bin == maxBin)
{
maxBin++;
}
}
}
//merge up
for (int bin = 1; bin < maxBin; bin++)
{
binList[bin].Merge(binList[bin - 1]);
}
//replace from last bin
Swap(binList[maxBin - 1]);
}
原文地址：http://old.blog.edu.cn/user1/14610/archives/2006/1378895.shtml