算法设计与分析 | 分治算法

算法简介

分治算法是一种将原问题划分为若干个相互独立且结构相同的子问题，递归地解决这些子问题，最后将子问题的解合并得到原问题解的算法思想。

分治算法通常包含三个步骤：

1. 分解（Divide）： 将原问题分解为若干个规模较小、相互独立、结构与原问题相同的子问题。这一步通常是递归的过程。

2. 解决（Conquer）： 递归地解决子问题。如果子问题的规模足够小，就直接求解。

3. 合并（Combine）： 将子问题的解合并成原问题的解。

分治算法需要证明问题具有最优子结构，并且子问题的解可以被合并得到原问题的解。

虽然分治算法通常会增加递归调用的开销，但通过高效地合并子问题的解，可以在某些情况下取得较好的性能。

例子：快速排序

快速排序采用分治思想，其基本过程如下：

1. 选择基准元素： 从待排序的数组中选择一个元素作为基准（pivot）。选择基准的方式可以是随机选择、选择第一个元素、选择最后一个元素等。这个基准元素的选择会影响算法的性能。

2. 分割数组： 将数组中的其他元素与基准元素比较，并将它们分为两个子数组，一个小于基准的子数组，一个大于基准的子数组。这个过程通常被称为“分区”或“分割”。

3. 递归排序： 对两个子数组递归地应用快速排序。即，分别对小于基准的子数组和大于基准的子数组进行快速排序。

4. 合并结果： 将排序好的子数组合并，得到最终的排序数组。

分区过程一般使用两个指针，一个从数组的左侧开始，另一个从右侧开始，然后它们交替移动，找到需要交换的元素，直到它们相遇。

整个快速排序的过程是递归的，不断地将数组分割为较小的子数组，直到子数组的大小为1，此时数组已经有序。

快速排序的平均时间复杂度为O(n log n)，其中n是数组的大小。最差情况下与冒泡排序时间复杂度相同，为O(n^2)

C++代码如下：

#include <iostream>

using namespace std;


void quick_sort(int a[], int begin, int end){
    cout << begin <<' '<< end << endl;
    if(begin >= end)
        return;
    int i = begin;
    int j = end;
    int x = a[begin];
    while(j > i){
        while(j > i && a[j] > x)
            j--;
        if(a[j] < x){
            a[i] = a[j];
            i++;
        } 
        while(j > i && a[i] < x)
            i++;
        if(a[i] > x){
            a[j] = a[i];
            j--;
        } 
    }
    a[i] = x;
    quick_sort(a, begin, i - 1);
    quick_sort(a, i + 1, end);
}

int main(){
    int a[8] = {8,5,6,4,2,10,3,9};
    quick_sort(a,0,7);
    for(int i = 0; i<8; i++)
        cout << a[i] << ' ';
}