分治思想排序（快速排序、归并排序）

分治：分而治之，即把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并

优点：

1. 降低时间复杂度：分治法可以将大问题分解为小问题，通过解决小问题来有效解决原问题，从而降低算法的时间复杂度
2. 简单易懂：分治算法的思路通常比较直观，编写代码时难度较低
3. 并行处理：由于分解得到的子问题之间是相互独立的，可以同时进行解决，提高了解决问题的效率
4. 容易确定运行时间：分治算法的运行时间通常可以通过分析子问题的数量和每个子问题的复杂度来确定

缺点：

1. 空间需求大：分治法需要额外的空间来存储子问题的解，可能会导致空间复杂度增加
2. 递归开销：分治算法通常采用递归方式实现，这会增加函数调用的开销，尤其是在问题规模较大时，可能会导致系统资源的大量消耗，严重时甚至可能导致程序崩溃
3. 分解和合并的复杂性：虽然子问题的解可以通过合并得到原问题的解，但如果分解和合并的过程过于复杂，可能会使得分解和合并所花费的时间超出暴力解法

1、快速排序

排序一次将数据分割成独立的两部分，其中一份中的所有数据都比另外一份的所有数据都要小，然后对这两部分再次进行该排序，整个排序过程可以使用递归进行来达到整个数据成为有序序列

步骤：

1. 确定分界数据
2. 划分、调整区间
3. 递归划分后的区间

void quick_sort(int q[], int l, int r){
    //递归终止条件
    if (l >= r) return;
    
    int i = l - 1, j = r + 1, x = q[(l + r)/2];
    
    while (i < j){
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    //递归处理
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

2、归并排序

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并

步骤：

1. 确定分界点
2. 递归排序
3. 归并，合二为一

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 (i = l, j = 0; i <= r; i ++, j ++ ){
        q[i] = tmp[j];
    }
}