快速排序

归并排序

归并排序的介绍

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

归并排序 ——-> 分治

步骤

  1. 确定分界点
    • mid = (i+r)/2
  2. 递归排序
  3. 归并 —- 合二为一
确定分界点
  • 分界点可以取任意值|中间值
对分开的值进行两边的递归排序

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

主要步骤

  1. 分别确定两指针从两端的数据头开始
1
int k = 0, i = l, j = mid + 1;
  1. 逐个取出数据后进行大小判断，再先后为temp赋值，temp为临时变量存储合二为一的数据
  2. 不断重复操作
1
2
3
4
5
6
7
while (i <= mid && j <= r) {  
    if (q[i] <= q[j]) {  
        temp[k++] = q[i++];  
    } else {  
        temp[k++] = q[j++];  
    }  
}
  1. 处理特殊情况左右两边数据大小不一致
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. 再将临时变量数组里面的数据转存到初始数组中
1
2
3
for (i = l, j = 0; i <= r; i++, j++) {  
    q[i] = temp[j];  
}

代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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];  
    }  
}