归并排序算法(merge_Sort)

归并排序算法(Merge_Sort )_C++实现

一. 介绍:

归并排序(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 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!