目录
分治算法思想
分治算法使用条件
二分搜索
分治算法之快速排序
思想:规模为n的原问题的解无法直接求出,进行问题规模缩减,划分子问题(这里子问题相互独立和原问题解的性质是相同的,只是问题规模缩小了)。如果子问题的规模仍然不够小,再进行子问题划分,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止,最后将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原问题的解。
分治算法所能解决的问题一般具有以下几个特征:
每次查找中间元素,从中间元素分开成二叉树,递归依次找到最后一个节点
代码实现:
#include <stdio.h> #include <stdlib.h> #include <vector> #include <algorithm> #include <iostream> using namespace std; bool binarySearch(vector<int> &vec, int i, int j, int val) { if (i > j) { return false; //元素不存在; } int mid = (i + j) / 2; if (vec[mid] == val) { return true; } else if (vec[mid] > val) { return binarySearch(vec, i, mid - 1, val); } else { return binarySearch(vec, mid + 1, j, val); } } int main() { vector <int> vec; for (int i = 0; i < 11; ++i) { vec.push_back(rand() % 100); } sort(vec.begin(), vec.end()); for (int v : vec) { cout << v << " "; } cout << endl; bool result = binarySearch(vec, 0, vec.size() - 1, 58); cout << "result : " << result << endl; system("pause"); return 0; }
结果如图:
见文章交换排序中的快排交换排序 (冒泡排序和快速排序)_xiaoming1999的博客-CSDN博客