Merge Sort (归并排序）

刺骨的言语ヽ痛彻心扉 2022-08-08 06:38 79阅读 0赞

归并排序是分治法的例子。

在归并排序中，会递归地把列表一分为2，然后进行排序，最后再合并。

归并排序中，需要使用辅助空间O(n)。

比如，要对3，5，4，9，2进行排序，我们有下图

![Image 1][]

不断地把n/2,然后进行排序和合并，程序如下所列：

<pre name="code" class="java">//
    //  main.cpp
    //  MergeSort
    //
    //  Created by Paul Huang on 15/5/10.
    //  Copyright (c) 2015年 Paul Huang. All rights reserved.
    //
    
    #include <iostream>
    int data[5]={3,5,4,9,2};
    int dataaux[5];
    
    int max(int x, int y)
    {
        if(x > y)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    
    void merge( int low, int mid, int high ){
        int i=low;
        int j=mid+1;
        for(int k=low;k<=high;k++){
            dataaux[k]=data[k]; //复制数组元素到一个新数组
        }
        
        for(int k=low;k<=high;k++){
            if(i>mid) data[k]=dataaux[j++];   //左边（低位）的数组已经全部比较完，并进入比较后的结果数组
            else if (j>high) data[k]=dataaux[i++]; //右边（高位）的数组已经全部比较完，并进入比较后的结果数组
            else if(max(dataaux[i],dataaux[j])) data[k]=dataaux[j++];  //左边和右边的数组进行比较
            else data[k]=dataaux[i++];
        }
        
        
        
        }
    
    void sort(int left, int right)
    {
        if(right<=left) return;
        int mid=left+(right-left)/2;
        sort(left,mid);
        sort(mid+1,right);
        merge(left,mid,right);
     }
    
    
    
    int main(int argc, const char * argv[]) {
        // insert code here...
        std::cout << "Hello, World!\n";
        sort(0,4);
        for(int i=0;i<5;i++){
            std::cout<<data[i]<<std::endl;
        }
    
        return 0;
    }

[Image 1]: