C4.06 分治算法

课堂内容：分治策略

• 归并排序

• 参考代码

#include<bits/stdc++.h> 
using namespace std;  
// 定义两个全局数组 a 和 b，以及一个全局变量 n  
int a[1005], b[1005], n;  
// Merge 函数，用于合并两个已排序的子数组  
void Merge(int L, int R, int mid) {
	// i 和 j 分别指向两个子数组的起始位置，k 用于指向临时数组 b 的当前位置  
    int i = L, j = mid + 1, k = 1; 
  
    // 合并操作，将元素依次放入临时数组 b 中  
    while (i <= mid && j <= R) {  
        if (a[i] > a[j])  // 如果左子数组的元素大于右子数组的元素  
            b[k++] = a[i++];  // 将左子数组的元素放入 b，并移动左子数组的指针  
        else  
            b[k++] = a[j++];  // 否则将右子数组的元素放入 b，并移动右子数组的指针  
    }  
  
    // 如果左子数组还有剩余元素，将其全部放入 b  
    while (i <= mid)  
        b[k++] = a[i++];  
  
    // 如果右子数组还有剩余元素，将其全部放入 b  
    while (j <= R)  
        b[k++] = a[j++];  
  
    // 将临时数组 b 的元素复制回原数组 a  
    k = 1;  
    for (int i = L; i <= R; i++)  
        a[i] = b[k++];  
}  
  
// Msort 函数，递归地执行归并排序  
void Msort(int L, int R) {  
    // 如果 L 和 R 相等，说明只有一个元素或没有元素，无需排序，直接返回  
    if (L == R) return;  
  
    // 计算中点，将数组分为两部分  
    int mid = (L + R) / 2;  
  
    // 递归地对左半部分和右半部分进行排序  
    Msort(L, mid);  
    Msort(mid + 1, R);  
  
    // 合并已排序的子数组  
    Merge(L, R, mid);  
}  
  
int main() {  
    // 输入数组的长度  
    cin >> n;  
  
    // 输入数组的元素  
    for (int i = 1; i <= n; i++)  
        cin >> a[i];  
  
    // 调用归并排序函数  
    Msort(1, n);  
  
    // 输出排序后的数组  
    for (int i = 1; i <= n; i++)  
        cout << a[i] << " ";  
  
    return 0;  
}

• 快速排序

• sort()​函数

sort函数用于C++中，对给定区间所有元素进行排序，默认为升序，也可进行降序排序。sort函数包含在头文件为#include<algorithm>的c++标准库中。

sort()函数调用一般形式

sort(start,end,cmp);

// tart 表示要排序数组的起始地址；对于数组来说就是数组的首地址，一般写上数组名就可以，因为数组名是一个指针常量。

// end 表示数组结束地址的下一位；即首地址加上数组的长度n（代表尾地址的下一地址）。

// cmp 用于规定排序的方法，可不填，默认升序。

• sort()函数的cmp

sort函数没有第三个参数，实现的是从小到大（升序）排列。

较为简单的排序条件修改。

bool cmp(int x, int y)
{
	return x  > y; // 降序
}

较为复杂的排序条件自定义。

bool cmp(stu x, stu y)  // 结构类型元素
{
	return x.score  > y.score; // score为结构类型的某个成员
}