归并排序

归并排序的介绍

是一种经典的基于分治策略的排序算法，其核心思想是将一个数组分成两个或多个子数组，对每个子数组进行排序，然后将排序好的子数组合并成一个最终的有序数组。

归并排序 ——-> 分治

步骤

确定分界点
- mid = (i+r)/2
递归排序
归并 —- 合二为一

确定分界点

分界点可以取任意值|中间值

对分开的值进行两边的递归排序

最后可以获得两组排好了的数据，将两组数据合二为一
下面用图示来具体分析过程

主要步骤

分别确定两指针从两端的数据头开始

1	int k = 0, i = l, j = mid + 1;

逐个取出数据后进行大小判断，再先后为temp赋值，temp为临时变量存储合二为一的数据
不断重复操作

while (i <= mid && j <= r) {  
    if (q[i] <= q[j]) {  
        temp[k++] = q[i++];  
    } else {  
        temp[k++] = q[j++];  
    }  
}

处理特殊情况左右两边数据大小不一致

1 2	左子数组：[1, 3, 5] 右子数组：[2, 4, 6, 7]

代码表示

1
2
3

while (i <= mid) {  
        temp[k++] = q[i++];  
    }

1 2	左子数组：[1, 4, 7, 8] 右子数组：[2, 3]

代码表示

1
2
3

while (j <= r) {  
        temp[k++] = q[j++];  
    }

再将临时变量数组里面的数据转存到初始数组中

1
2
3

for (i = l, j = 0; i <= r; i++, j++) {  
    q[i] = temp[j];  
}

代码模板

void merge_sort(int q[], int l, int r) {  
    if (l >= r) return;  
    int mid = (l + r) / 2;  
    merge_sort(q, l, mid);  
    merge_sort(q, mid + 1, r);  
    int k = 0, i = l, j = mid + 1;  
    while (i <= mid && j <= r) {  
        if (q[i] <= q[j]) {  
            temp[k++] = q[i++];  
        } else {  
            temp[k++] = q[j++];  
        }  
    }  
    while (i <= mid) {  
        temp[k++] = q[i++];  
    }  
    while (j <= r) {  
        temp[k++] = q[j++];  
    }  
    for (i = l, j = 0; i <= r; i++, j++) {  
        q[i] = temp[j];  
    }  
}