归并排序 - 简书

归并排序

废话不多说先上代码

void mergeSort(int arr[], int start, int end) {
    if(start >= end)
        return;

    int middle = start + ((end - start) >> 1);

    mergeSort(arr, start, middle);
    mergeSort(arr, middle + 1, end);

    _merge(arr, start, middle, middle + 1, end);

    return;
}

void _merge(int arr[], int start1, int end1, int start2, int end2) {
    int temp[end2 - start1 + 1];
    int index = 0;
    int s1 = start1;
    int s2 = start2;

    while(s1 <= end1 && s2 <= end2) {
        if (arr[s1] < arr[s2])
        {
            temp[index++] = arr[s1++];
        } else {
            temp[index++] = arr[s2++];
        }
    }

    while(s1 <= end1)
        temp[index++] = arr[s1++];
    
    while(s2 <= end2)
        temp[index++] = arr[s2++];

    for (int i = 0; i <= end2 - start1; ++i)
    {
        arr[start1 + i] = temp[i];
    }

    return;
}
//代码看着比较长，没有特别的东西

时间复杂度

O(n * log n) 这个时间复杂度不会变化，无论是完全逆序还是已经有序

空间复杂度

O(n) 不是原地排序

稳定排序

是稳定排序

算法核心思想

最经典的分而治之的思想

图片.png

将待排序数组从中间分为两个待排序数组。
对两个数组分别排序，再将两个有序数组合并。

一步一步实现归并排序

分

终止条件
数组只有一个元素就不可再分解。

void mergeSort(int arr[], int start, int end) {
    if(start >= end)
        return;
}

拆分数组

void mergeSort(int arr[], int start, int end) {
    if(start >= end)
        return;
    //计算中间元素
    int middle = start + ((end - start) >> 1);
    //对拆分后的数组再次进行拆分
    mergeSort(arr, start, middle);
    mergeSort(arr, middle + 1, end);
}

执行合并
数组拆分到最小单位后进行合并

void mergeSort(int arr[], int start, int end) {
    if(start >= end)
        return;
    //计算中间元素
    int middle = start + ((end - start) >> 1);
    //对拆分后的数组再次进行拆分
    mergeSort(arr, start, middle);
    mergeSort(arr, middle + 1, end);
    //合并函数
    _merge(arr, start, middle, middle + 1, end);
}

治

合并两个有序数组

void mergeSort(int arr[], int start, int end) {
    if(start >= end)
        return;
    //计算中间元素
    int middle = start + ((end - start) >> 1);
    //对拆分后的数组再次进行拆分
    mergeSort(arr, start, middle);
    mergeSort(arr, middle + 1, end);
    //合并函数
    _merge(arr, start, middle, middle + 1, end);
}

//合并函数 
//start1、end1 是第一个数组的起始下标
//start2、end2 是第二个数组的起始下标
void _merge(int arr[], int start1, int end1, int start2, int end2) {
    //申请一个临时数组，存储合并的元素
    int temp[end2 - start1 + 1];
    int index = 0;
    //用来表示要比较的元素
    int s1 = start1;
    int s2 = start2;

    //合并两个有序数组
    while(s1 <= end1 && s2 <= end2) {
        if(arr[s1] < arr[s2]) {
            temp[index++] = arr[s1++];
        } else {
            temp[index++] = arr[s2++];
        }
    }
    
    //将剩下的元素添加到临时数组
    while(s1 <= end1)
        temp[index++] = arr[s1++];
    while(s2 <= end2)
        temp[index++] = arr[s2++];
    
    //将临时数组中的变量赋值给原数组
    for(int i = 0; i <= end2 - start1; ++i) {
        arr[i + start1] = temp[i];
    }

    return;
}
//归并排序结束

归并排序结束了

应该还是比较好理解，就是代码比较复杂，小心点别写错了就可以。

都看到这里了，点个赞再走啊~

最后编辑于：2020.06.07 18:42:38