[每日算法]归并排序

题目描述

利用归并排序算法将读入的 N 个数从小到大排序后输出。

快速排序是信息学竞赛的必备算法之一。对于快速排序不是很了解的同学可以自行上网查询相关资料，掌握后独立完成。（C++ 选手请不要试图使用 STL，虽然你可以使用 sort 一遍过，但是你并没有掌握快速排序算法的精髓。）

输入格式

第 1 行为一个正整数 N，第 2 行包含 N 个空格隔开的正整数 a_i，为你需要进行排序的数，数据保证了a_i不超过 10^9。

输出格式

将给定的 N 个数从小到大输出，数之间空格隔开，行末换行且无空格。

输入输出样例

样例#1	输出#1
5 4 2 4 5 1	1 2 4 4 5

说明/提示

对于20% 的数据，有 N≤ 10^3；

对于 100% 的数据，有 N≤10^5

题解

归并排序是一种稳定的排序算法，平均时间复杂度为O(n log n)。

一般来说归并排序分为3个过程来完成：

1.将数列划分为两个部分；

2.递归地分别对两个子序列进行归并排序；

3.合并两个子序列

归并排序的原理图为：

源代码

#include <iostream>
using namespace std;

//合并两个有序的序列
void merge(int* numbers, int start, int mid, int end)
{
    int i, j, k, n1, n2;
    //n1为左边元素的个数，n2为右边元素的个数
    n1 = mid - start + 1;
    n2 = end - mid;
    int* left = new int[n1], * right = new int[n2];
    //将原始数组拆分成左右两个部分
    for (i = 0; i < n1; i++) // 将numbers的左边元素依次放入left数组
        left[i] = numbers[start + i];
    for (j = 0; j < n2; j++) // 将numbers的右边元素依次放入right数组
        right[j] = numbers[mid + j + 1];
    i = 0;
    j = 0;
    k = start;
    //把两个有序数组进行合并
    while (i < n1 && j < n2)
    { //两边都有数据时，每个数组使用一个指针指向第一个元素，将两个元素进行比较，将小的放到合并后的数组中，并且指针后移
        if (left[i] <= right[j])
        {
            numbers[k++] = left[i++];
        }
        else
        {
            numbers[k++] = right[j++];
        }
    }
    while (i < n1)
    { //如果左边有剩余元素，将元素依次加入结果数组
        numbers[k++] = left[i++];
    }
    while (j < n2)
    { //如果右边有剩余元素，将元素依次加入结果数组
        numbers[k++] = right[j++];
    }
    //释放创建的空间
    delete[] left;
    delete[] right;
}

//归并排序
void mergeSort(int* numbers, int start, int end)
{
    int mid;
    //start>=end时，即拆分成了每个数组只有一个元素，为递归出口
    if (start >= end) return;
    mid = (start + end) / 2;
    //使用递归的方法依次拆分，拆到每个数组只有一个元素为止
    mergeSort(numbers, start, mid);
    mergeSort(numbers, mid + 1, end);
    //执行拆分与合并排序的操作
    merge(numbers, start, mid, end);
}

int main()
{
    int n, i, number;
    cin >> n;    //获取正整数的个数n
    int* numbers = new int[n];
    //将正整数输入到数组中
    for (i = 0;i < n;i++)
    {
        cin >> number;
        numbers[i] = number;
    }

    //进行快速排序
    mergeSort(numbers, 0, n - 1);

    //将排好序后的数输出
    for (i = 0;i < n;i++)
    {
        cout << numbers[i] << " ";
    }
}