归并排序

当两组数据已经有序，我们可以通过以下方式让两组数据快速排序。

依次从两组数据中取前面最小的元素放到新的数组中，然后再把新数组中有序的数据拷贝到原数组，完成排序。这就是归并思想。

代码实现

#include<iostream>
using namespace std;

void mergeAdd(int* arr,int left,int mid,int right)
{
    int temp[64] = { 0 };
    int i = left;//指向左边数组最小的元素位置
    int j = mid;//指向右边数最小的元素位置
    int k = 0;//临时数组下标

    while (i < mid && j <= right)
    {
        if (arr[i] < arr[j])
        {
            temp[k++] = arr[i++];
        }
        else
        {
            temp[k++] = arr[j++];
        }
    }
    while(i< mid)
    {
        temp[k++] = arr[i++];
    }
    while (j <= right)
    {
        temp[k++] = arr[j++];
    }
    //把temp中内容拷贝到
    memcpy(arr + left, temp+left, sizeof(int) * (right - left + 1));
    
}

void print(int* arr,int len)
{
    for (int i = 0; i < len; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
}
int main(void)
{
    int arr[] = { 1,3,5,7,2,4,6,8 };
    int len = sizeof(arr) / sizeof(arr[0]);
    int mid = len / 2;
    mergeAdd(arr, 0,mid, len - 1);
    print(arr, len);
    return 0;
}

当数据无序的时候，只用归并思想就无法实现排序了。

依靠这种思想，引出归并排序方法。

下面是一组待排序的数组。

以中间为界，分为两个数组。

再进行细分

再分

利用上面的归并思想将两个数组分别有序

最后合并到一起。

代码实现(分治法+归并思想)

#include<iostream>
using namespace std;

//归并法，将两个有序的数组合并到一起
void mergeAdd(int* arr,int left,int mid,int right,int* temp)
{

    int i = left;//指向左边数组最小的元素位置
    int j = mid;//指向右边数最小的元素位置
    int k = left;//临时数组下标

    while (i < mid && j <= right)
    {
        if (arr[i] < arr[j])
        {
            temp[k++] = arr[i++];
        }
        else
        {
            temp[k++] = arr[j++];
        }
    }
    while(i< mid)
    {
        temp[k++] = arr[i++];
    }
    while (j <= right)
    {
        temp[k++] = arr[j++];
    }
    //排好序的存到原来的位置——分块排序时，对应位置的元素，分治归并后还放在对应的位置。
    memcpy(arr + left, temp+left, sizeof(int) * (right - left + 1));
    
}

void print(int* arr,int len)
{
    for (int i = 0; i < len; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
}

void mergeSort(int* arr,int left,int right,int* temp)
{
    int mid = 0;
    if (left < right)
    {
        mid = left + (right - left) / 2;//找中间值
        mergeSort(arr, left, mid, temp);
        mergeSort(arr, mid + 1, right, temp);
        mergeAdd(arr, left,mid+1, right, temp);//mid在整合的时候算在右边那半
    }
}
int main(void)
{
    int arr[] = { 3,1,4,5,5,4,1,3};
    int len = sizeof(arr) / sizeof(arr[0]);
    int mid = len / 2;
    int* temp = new int[len];
    mergeSort(arr, 0, len - 1, temp);
    mergeAdd(arr, 0,mid, len - 1,temp);
    print(arr, len);
    return 0;
}