有k个list列表， 各个list列表的元素是有序的，将这k个列表元素进行排序( 基于堆排序的K路归并排序)

解题思路：

排序方法：多路归并排序

每次将n个list的头元素取出来，进行排序（堆排序），最小元素从堆中取出后，将其所在list的下一个元素

放入堆中，调整堆序列。

函数实现原型：

void listnodesort(list<list<Node> >* listlistnode){}

#include <iostream>
#include <list>

using namespace std;

struct Node{
    int value;
    Node *next = NULL;
};

///堆排序（调整堆）
void HeapAdjust(Node* heap, int i, int length){
    int min = i;
    int lch = 2*i+1;
    int rch = 2*i+2;

    if(i <= (length-2)/2){
        if(lch < length && heap[min].value > heap[lch].value){
            min = lch;
        }
        if(rch < length && heap[min].value > heap[rch].value){
            min = rch;
        }
        if(min != i){
            swap(heap[min], heap[i]);
            HeapAdjust(heap, min, length);
        }
    }
}
///堆排序（建堆）
void BuildHeap(Node* heap, int length)
{
　　 ///要确定好是-2,还是-1
    for(int i = (length-2)/2; i >=0; i--){ 
        HeapAdjust(heap, i, length);
    }
}

///主要排序函数
void listnodesort(list<list<Node> >* listlistnode)
{
    list<Node> listTotal;
    int length = (*listlistnode).size();
    Node* heap = new Node[length];
    int i = 0;
    for(list<list<Node> >::iterator iter = (*listlistnode).begin(); iter !=(*listlistnode).end(); iter ++){
        heap[i] = (*iter).front();
        i++;
    }
    BuildHeap(heap, length);
    while(length>0){
        listTotal.push_back(heap[0]);
        if(length == 1){
            break;
        }
        if(heap[0].next == NULL){
            heap[0] = heap[length-1];
            length -=1;
        }
        else{
            heap[0] = *(heap[0].next);
        }
        HeapAdjust(heap, 0, length);
    }
    cout << "totalList: ";
    for(list<Node>::iterator it=listTotal.begin(); it!=listTotal.end(); it++){
        cout << (*it).value << " ";
    }
    cout << endl;
}

list<list<Node> > buildListList(int sum, int interval)
{
    list<list<Node> > listlistnode;
    for(int i = 0; i<interval; i++){
        list<Node> listnode;

        ///mode 1: start
        Node* node = new Node(); ///此处一定要用new分配一个内存，不能直接使用Node node;
        int j = i;
        while(j<sum){
            Node* nodeNext = new Node();
            node->value = j;
            if(j+interval > sum){
                node->next = NULL;
            }
            else
                node->next = nodeNext;
            listnode.push_back(*node);
            node = nodeNext;
            j+=interval;
        }
        ///mode 1: end


        ///mode2:start
//        int j = i;
//        Node* head = NULL;
//        Node* endp = NULL;
//        while(j<sum){
//            Node* node = new Node();
//            node->value = j;
//            node->next = NULL;
//            if(head == NULL){
//                head = node;
//                endp = node;
//            }
//            else{
//                endp->next = node;
//                endp = node;   ///此处也不可忘了
//            }
//            j=j+interval;
//        }
//        while(head != NULL){
//            listnode.push_back(*head);
//            head = head->next;
//        }
        /// mode 2:end


        listlistnode.push_back(listnode);
    }

    return listlistnode;
}

void print(list<list<Node> > *listlistnode) ///到底是传值还是传指针，后续代码块中的操作也要做相应变动；
{
    for(list<list<Node> >::iterator iter=(*listlistnode).begin(); iter != (*listlistnode).end(); iter++){
        list<Node> listnode = *iter;           ///迭代器解地址后就是其内部所指内容
        for(list<Node>::iterator it=listnode.begin(); it!=listnode.end(); it++){
            cout << (*it).value << " ";
        }
        cout << endl;
    }
}

int main()
{
    list<list<Node> > listlistnode = buildListList(39,9);
    print(&listlistnode);
    listnodesort(&listlistnode);  ///根据函数的定义决定是传值还是传指针

    cout << "Hello world!" << endl;
    return 0;
}

 

另外，还有一种更加简单的方法：借助map结构，因为map本身就是key有序的序列结构，所以将listlistnode中的所有元素依次加入map中即可完成排序。

　　 map<int, int> mapNode;
    for(list<list<Node> >::iterator iter=listlistnode.begin(); iter != listlistnode.end(); iter++){
        list<Node> listnode = *iter;
        for(list<Node>::iterator it=listnode.begin(); it!=listnode.end(); it++){
　　　　　　　　///如果不存在则插入，如果存在则key相应得value++即可。
            if(mapNode.count((*it).value)==0)
                mapNode.insert(pair<int, int> ((*it).value,1));
            else{
                mapNode[(*it).value]++;
            }
        }
    }

    for(map<int, int>::iterator it = mapNode.begin(); it!=mapNode.end(); it++){
        cout << it->first << " " << it->second << endl;
    }