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

时间:2021-10-22 03:35:32

解题思路:

排序方法:多路归并排序

每次将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; }