归并排序原理

归并排序的目的就是分而治之，把一个大的问题，分解成若干个小问题，然后再把问题合并起来。具体的原理如下图所示

那就是说，整个过程需要两步，一：分，二：合。对于普通的数组我们可以递归的分，然后合并。如下所示：

#include<iostream>
#include<vector>
using namespace std;


void mergeTwoVector(vector<int>&v1,vector<int>&v2,vector<int>&out){
    out.clear();
    int i=0;
    int j=0;
    while(i<v1.size()&&j<v2.size()){
       if(v1[i]<=v2[j]){
           out.push_back(v1[i++]);
       }else
       {
           out.push_back(v2[j++]);
       }
       
    }
    while (i<v1.size())
    {
        /* code */
         out.push_back(v1[i++]);
    }
    while (j<v2.size())
    {
        out.push_back(v2[j++]);
    }
    

}
void mergeSort(vector<int>&vec){
    //分
    if(vec.size()<2){
        return;
    }
    vector<int> subVectorL;
    vector<int> subVectorR;
    int mid = vec.size()/2;
    subVectorL.assign(vec.begin(),vec.begin()+mid);
    subVectorR.assign(vec.begin()+mid,vec.end());
    //左
    mergeSort(subVectorL);
    //右
     mergeSort(subVectorR);
    //合二为一
    mergeTwoVector(subVectorL,subVectorR,vec);

}

int main(){
    vector<int> input{2,1,3432,12,3,35,6,57,23,465};
    for(auto k:input){
        cout<<k<<",";

    }
    cout<<endl;
    mergeSort(input);
    cout<<"after sort"<<endl;
    for(auto k:input){
        cout<<k<<",";

    }
    cout<<endl;
}

链表的归并排序

对于链表的归并排序不像数组，我们可以直接定位到一个数组的中间。所以解决链表定位到中间位置也就解决了这个问题

如上图所示，记录了一次循环后把链表分成了两部分，两部分的头节点分别是head和slow。然后递归调用即可，代码如下

#include <iostream>
#include <vector>
using namespace std;

//单链表的排序算法
//归并排序
struct ListNode
{
    /* data */
    ListNode* next;
    int val;
    ListNode(int val):val(val),next(NULL){}
};
bool myCompare(int a,int b){
    return a>b;
}
//合并
ListNode* merge(ListNode* left,ListNode *right,bool (*compare)(int,int)){
    ListNode* output = new ListNode(0);
    ListNode* cur = output;
    while (left&&right)
    {
        /* code */
        if(compare(left->val,right->val)){
            cur->next = left;
            cur=cur->next;
            left=left->next;
        }else
        {
            /* code */
            cur->next = right;
            cur=cur->next;
            right=right->next;
        }
        
    }
    while (left)
    {
        /* code */
        cur->next = left;
        cur=cur->next;
        left=left->next;
    }
    while (right)
    {
        /* code */
        cur->next = right;
        cur=cur->next;
        right=right->next;
    }
    return output->next;
    
}
ListNode* sort_list(ListNode* head,bool (*compare)(int,int)){
    if(NULL == head->next){
        return head;
    }
    ListNode* slow = head; //慢指针
    ListNode* fast = head;//快指针
    ListNode* sign = NULL;
    //分治
    while (fast&&fast->next)
    {
        /* code */
        sign = slow;
        slow = slow->next;
        fast = fast->next->next;
    }
   
    sign->next = NULL;//从慢指针的位置打断
    auto left = sort_list(head,compare);
    auto right = sort_list(slow,compare);
    return merge(left,right,compare);

}


int main()
{
  ListNode * a = new ListNode(10);
  ListNode * b = new ListNode(12);
  ListNode * c = new ListNode(1);
  ListNode * d = new ListNode(4);
  ListNode * e = new ListNode(30);
  a->next = b;
  b->next = c;
  c->next = d;
  d->next = e;
  //
  auto head = a;
  cout<<"before sort"<<endl;
  while (a->next)
  {
      /* code */
      cout<<a->val<<" ";
      a=a->next;
  }
  cout<<a->val<<endl;
  cout<<"after sort"<<endl;
  head = sort_list(head,myCompare);
  while (head->next)
  {
        /* code */
    cout<<head->val<<" ";
    head=head->next;
  }
  cout<<head->val<<endl;
    
}