分治法的基本思想是:将原问题分解为若干个规模更小但结构与原问题相似的子问题,递归地解这些子问题,然后将这些子问题的解组合为原问题的解。

  • 分解(divide):将原问题分解成一系列子问题
  • 解决(conquer):递归地解决各子问题。若子问题足够小,则直接求解
  • 合并(combine):将子问题的结果合并成原问题的解

快速排序

利用分治法可将快速排序的分为三步:

  • 在数据集之中,选择一个元素作为”基准”(pivot)。
  • 所有小于”基准”的元素,都移到”基准”的左边;所有大于”基准”的元素,都移到”基准”的右边。这个操作称为分区 (partition) 操作,分区操作结束后,基准元素所处的位置就是最终排序后它的位置。
  • 对”基准”左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。

此处输入图片的描述


#include<iostream>
#include<vector>

using namespace std;

int partition(vector<int> &vi, int low, int up) {
    int pivot = vi[up];  // 直接选最右边的元素为基准元素
    int i = low - 1;
    for (int j = low; j < up; j++) {
        if (vi[j] <= pivot) {
            ++i;
            swap(vi[i], vi[j]);
        }
    }

    swap(vi[i + 1], vi[up]); // 将基准元素放到正确位置上
    return i + 1;
}

void quicksort(vector<int> &vi, int low, int up) {
    if (low < up) {
        int mid = partition(vi,low,up);
        quicksort(vi, low, mid - 1);
        quicksort(vi, mid + 1, up);
    }
}

int main() {
    vector<int> a{ 3,7,8,4,2,1,9,5,5 };
    for (auto i : a)
        cout << i << " ";
    cout << endl;

    quicksort(a, 0, a.size() - 1);
    for (auto i : a)
        cout << i << " ";
    cout << endl;

    system("pause");

}

归并排序

  • 分解(divide):将个元素分成各含个元素的子序列
  • 解决(conquer):用合并排序法对两个子序列递归地排序
  • 合并(combine):合并两个已排序的子序列以得到排序结果

Merge Sort


int merge(vector<int> &vi, int b, int m, int e) {
    vector<int> tmp(e - b + 1);
    int s1 = b, s2 = m + 1;
    int k = 0;
    //合并两有序数组
    while (s1 <= m && s2 <= e) {
        if (vi[s1] <= vi[s2])
            tmp[k++] = vi[s1++];
        else
            tmp[k++] = vi[s2++];
    }
    //剩余部分
    while (s1 <= m) tmp[k++] = vi[s1++];
    while (s2 <= e) tmp[k++] = vi[s2++];

    for (int i = 0; i < k; ++i) vi[b + i] = tmp[i];
}

int mergesort(vector<int> &vi, int p, int r) {
    if (p < r) {
        int q = (p + r) / 2;
        mergesort(vi, p, q);
        mergesort(vi, q + 1, r);
        merge(vi, p, q, r);
    }
}