JZTXT

排序

发布时间 2023-12-06 03:18:26作者: vLiion

题目链接

912. 排序数组

1. 快速排序

2. 归并排序

思路

算法的思想是分治

一句话总结：将排序的任务先递归分解成一个一个小的任务，将小的任务完成，再用小任务完成大任务，逐步完成最终得到整个排序的任务。

一张图片直观表示分治的思路：

img

题解思路

  1. 上图中的每一层如何实现？

    通过递归的方式。将数组递归处理，处理 q[l, mid] 和 q[mid+1, r] 来实现

  2. “治”中，如何实现两个子数组的有序合并？

    【两个有序数组的合并】问题可以通过双指针算法求解

image-20231206030419571

题解模板

  1. 通过函数调用递归来实现，因此参数传入为 int q[], int l, int r
  2. 【递归结束条件】当小任务中有 0 个或者 1 个数时，返回
  3. 【分】递归左边和右边
  4. 【治】两个有序数组的合并
    • 设置辅助数组 tmp
    • 界定退出循环为：两个子数组有一个遍历完成
    • 将未遍历完的数据追加到尾部
    • 将 tmp 数组内容放回 q 中

题解代码

void merge_sort(int q[], int l, int r) {
    if (l >= r) return;
    
    int mid = l + r >> 1;
    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]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    }
    
    while (i <= mid) tmp[k++] = q[i++];
    while (j <= r) tmp[k++] = q[j++];
    
    for (int i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
    
}