基本排序算法---归并排序

1、为什么要引入归并排序

在之前介绍的排序算法中，冒泡排序和选择排序的时间复杂度过高（O(n2)）原因是因为在冒泡排序时，一轮下来进行了多次比较但是只排好了一个最大数放在尾部，在选择排序中，同样也是进行多次比较，选最小的放在了头部，这期间浪费了很多时间，多余的比较做了无用功。
至于插入排序，解决的是对比较次数进行了优化，不再进行不必要的比较。插入排序的思想类似于摸扑克牌，自左向右遍历，当遍历到新元素时，我们向前去比较（此时前面已经是有序序列了），找到第一个比它小的，就放于此处，因为算法设计的巧妙性，我们可以降低时间复杂度，在整体都有序的情况下时间复杂度最低为O(n),在整个序列都逆序的时候时间复杂度最高为O（n2)。
为了将比较次数降到最低，我们将比较范围进行了划分，小范围排序后再合并，引入了归并排序。

//插入排序
for (size_t i = 1; i < nums.size(); i++)
    {
        for (int j = i; j > 0 && nums[j] < nums[j - 1]; j--)//如果不满足条件，则不执行循环
        {
            swap(nums,j,j-1);
        }
    }

2、归并排序的思想

归并排序是一种分治思想，首先将大问题划分为多个小问题，也就是将长序列经过多次划分成单个元素的序列，8变4、4变2、2变1，在1个元素时天然有序，此时不再划分而是进行合并，也就是先分后治的套路。

void mergesort(vector<int>&nums, int l, int r, vector<int>& temp)
{
    if (l<r)
    {
        int mid = l + (r - l) / 2;
        mergesort(nums, l, mid, temp);
        mergesort(nums, mid + 1, r, temp);
        merge(nums,l,r, temp);
    }
}

在两部分合并时候，令指针i指向左侧的最左边，j指向右侧的最左边，因为两个序列在各自内部已经有序，所以i与j指向的元素肯定有一个是全局最小的，通过比较将其放到temp数组（为什么要引入额外辅助数组？）中，然后指针后移，继续比较，直到有一个序列为空时止。在谁小移谁后，如果有一个序列还没比较完即i或j没有到尾部，则将剩余的元素直接拷贝到temp数组中。这样就完成了一轮[L,R]的排序。多次递归，将得到整个有序的序列。

void merge(vector<int>&nums, int l, int r, vector<int>& temp)
{
    int mid = l + (r - l) / 2;
    int i = l, j = mid + 1;
    int index = l;
    temp.assign(nums.begin(), nums.end());
    while (i<=mid&&j<=r)
    {
        if (nums[i] > nums[j])
        {
            temp[index++] = nums[j++];
        }
        else
            temp[index++] = nums[i++];
    }
    while (i <= mid)
    {
        temp[index++] = nums[i++];
    }
    while (j <= r)
    {
        temp[index++] = nums[j++];
    }   
    for (size_t i = 0; i < nums.size(); i++)
    {
        cout << temp[i]<<" ";
    }
    for (size_t i = l; i <= r; i++)
    {
        nums[i] = temp[i];      
    }
}

[注意]：引入temp数组的意义
我们在merge时，需要一个辅助数组来临时保存中间变量的值，如下图所示，先排1、5再排1、5、3，以此类推，因为涉及交换，如果无辅助数组，交换值的时候会对nums数组进行替换，影响下一轮排序。

image.png

3、归并排序所有代码

#include "stdafx.h"
#include<vector>
#include<iostream>
using namespace std;
//合并算法
void merge(vector<int>&nums, int l, int r, vector<int>& temp)
{
    int mid = l + (r - l) / 2;
    int i = l, j = mid + 1;
    int index = l;
    while (i<=mid&&j<=r)
    {
        if (nums[i] > nums[j])
        {
            temp[index++] = nums[j++];
        }
        else
            temp[index++] = nums[i++];
    }
    while (i <= mid)
    {
        temp[index++] = nums[i++];
    }
    while (j <= r)
    {
        temp[index++] = nums[j++];
    }   
    for (size_t i = 0; i < nums.size(); i++)
    {
        cout << temp[i]<<" ";
    }
    cout << endl;
    for (size_t i = l; i <= r; i++)
    {
        nums[i] = temp[i];      
    }
}
//归并排序
void mergesort(vector<int>&nums, int l, int r, vector<int>& temp)
{
    if (l<r)
    {
        int mid = l + (r - l) / 2;
        mergesort(nums, l, mid, temp);
        mergesort(nums, mid + 1, r, temp);
        merge(nums,l,r, temp);
    }
}
int main()
{
    vector<int>nums = { 1,5,3,6,9,8,7,4,55,66};
    vector<int>temp(nums.size());
    cout << "排序前数组"<<endl;

    for (size_t i = 0; i <= nums.size() - 1; i++)
    {
        cout << nums[i] << " ";
    }
    cout << endl;
    cout << "----------temp数组------------"<<endl;
    mergesort(nums, 0, nums.size() - 1, temp);
    getchar();
    return 0;
}

基本排序算法---归并排序