归并排序

自顶向下的归并排序

Notes:

1. 也就比合并有序链表多了拆分的步骤
2. 写完后可以优化下代码行数

/*
自顶向下的归并排序
*/
#include <iostream>
using namespace std;

void Merge(int* arr1,int len1,int* arr2,int len2){
    int* tmp = new int[len1+len2];
    int i = 0,j = 0,k = 0;
    while( i != len1 && j != len2){
        if(arr1[i] <= arr2[j]){
            tmp[k++] = arr1[i++];
        }
        else{
            tmp[k++] = arr2[j++];
        }
    }
    while(j < len2){
        tmp[k++] = arr2[j++];
    }
    while(i < len1){
        tmp[k++] = arr1[i++];
    }
    for(i = 0;i < k;i++){
        arr1[i] = tmp[i];
    }
    delete []tmp;
    tmp = NULL;
}
void MergeSort(int* arr,int len){
    if(len > 1){
        int* arr1 = arr;
        int arr1_len = len/2;
        int* arr2 = arr + arr1_len;
        int arr2_len = len - arr1_len;
        //分解
        MergeSort(arr1,arr1_len);
        MergeSort(arr2,arr2_len);
        //合并
        Merge(arr1,arr1_len,arr2,arr2_len);
    } 
}

void Print(int* arr,int len){
    for(int i = 0;i < len;i++){
        cout<<arr[i]<<"  ";
    }
    cout<<endl;
}
int main(int argc, char const *argv[])
{
    int arr[8] = {2,4,11,0,1,9,6,7};
    Print(arr,8);
    MergeSort(arr,8);
    Print(arr,8);
    
    return 0;
}

用下标的归并排序算法

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

void Print_(int* arr,int len){
    for(int i = 0;i < len;i++){
        cout<<arr[i]<<"  ";
    }
    cout<<"tmp "<<endl;
}
void Merge(int* arr,int l,int m,int r){
    int tmp_size = r-l+1;
    int* tmp =new int[tmp_size];
    //memcpy(tmp,arr,tmp_size*sizeof(int));
    for(int i = l;i <=r;i++){
        tmp[i-l] = arr[i];
    }
    int i = l,j = m+1;
    for(int k = l;k <= r;k++){  //为啥要写=
        if(i > m){      //左边循环完
            arr[k] = tmp[j-l];
            j++;
        }
        else if(j > r){     //右边循环完
            arr[k] = tmp[i-l];
            i++;
        }
        else if(tmp[i-l] <= tmp[j-l]){
            arr[k] = tmp[i-l];
            i++;
        }
        else{
            arr[k] = tmp[j-l];
            j++;
        }
    }
    //Print_(arr,tmp_size);
    delete []tmp;
    tmp = NULL;
}
void MergeSort(int* arr,int l,int r){
    cout<<"deal with ["<<l<<"---"<<r<<"]"<<endl;
    if(l >= r){
        return ;
    }
    else{
        int m = (r+l)/2;        //(r+l)/2
        MergeSort(arr,l,m);
        MergeSort(arr,m+1,r);
        Merge(arr,l,m,r);
    }
}
void Print(int* arr,int len){
    for(int i = 0;i < len;i++){
        cout<<arr[i]<<"  ";
    }
    cout<<endl;
}
int main(int argc, char const *argv[])
{
    int arr[7] = {55,4,53,2,8,7,0};
    Print(arr,7);
    MergeSort(arr,0,6);
    Print(arr,7);
    return 0;
}

本来想更新到码云上,为啥抽风了。。。。

参考链接：

1. C++实现自顶向下的归并排序算法
2. 玩转算法

自顶向下的归并排序

原文：https://www.cnblogs.com/ziyuemeng/p/12381343.html