排序算法之归并排序

归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。代价是需要额外的内存空间。若将两个有序表合并成一个有序表，称为2-路归并。该算法的时间复杂度为 O(n log n)。

归并排序算法的原理如下：

1. 把长度为n的输入序列分成两个长度为n/2的子序列；

2. 对这两个子序列分别采用归并排序；

3. 将两个排序好的子序列合并成一个最终的排序序列。

归并排序代码实现

// 归并排序函数，arr为待排序数组，start为子数组的起始索引，end为子数组的结束索引，temp为临时数组用于合并
void MergeSort(int arr[], int start, int end, int * temp) {
    if (start >= end) {
        // 如果子数组只有一个元素或为空，不需要排序
        return;
    }
    int mid = (start + end) / 2;
    // 分别对左右两半进行递归排序
    MergeSort(arr, start, mid, temp);
    MergeSort(arr, mid + 1, end, temp);

    // 合并两个有序序列
    int length = 0; // 辅助空间元素计数器
    int i_start = start; // 左半部分的起始索引
    int i_end = mid;     // 左半部分的结束索引
    int j_start = mid + 1; // 右半部分的起始索引
    int j_end = end;     // 右半部分的结束索引
    while (i_start <= i_end && j_start <= j_end) {
        // 比较左右两半部分的元素，将较小的元素放入temp数组中
        if (arr[i_start] < arr[j_start]) {
            temp[length++] = arr[i_start++];
        } else {
            temp[length++] = arr[j_start++];
        }
    }
    // 将左半部分剩余的元素复制到temp数组中
    while (i_start <= i_end) {
        temp[length++] = arr[i_start++];
    }
    // 将右半部分剩余的元素复制到temp数组中
    while (j_start <= j_end) {
        temp[length++] = arr[j_start++];
    }
    // 将temp数组中的元素复制回原数组，完成合并
    for (int i = 0; i < length; i++) {
        arr[start + i] = temp[i];
    }
}