Merge-Sort(归并排序)

Merge-Sort(归并排序)

思想

利用分治的思想，具体实现也就是递归，不断的将问题话分为更小的子问题，当子问题中规模为1的时候，认为数组已经有序了，然后再将子问题求得的结果不断的合并。也就是将长度为1的两个数组合并到长度为2的数字，依次合并下去。 合并的过程就是依次比较两个数组，将较小的数复制回原数组，然后移动指针，以此类推。有一个小技巧就是在数组的最后都加一个INT_MAX作为哨兵，就不用判断某个数组是否已经没有元素可以用来比较了。

实现

#include <iostream>

#include <vector>

#include <cmath>

using namespace std;

class Solution {

public:

    //插入排序算法

    void merge_sort(vector<int>& vec, int p, int r) {

        if (p < r) {

            int q = floor((r + p) / 2);

            merge_sort(vec, p, q);    //划分子问题

            merge_sort(vec, q + 1, r);

            merge(vec, p, q, r);      //合并

        }

    }

    void merge(vector<int>& vec, int p, int q, int r) {

        vector<int> vec1(vec.begin() + p, vec.begin() + q + 1);

        vector<int> vec2(vec.begin() + q + 1, vec.begin() + r + 1);

        vec1.push_back(INT_MAX);

        vec2.push_back(INT_MAX);

        int i = 0;

        int j = 0;

        for (int k = p; k <= r; k++) {

            if (vec1[i] < vec2[j]) {

                vec[k] = vec1[i];

                i++;

            } else {

                vec[k] = vec2[j];

                j++;

            }

        }

    }

};

int main() {

    int arr[] = {1, 2, 3, 4, 1, 3, 4, 2, 2, 3};

    vector<int> vec(arr, arr+10);

    Solution* solution = new Solution();

    solution->merge_sort(vec, 0, 9);

    for (int i = 0; i < vec.size(); i++) {

        cout << vec[i] << " ";

    }

    cout << endl;

    return 0;

}