完全理解歸併排序

一、歸併排序簡介

歸併排序

複雜度：O(nlogn)

歸併排序（自頂向下）的操作有兩步，分割和歸併

1、分割：將數組二等分，並將得到的子數組繼續二等分，直到每個子數組只剩下一個元素為止。

2、歸併：不斷將原本屬於同一個數組的兩個子數組歸併成一個有序的數組，方法為不斷比較子數組的首元素，並彈出較小的放入合併後組成的數組中。直到所有子數組合併為一個數組。

二、自頂向下遞歸以及自底向上迭代的歸併排序

代碼、詳細注釋以及測試：

#include<iostream>#include<vector>#include <climits>using namespace std;#define maxn (1<<20)void Merge(int arr[],int lo,int mi,int hi){//合併方法一 int ml=mi-lo; int *b=new int[ml]; for(int i=0;i<ml;i++)b[i]=arr[i+lo];//備份兩段中的前段，注意要從lo開始 int x=0,y=mi; for(int i=lo;i<hi;){ if(y>=hi||(x<ml&&b[x]<=arr[y]))//如果後段越界或者前段未越界且小於後段 arr[i++]=b[x++]; if(x>=ml||(y<hi&&arr[y]<b[x]))//如果前段越界或者後段未越界且小於前段 arr[i++]=arr[y++]; } delete []b;}void Merge2(int arr[],int lo,int mi,int hi){//合併方法二，代碼更易懂，速度稍慢 int ml=mi-lo; int *b=new int[ml]; for(int i=0;i<ml;i++)b[i]=arr[i+lo];//備份兩段中的前段，注意要從lo開始 int x=0,y=mi; for(int i=lo;i<hi;i++){ if(x>=ml)arr[i]=arr[y++];//如果前段越界 else if(y>=hi)arr[i]=b[x++];//如果後段越界 else if(b[x]<=arr[y])arr[i]=b[x++];//如果前段未越界且比後段小 else arr[i]=arr[y++]; } delete []b;}void MergeSort(int arr[],int lo,int hi){//自頂向下遞歸，採用merge if(hi-lo<2)return; int mi=(lo+hi)/2; MergeSort(arr,lo, mi); MergeSort(arr,mi, hi); Merge(arr,lo,mi,hi);}void MergeSort2(int arr[],int lo,int hi){//自頂向下遞歸，採用merge2 if(hi-lo<2)return; int mi=(lo+hi)/2; MergeSort(arr,lo, mi); MergeSort(arr,mi, hi); Merge2(arr,lo,mi,hi);}void MergeSortDownToUp(int arr[],int n){//自底向上迭代 for(int sz=1;sz<n;sz<<=1){//歸併段大小 for(int l=0;l+sz<n;l+=sz+sz){//一段段地歸併 Merge(arr, l, l+sz, min(l+2*sz,n)); } }}void MergeSortDownToUp2(int arr[],int n){//自底向上迭代，採用merge for(int sz=1;sz<n;sz<<=1){//歸併段大小 for(int l=0;l+sz<n;l+=sz+sz){//一段段地歸併 Merge2(arr, l, l+sz, min(l+2*sz,n)); } }}void print(int a[],int size){ for(int i=0;i<size;i++){ cout<<a[i]<<" "; if(0==i+1%4)cout<<endl; }}int main(){ int arr[maxn]; clock_t s,e; //MergeSort srand(unsigned(clock())); for(int i=0;i<maxn;i++)arr[i]=rand(); s=clock(); MergeSort(arr, 0,maxn); e=clock(); //print(arr,maxn); cout<<endl<<maxn<<" Num-Sortint "<<"MergeSort Using: "<<e-s<<" us"<<endl; //MergeSort2 srand(unsigned(clock())); for(int i=0;i<maxn;i++)arr[i]=rand(); s=clock(); MergeSort2(arr, 0,maxn); e=clock(); //print(arr,maxn); cout<<endl<<maxn<<" Num-Sortint "<<"MergeSort2 Using: "<<e-s<<" us"<<endl; //MergeSortDownToUp srand(unsigned(clock())); for(int i=0;i<maxn;i++)arr[i]=rand(); s=clock(); MergeSortDownToUp(arr,maxn); e=clock(); //print(arr,maxn); cout<<endl<<maxn<<" Num-Sortint "<<"MergeSortDownToUp: "<<e-s<<" us"<<endl; //MergeSortDownToUp2 srand(unsigned(clock())); for(int i=0;i<maxn;i++)arr[i]=rand(); s=clock(); MergeSortDownToUp2(arr,maxn); e=clock(); //print(arr,maxn); cout<<endl<<maxn<<" Num-Sortint "<<"MergeSortDownToUp2 Using: "<<e-s<<" us"<<endl;}

對100萬個隨機數進行排序的結果：

1048576 Num-Sortint MergeSort Using: 506184 us1048576 Num-Sortint MergeSort2 Using: 506310 us1048576 Num-Sortint MergeSortDownToUp: 421952 us1048576 Num-Sortint MergeSortDownToUp2 Using: 438836 us

簡而言之，自底向上的迭代遞歸效率稍稍高一些。

三、多路歸併

Merge k Sorted Lists - LeetCode?

leetcode.com

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

struct comp{//優先隊列的比較函數public: bool operator()(ListNode*a,ListNode *b){ return a->val>b->val; }};class Solution {public: ListNode* mergeKLists(vector<ListNode*>& lists) { ListNode pre(-1);//創造一個哨兵結點 ListNode* p=&pre; priority_queue<ListNode*,vector<ListNode*>,comp >q;//用一個優先隊列保存每個鏈表的最小結點 for(int i=0;i<(int)lists.size();i++){ if(lists[i])q.push(lists[i]); } while(!q.empty()){ ListNode*top=q.top();q.pop();//總是推出最小的結點，連接起來，並將其後的結點壓入優先隊列 p->next=top;p=p->next; if(top->next)q.push(top->next);//注意不能推入空結點 } return pre.next; }};

如果不是歸併多個鏈表而是多個數組，總的思路和上面一致，不過需要用到索引優先隊列來即時維護K個數組的首元素：演算法優化小助手：索引優先隊列

PS：

廣告時間啦~

理工狗不想被人文素養拖後腿？不妨關注微信公眾號：

推薦閱讀：