归并排序算法(Merge_Sort )

一、介绍：

归并排序（Merge_Sort）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

• 中文名

  归并排序

• 外文名

  Mergesort

• 稳定性

  稳定

• 时间复杂度

  O(nlogn)

• 空间复杂度

  O（n)

• 发明者

  约翰·冯·诺伊曼

二、逻辑:

具体逻辑：分为两个步骤

1.切分操作：将一组数组切分成两部分，运用分治思想(具体实现：递归)，将切分的两部分分别进行切分(再次将每部分一分为二)，以此类推，直到数组中的元素不能再进行切分(递归到底，直到切分到元素自身”l>=r”)。

2.归并操作：然后将元素进行比较再依次归并。

例子：数组{5，3，2，1，7，4，8，0}进行排序

切分：

1.将数组分为{5, 3, 2,1}和{,7, 4 ,8, 0}两个数组

2.将{5, 3, 2,1}和{7, 4 ,8, 0}两个数组分别进行切分,分为{5, 3}、{2, 1}、{7, 4}和{8, 0}

3.将5, 3}、{2, 1}、{7, 4}和{8, 0}数组再进行分……

4.递归到{5}(此时不能分)最后

归并

1.将5, 3}、{2, 1}、{7, 4}和{8, 0}数组进行比较，得：{3, 5}、{1, 2}、{4, 7}和{0, 8}

2.将数组3, 5}、{1, 2}和{4, 7}, {0, 8}中元素进行比较并归并成{1, 2, 3, 5}和{0, 4, 7, 8}

3.重复”2”操作，最终排序完成，得出{0, 1, 2, 3, 4, 5, 7, 8}

三、代码实现

#include <iostream>

using namespace std;

// 将arr[l...mid]和arr[mid+1...r]两部分进行归并
template<typename  T> //使用模板
void __merge(T arr[], int l, int mid, int r){


    //* 这里需要使用new申请空间, 不要忘了在__merge函数的最后, delete掉申请的空间:)
    T aux[r-l+1];
    //T *aux = new T[r-l+1];

    for( int i = l ; i <= r; i ++ )
        aux[i-l] = arr[i];

    // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
    int i = l, j = mid+1;
    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){

    if( l >= r )
        return;

    int mid = (l+r)/2; //将数组进行切分
    __mergeSort(arr, l, mid);
    __mergeSort(arr, mid+1, r);
    __merge(arr, l, mid, r);
}

template<typename T>
void mergeSort(T arr[], int n){

    __mergeSort( arr , 0 , n-1 );
}

本作品采用《CC 协议》，转载必须注明作者和本文链接