美文网首页
排序算法之归并排序

排序算法之归并排序

作者: 风之旅人c | 来源:发表于2020-03-01 11:03 被阅读0次

    归并排序(Merge Sort)

    归并排序是利用归并的思想实现排序的方式,该算法采用的是经典的分治算法

    归并排序过程

    • 将n个元素从中间切开,分成两部分。(左边可能比右边多1个数)
    • 将步骤1分成的两部分,再分别进行递归分解。直到所有部分的元素个数都为1。
    • 从最底层开始逐步合并两个排好序的数列。
    归并排序过程

    归并排序动图

    归并排序过程

    归并排序代码(递归)

    #include <set>
    #include <map>
    #include <cmath>
    #include <queue>
    #include <string>
    #include <vector>
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    int a[10] = {33, 12, 15, 1, 5, 9, 48, 4, 13, 19};
    
    void mergeArray(int *a, int first, int mid, int end, int *temp)
    {
        int i = first, j = mid + 1;
        int m = mid, n = end;
        int k = 0;
        while(i <= m && j <= n)
        {
            if(a[i] <= a[j]) temp[k++] = a[i++];
            else temp[k++] = a[j++];
        }
        while(i <= m) temp[k++] = a[i++];
        while(j <= n) temp[k++] = a[j++];
        for(int l=0; l<k; ++l) a[first + l] = temp[l];
    }
    
    void mergeSort(int *a, int first, int end, int *temp)
    {
        if(first < end)
        {
            int mid = (first + end) / 2;
            mergeSort(a, first, mid, temp);
            mergeSort(a, mid + 1, end, temp);
            mergeArray(a, first, mid, end, temp);
        }
    }
    
    void sort(int *b)
    {
        int temp[10];
        mergeSort(b, 0, 9, temp);
    }
    
    
    int main()
    {
        for(int i=0; i<10; ++i) cout<<a[i]<<" ";
        cout<<endl;
        
        sort(a);
        
        for(int i=0; i<10; ++i) cout<<a[i]<<" ";
        cout<<endl;
    }
    

    归并排序复杂度

    时间复杂度:O(nlogn)
    空间复杂度:O(n)

    相关文章

      网友评论

          本文标题:排序算法之归并排序

          本文链接:https://www.haomeiwen.com/subject/lootkhtx.html