数据结构-归并排序

原理

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序是一种稳定的排序方法。

图示过程

一分解

image.png

二合并

image.png

代码实现

// 交换 或者赋值排序
//中间数组排序
/**
* 合并两个有序数列
* array[left]~array[mid]为第一组
* array[mid+1]~array[right]为第二组
* temp[]为存放两组比较结果的临时数组
*/
void merge(int arr[], int left, int mid, int right) {
    int temp[right - left + 1];
    int i = left;
    int j = mid + 1;
    int t = 0;
    // 比较左右两部分的元素，哪个小，把那个元素填入temp中
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[t++] = arr[i++];
        }else {
            temp[t++] = arr[j++];
        }
    }
    
    // 上面的循环退出后，把剩余的元素依次填入到temp中
    // 以下两个while只有一个会执行
    while (i <= mid) {
        temp[t++] = arr[i++];
    }
    
    while (j <= right) {
        temp[t++] = arr[j++];
    }
    
    t = 0;
    
    while (left <= right) {
        arr[left++] = temp[t++];
    }
}

void merge_sort_gui(int arr[], int left, int right) {
    if (left == right) {
        return;
    }
    int mid = left + (right - left)/2;
    merge_sort_gui(arr, left, mid); // 递归归并左边元素
    merge_sort_gui(arr, mid + 1, right); // 递归归并右边元素
    merge(arr, left, mid, right);  //再将两个有序数列合并
}

void merge_sort(int arr[], int length) {
    
    merge_sort_gui(arr, 0, length -1);    
}