数据结构：归并排序 && 逆序对统计

╰半夏微凉° 2022-05-31 12:53 204阅读 0赞

# 归并排序 #

要注意归并排序需要一个辅助空间，别的直接递归即可

# 代码如下 #

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    
    using namespace std;
    
    
    void merge(int a[], int fir, int mid, int fin, int temp[])
    {
        int i = fir, j = mid + 1;
        int m = mid, n = fin;
        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 h = 0; h <k; h++)
            a[fir + h] = temp[h];
    }
    
    void MergeSort(int a[], int fir, int fin, int temp[])
    {
        if (fir == fin)
            return;
        else
        {
            int mid = (fir + fin) / 2;
            MergeSort(a, fir, mid, temp);
            MergeSort(a, mid + 1, fin, temp);
            merge(a, fir, mid, fin, temp);
        }
    }
    
    void print(int a[], int SIZE)
    {
        for (int i = 0; i < SIZE; i++)
            cout << a[i] << "   ";
        cout << endl;
    }
    
    void main()
    {
        int a[10] = { 9,8,7,6,5,4,3,2,1,11 };
        int b[10] = { 0 };
        cout << "排序前：" << endl;
        print(a, 10);
        print(b, 10);
        MergeSort(a, 0, 9, b);
        cout << "排序后：" << endl;
        print(a, 10);
        print(b, 10);
    
        system("pause");
    }

逆序对参考这个博客[剑指offer读书笔记：第五章，优化时间和空间效率][offer]

[offer]: https://blog.csdn.net/jackzhang_123/article/details/79501029