归并排序(merge sort)

  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;
}