分治思想求解的问题,但是比较特殊,只有分解问题和求解小问题,不需要合并
每次也只需要经过判断,分解一半,所以比其他分解两边的效率高
最坏情况时间复杂度为O(n^2),期望时间复杂度为O(n)
找基准值时候可以考虑随机选择
#include<iostream> #include<vector> #include<algorithm> #include<random> #include<ctime> using namespace std; int select(vector<int>& data, int left, int right, int k); int main() { //次序选择问题:求数组中第k小的元素 // 思想:分而治之 // 将问题分解partition // 如果要找的第k个元素正好是基准值,那正好,也就是最好情况了,时间复杂度为O(n),因为只进行了一次partition //如果要找的第k个元素在基准值左侧,也就是左子数组里,那么在子数组里,还是找第k小元素 //如果要找的第k个元素在基准值右侧,也就是右子数组里,那么在右子数组里,找的是第k-(q-p+1)个元素 int k = 1; vector<int> data = { 7,5,6,4,3,1,9 }; //获取序列元素个数 int length = data.size(); int left = 0; int right = 6; int result;//用来保存第k小元素的值 result = select(data, left, right, k); cout << result << endl; } int select(vector<int>& data, int left, int right, int k) { if (left == right) return data.at(left);//递归结束的条件 //这部分是partition,也可以单独写成一个函数调用 int key = data.at(right); /*这里有一种优化的方法,就是这个中轴数随机的找,然后交换到末尾,再往下执行*/ /* default_random_engine e(time(0)); //时间引擎 uniform_int_distribution<signed> u(left, right); int key = u(e); int tem = data.at(key); data.at(key) = data.at(right); data.at(right) = tem; int ave = data.at(right); */ int i = left - 1; for (int j = left; j < right; j++) { if (data.at(j) <= key) { i++; int temp = data.at(j); data.at(j) = data.at(i); data.at(i) = temp; } } //将基准值放在合适的位置 i++; int temp = data.at(i); data.at(i) = key; data.at(right) = temp; //此时的i就是基准值的位置 //以上是partition部分,可以单独写成函数调用 //当前第cur小的元素,这里很重要,一定要这么写 int cur = i - left + 1; if (k == cur)//如果基准值正好是第k小元素 return data.at(i); else if (k < cur)//要找的第k小元素出现在左边 { return select(data, left, i - 1, k); } else { return select(data, i + 1, right, k - cur);//如果出现在右边,原始的第k小元素在右边子数组中就是第k-cur小元素,这里很重要 } }