0.x 9.归并排序

dddd数据结构课本

• Author：李英民 | Henry
• E-mail: li_yingmin@outlookdotcom
• $Beijing~~U~of~Posts~and~Telecom$$(BUPT~)$
• Home: https://liyingmin.wixsite.com/henry

• 快速了解我: About Me

• 转载请保留上述引用内容，谢谢配合！

自顶向下

#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <algorithm>
#include <typeinfo>
#include <numeric>
#include <memory>
#include <stdexcept>
#include <fstream> 
#include <sstream>
using namespace std;
//win+<-/-> 切换窗口位置
//ctrl+win+<-/->切换桌面 
//ctrl+alt+上/下 改变显示器方向 
template<typename  T>
void __merge(T arr[], int l, int mid, int r){
    //* VS不支持动态长度数组, 即不能使用 T aux[r-l]的方式申请aux的空间
    //* 使用VS的同学, 请使用new的方式申请aux空间
    //* 使用new申请空间, 不要忘了在__merge函数的最后, delete掉申请的空间:)
    //T aux[r-l];
    T *aux = new T[r-l];
    for( int i = l ; i != r; ++i ) //采用C++11的循环风格
        aux[i-l] = arr[i];
    // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid
    int i = l, j = mid;
    for( int k = l ; k != r; ++k ){
        if( i == mid ){  // 如果左半部分元素已经全部处理完毕
            arr[k] = aux[j-l]; ++j;
        }
        else if( j == r ){  // 如果右半部分元素已经全部处理完毕
            arr[k] = aux[i-l]; ++i;
        }
        else if( aux[i-l] <= aux[j-l] ) {  // 左半部分所指元素 <= 右半部分所指元素,稳定排序 
            arr[k] = aux[i-l]; ++i;
        }
        else{  // 左半部分所指元素 > 右半部分所指元素
            arr[k] = aux[j-l]; ++j;
        }
    }
    delete[] aux;
}
// 递归使用归并排序,对arr[l...r)的范围进行排序
template<typename T>
void __mergeSort(T arr[], int l, int r){
    int mid = l + (r-l)/2;//注意，这里处理得很细腻了
    if( l == mid )//注意，当r-l<=20，可以使用插入排序更快
        return;
    __mergeSort(arr, l, mid);
    __mergeSort(arr, mid, r);
    if(arr[mid - 1] > arr[mid])
        __merge(arr, l, mid, r);
}
template<typename T>
void mergeSort(T arr[], int n){
    __mergeSort( arr , 0 , n );
}
int main() {
    int a[20] = {10,9,8,7,6,5,4,3,2,1,10,9,8,7,6,5,4,3,2,1};
    mergeSort(a,20);
    for( int i = 0 ; i < 20 ; i ++ )
        cout<<a[i]<<ends;
    cout<<endl;
    return 0;
}

自底向上

template<typename  T>
void __merge(T arr[], int l, int mid, int r){  //只有1个也可以merge 
    //* VS不支持动态长度数组, 即不能使用 T aux[r-l]的方式申请aux的空间
    //* 使用VS的同学, 请使用new的方式申请aux空间
    //* 使用new申请空间, 不要忘了在__merge函数的最后, delete掉申请的空间:)
    //T aux[r-l];
    T *aux = new T[r-l];
    for( int i = l ; i != r; ++i )
        aux[i-l] = arr[i];
    // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid
    int i = l, j = mid;
    for( int k = l ; k != r; ++k ){
        if( i == mid ){  // 如果左半部分元素已经全部处理完毕
            arr[k] = aux[j-l]; ++j;
        }
        else if( j == r ){  // 如果右半部分元素已经全部处理完毕
            arr[k] = aux[i-l]; ++i;
        }
        else if( aux[i-l] <= aux[j-l] ) {  // 左半部分所指元素 <= 右半部分所指元素,稳定排序 
            arr[k] = aux[i-l]; ++i;
        }
        else{  // 左半部分所指元素 > 右半部分所指元素
            arr[k] = aux[j-l]; ++j;
        }
    }
    delete[] aux;
}
template<typename T>
void mergeSort(T arr[], int n){
    for(int sz = 1; sz < n; sz+=sz) //sz<n即可，不必<=
        for(int i = 0; i +sz < n; i += sz + sz)//sz+i<n即可，不必<=
            __merge(arr, i, i+sz, min(i +sz + sz, n));      
}
int main() {
    int a[20] = {10,9,8,7,6,5,4,3,2,1,10,9,8,7,6,5,4,3,2,1};
    mergeSort(a,20);
    for( int i = 0 ; i < 20 ; i ++ )
        cout<<a[i]<<ends;
    cout<<endl;
    return 0;
}