归并排序的迭代写法

归并排序是一种司空见惯的排序方法，而大多数实现方式都是采用递归的方法，这里介绍一下笔者从SGI-STL里面学习到的迭代实现归并排序的方法．

算法实现

这里选取排序一个链表为例子，这是因为这种迭代实现对排序链表显得更加优美，当然排序一个vector类似的容器也可以，但是需要多次申请的空间，代码显得很臃肿，这里为了阐述算法的思想，就以链表排序为例.

//仿照SGI STL里面的List容器的sort函数，实现迭代版的归并排序
ListNode *ListSort(ListNode *pHead){
    if(!pHead || !pHead->next)  return pHead;
    vector<ListNode*> counter(64, NULL);
    ListNode *carry;
    ListNode *pos = pHead;
    int fill = 0;
    while(pos){
        carry = new ListNode(pos->val);
        pos = pos->next;
        int i = 0;
        for(i = 0; i < fill && counter[i]; i++){
			//合并两个已排序的链表
            carry = MergeSortedList(carry, counter[i]); 
            counter[i] = NULL;
        }
        counter[i] = carry;
        if(i == fill) fill++;
    }
    for(int i = 1; i < fill; i++){
        counter[i] = MergeSortedList(counter[i-1], counter[i]);
    }
    return counter[fill-1];
}

算法解释

总体上来说，算法的思想就是准备64个槽(counter[i])，编号为0,1,…,63,分别表示已经排序长为1,2,…,2^63的链表．一开始这64个槽为空.

如果待排序链表还有未被取出的元素则取出下一个元素，否则转到3
将这个元素先和0号槽合并，如果此时0号槽为空则，将合并后结果放入0号槽;如果不为空那么合并后长度变为2,则清空0号槽，继续和1号槽合并，依次类推一直合并到i号槽，且i号槽为空，则将合并结果放入i号槽．转到1.
将这64个槽从低到高依次合并，得到最终的结果.

Note: 上面是算法的主体思想，但是可以看到上面的代码在实现的时候做出了一定的优化,就是设置了fill变量以避免步骤3合并所有的槽，而是合并0,1,…fill-1这些槽就可以了.

举例说明

下面以链表数据4，2，1，5，6，9，7，8，10为例分析这个迭代版的代码过程

example

在while循环里面每次都是从原链表里取出一个节点，然后往counter数组里面归并，fill值表明目前counter数组中存有数据的最大的那个数组标号+1,比如说，我们首先取出４，此时fill = 0, 直接就把４放在counter[0]链表上，fill变为1，然后取出1，就拿2与counter[0]进行merge，得到结果放到count[1],fill变为2，此时counter数组的情况是counter[0]为空，counter[1]存放2，4，再加入1时候直接放到counter[0], 再加入5时候，1与5merge，得到1，5再继续向上和couter[1]中的2,4,merge得到1，2，4，5，如果此时counter[2]不为空，那么继续merge，这里为空则1，2，4，5存到counter[2],于是就这样一步步的向上merge，每次merge链表长度都是加倍

最终取完所有数据之后，counter数组里面的数据需要最终整合一下，代码中最后一个for循环就是不断的把couter中的内容向上merge，最终形成最后的结果

这里其实也就是形成了一颗归并树，时间复杂度依然是O(nlgn)

复杂度分析

时间复杂度O(nlgn),空间复杂度O(1)

Note: 因为是链表所以空间复杂度才会是O(1),换成连续存储的容器就不行了.

- EOF -

声明:本文采用BY-NC-SA协议进行授权.转载请注明: 归并排序的迭代写法

归并排序的迭代写法 --14 April 2014

算法实现

算法解释

举例说明

复杂度分析

Tags

相关文章