归并排序(merge sort)

组别:提高级
难度:5

归并排序是基于分治算法的一种排序,我们把一个问题分解成子问题,每个子问题再分别解决,最后再把子问题的解合并成最终结果。

如下图数列{6,5,12,10,9,1},首先将数列分成两分{6,5,12}和{10,9,1},再把这俩个子数列继续分解成{6},{5,12},{10},{9,1} ,当就子数列就剩两个元素时比较大小,现把子数列逐级合并成一个有序数列。

Merge Sort (With Code)

代码实现:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
/**************************************************************** 
 * Description: 用C++实现归并算法,Merge sort in C++
 * Author: Alex Li
 * Date: 2022-02-10 19:55:32
 * LastEditTime: 2024-12-02 17:50:17
****************************************************************/
#include <iostream>
#include <vector>
using namespace std;
int arr[100];
// 合并两个子数组Left_arr和Right_arr到主数组中
void merge(int arr[], int left, int middle, int right) {
    // 确定左右子数组的大小
    int left_size = middle - left + 1;
    int right_size = right - middle;

    // 临时数组用于存储左右子数组的值
    vector<int> left_array(left_size);
    vector<int> right_array(right_size);

    // 将数据从主数组复制到子数组中
    for (int i = 0; i < left_size; i++) {
        left_array[i] = arr[left + i];
    }
    for (int j = 0; j < right_size; j++) {
        right_array[j] = arr[middle + 1 + j];
    }

    // 维护子数组和主数组的索引
    int left_index = 0, right_index = 0;
    int merged_index = left;

    // 按顺序将两个子数组中的元素合并到主数组中
    while (left_index < left_size && right_index < right_size) {
        if (left_array[left_index] <= right_array[right_index]) {
            arr[merged_index] = left_array[left_index];
            left_index++;
        } else {
            arr[merged_index] = right_array[right_index];
            right_index++;
        }
        merged_index++;
    }

    // 将剩余的元素合并到主数组中
    while (left_index < left_size) {
        arr[merged_index] = left_array[left_index];
        left_index++;
        merged_index++;
    }

    while (right_index < right_size) {
        arr[merged_index] = right_array[right_index];
        right_index++;
        merged_index++;
    }
}

// 递归地将主数组分解成两个子数组,再合并子数组
void mergeSort(int arr[], int begin, int end) {
    if (begin < end) {
        // middle是把主数组分成两个子数组的分界点
        int middle = begin + (end - begin) / 2;

        // 对左半部分进行排序
        mergeSort(arr, begin, middle);
        // 对右半部分进行排序
        mergeSort(arr, middle + 1, end);

        // 合并已经排好序的子数组
        merge(arr, begin, middle, end);
    }
}

// 打印排好序的数组
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// 主程序
int main() {
    int size;
    cout << "请输入数组大小: ";
    cin >> size;
    

    cout << "请输入 " << size << " 个数组元素: ";
    for (int i = 0; i < size; i++) {
        cin >> arr[i];
    }

    mergeSort(arr, 0, size - 1);

    cout << "排好序的数组: " << endl;
    printArray(arr, size);
    return 0;
}

逆序对问题:

要在 Merge Sort 基础上解决逆序对问题,可以通过在合并阶段计算出逆序对的数量。在逆序对问题中,如果在数组中 i < j 但是 arr[i] > arr[j],那么我们就称 (i, j) 是一个逆序对。

下面是一个基于 Merge Sort 的方法,通过在合并的过程中统计逆序对的数量来解决这个问题。

思路:

  • 在每次合并子数组的过程中,如果左子数组的元素大于右子数组的元素,那么这些左子数组的元素与当前右子数组的元素构成逆序对,因为左子数组元素的索引比右子数组元素的索引小。
while (left_index < left_size && right_index < right_size) {
        if (left_array[left_index] <= right_array[right_index]) {
            arr[merged_index] = left_array[left_index];
            left_index++;
        } else {
            // 如果左子数组的当前元素大于右子数组的当前元素,则构成逆序对
            arr[merged_index] = right_array[right_index];
            right_index++;
            // 左子数组中剩余的所有元素都与右子数组当前元素构成逆序对
            reverse_count += (left_size - left_index);
        }
        merged_index++;
    }

瑞士轮 [NOIP2011 普及组] [P1309]

题目背景

在双人对决的竞技性比赛,如乒乓球、羽毛球、国际象棋中,最常见的赛制是淘汰赛和循环赛。前者的特点是比赛场数少,每场都紧张刺激,但偶然性较高。后者的特点是较为公平,偶然性较低,但比赛过程往往十分冗长。

本题中介绍的瑞士轮赛制,因最早使用于1895年在瑞士举办的国际象棋比赛而得名。它可以看作是淘汰赛与循环赛的折中,既保证了比赛的稳定性,又能使赛程不至于过长。

题目描述

2×N名编号为 1∼2N的选手共进行R 轮比赛。每轮比赛开始前,以及所有比赛结束后,都会按照总分从高到低对选手进行一次排名。选手的总分为第一轮开始前的初始分数加上已参加过的所有比赛的得分和。总分相同的,约定编号较小的选手排名靠前。

每轮比赛的对阵安排与该轮比赛开始前的排名有关:第11 名和第22 名、第 33 名和第 44名、……、第2K−12K−1名和第2K2K名、…… 、第2N−12N−1名和第2N2N名,各进行一场比赛。每场比赛胜者得11分,负者得 00分。也就是说除了首轮以外,其它轮比赛的安排均不能事先确定,而是要取决于选手在之前比赛中的表现。

现给定每个选手的初始分数及其实力值,试计算在R 轮比赛过后,排名第QQ 的选手编号是多少。我们假设选手的实力值两两不同,且每场比赛中实力值较高的总能获胜。

输入格式

第一行是三个正整数N,R,QN,R,Q,每两个数之间用一个空格隔开,表示有 2×N2×N名选手、RR 轮比赛,以及我们关心的名次 QQ

第二行是2×N2×N 个非负整数s1,s2,…,s2Ns1​,s2​,…,s2N​,每两个数之间用一个空格隔开,其中sisi​表示编号为ii 的选手的初始分数。 第三行是2×N2×N 个正整数w1,w2,…,w2Nw1​,w2​,…,w2N​,每两个数之间用一个空格隔开,其中 wiwi​ 表示编号为ii 的选手的实力值。

输出格式

一个整数,即RR 轮比赛结束后,排名第QQ 的选手的编号。

输入输出样例

输入 #1复制2 4 2 7 6 6 7 10 5 20 15

输出 #1复制1

说明/提示

【样例解释】

【数据范围】

对于30%30%的数据,1≤N≤1001≤N≤100;

对于50%50%的数据,1≤N≤10,0001≤N≤10,000;

对于100%100%的数据,1≤N≤100,000,1≤R≤50,1≤Q≤2N,0≤s1,s2,…,s2N≤108,1≤w1,w2,…,w2N≤1081≤N≤100,000,1≤R≤50,1≤Q≤2N,0≤s1​,s2​,…,s2N​≤108,1≤w1​,w2​,…,w2N​≤108。

Scroll to Top