分治思想求解的问题，但是比较特殊，只有分解问题和求解小问题，不需要合并
每次也只需要经过判断，分解一半，所以比其他分解两边的效率高
最坏情况时间复杂度为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,1)">int right,1)">int k); main() { //次序选择问题：求数组中第k小的元素 思想：分而治之 将问题分解partition 如果要找的第k个元素正好是基准值，那正好，也就是最好情况了，时间复杂度为O(n)，因为只进行了一次partition 如果要找的第k个元素在基准值左侧，也就是左子数组里，那么在子数组里，还是找第k小元素 如果要找的第k个元素在基准值右侧，也就是右子数组里，那么在右子数组里，找的是第k-(q-p+1)个元素 int k = 1; vector<int> data = { 7,5,1)">6,1)">4,1)">3,1)">1,1)">9 }; 获取序列元素个数 int length = data.size(); int left = 0; int right = 6int result;用来保存第k小元素的值 result = select(data,left,right,k); cout << result << endl; } 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 - 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++ data.at(i); data.at(i) = key; data.at(right) = temp; 此时的i就是基准值的位置 以上是partition部分，可以单独写成函数调用 当前第cur小的元素，这里很重要，一定要这么写 int cur = i - left + if (k == cur)如果基准值正好是第k小元素 return data.at(i); else if (k < cur)要找的第k小元素出现在左边 { return select(data,i - ,k); } else { 如果出现在右边，原始的第k小元素在右边子数组中就是第k-cur小元素，这里很重要 } }
