特别简单的问题，从一组数组中选出第k大的元素A[i]，最容易想到的办法时间复杂度为O(n^2)，考虑快排中的划分法（分治思想）
选择的基准元素默认是数组的第一个。
图1 复杂度较高的划分法伪代码（来源：国科大刘老师PPT）
对应代码：
// 试用划分法 int PartSelect(vector<int>& A, int n, int k) { int m, r, j; m = 1; r = n + 1; A[n + 1] = 0; while (true) { j = r; partition(A,m,j); if (k = j) return j; // 返回j,当前数组的元素A[j]是第j小的元素 else if (k < j) r = j; // j是新的下标上界 else { m = j + 1; k = k - j; // j+1是新的下标下界 } } } // 但是这样每次分治迭代只会减少1的复杂度，最坏复杂度（n2）其他划分法主要过程如下图所示：
图1 《算法导论 》p123
改进后的选择问题的划分法：改变划分元素，使每次划分规模减半，将A划分为r(如r=5)个一组，共有n/5(向上取整)个组（取n/5个中位），每组找一个中位数，把它们放到集合M中，可使用排序法。
talk is cheap,show me the code.
代码的一些解释，选用的排序算法是改进后的插入排序（使用二分查找去插），复杂度是O(nlogn)，但是排序的元素是各个组的，总复杂度就是另外一回事来了。也可使用归并排序，在下面的代码中都有实现。
目录3的算法描述中选取各组中位数组成一个新的组，看起来很简单，但是下面实现的代码中没有增加新的数组，都在一个数组中进行。具体表现为将选取的中位数通通聚集到数组的前面。再排序，选出最终的，通过交换元素位置实现。
在调试时，发现最开始是3组，递归到最后是1组，所以加了一些判断，代码看起来有点复杂和乱，暂时不管了~能力有限见谅，有错误敬请指正~
//选择问题 //问题描述：在一个数组A[1..n]中寻找第k小元素t,并将其存放于位置k,即A[k]=t。 // 关键词：分治 #include <iostream> using namespace std; #include<algorithm> #include <vector> class SelectPartitionClass { public: //选择问题 // 快排 划分元素 int partition(vector<int> &arr,int startIndex, int endIndex) { // 被划分的数组是arr[m,p-1], //选定作划分的数组元素（基准元素）是v=arr[m] int pivot = arr[startIndex];//取第一个元素当做基准元素 int left = startIndex; int right = endIndex; while (left!=right) { while (left<right&&arr[right]>pivot) { right--;// 控制right指针左移 } while (left<right && arr[left]<=pivot) { left++;// 从右向左查 } if (left < right) { // 交换A[i]和A[p]的位置 swap(arr[left], arr[right]); } } //pivot和指针重合点交换 arr[startIndex] = arr[left]; arr[left] = pivot; // 划分元素在位置p,把本来在2位置的划分元素挪到4去。也相当于做一个交换 return left; // 返回基准元素的位置 } // 试用划分法 int PartSelect(vector<int>& A, int n, int k) { int m, r, j; m = 1; r = n + 1; A[n + 1] = 0; while (true) { j = r; partition(A,m,j); if (k = j) return j; // 返回j,当前数组的元素A[j]是第j小的元素 else if (k < j) r = j; // j是新的下标上界 else { m = j + 1; k = k - j; // j+1是新的下标下界 } } } // 但是这样每次分治迭代只会减少1的复杂度，最坏复杂度（n2） int midposition = 0; // 改进后的选择问题的划分法：改变划分元素，使每次划分规模减半 int Select(vector<int> &arr,int m,int p,int k) {// 输入arr[0,...n],k是置顶要输出的第k小的元素 // 将A划分为r(如r=5)个一组，共有n/5(向上取整)个组（取n/5个中位） // 每组找一个中位数，把它们放到集合M中 // 可使用排序法，时间复杂度为O(c) // 参数说明：返回一个i值，使得A[i]是A[m..p]中第k小的元素 int n, i, j; int r = 5; if (p - m + 1 <= r) { insertSort(arr, m, p); return m+k; // m+k是这个的中位数 } while(true){ n = p - m + 1; int t = floor( n / r); // 新的边界，0-m + floor(n / r) if (t==1) { // 当只有1组时，交换后arr[1]就是中位数了，直接去划分就好 for (int i = 1; i <= 1; i++) {//计算中间值 int right = m + i * r - 1; insertSort(arr, m + (i - 1) * r, right); // i代表这是第几组 // 将中间值收集到A[m..p]的前部 swap(arr[m + i - 1], arr[m + (i - 1) * r + (int)ceil(r / 2)]); } }else{ for (int i = 1; i <= floor(n / r) + 1; i++) {//计算中间值 int right = m + i * r - 1; if (i == floor(n / r) + 1) { right = n - 1; insertSort(arr, m + (i - 1) * r, right); // i代表这是第几组 // 最后一组元素个数n mod 5 swap(arr[m + i - 1], arr[m + (i - 1) * r + (int)ceil((n % 5) / 2)]); } else { insertSort(arr, m + (i - 1) * r, right); // i代表这是第几组 // 将中间值收集到A[m..p]的前部 swap(arr[m + i - 1], arr[m + (i - 1) * r + (int)ceil(r / 2)]); } } int newright = m + floor(n / r) ;// 分成了3组就有3个中位数[0,2]再次进行排序，选最终的中位数 // 为什么要将ceil(floor(n/r)/2 中值的中值 作为k传入=>选好的中位数现在排在最前面，还需要再中位数中选出中位数 j=Select(arr,m, newright,ceil(floor(n/r)/2));// 左边界m,右边界m+floor(n/r)-1，中值的中值 // 这里期望j返回的是什么呢？返回中位数的位置？ swap(arr[m],arr[j]); } midposition= partition(arr,m, p); // 以最终选出的中位数arr[m]，这里中位数已经被收集到前面了作为参照数，将数组s划分为两个部分，使得m所处的位置比左侧的数目大1 if (midposition-m+1==k) {// 如果划分后左侧的元素的个数+1后刚好等于k，那么这个中位数就是要找的 return arr[midposition]; }else if(midposition -m+1>k) { p = midposition - 1; }else { k = k - (midposition -m+1); m = midposition + 1; } } } private: // 二分法 查找插入位置 int searchInsert(vector<int>& Array, int left, int right, int target) { /* if ((right-left)==1) { int position; position = Array[left] > Array[right] ? left-1 : right-1; return position; }*/ while (left <= right) { int mid = left + (right - left) / 2; if (Array[mid] == target) { return mid; } else if (Array[mid] < target)//如果中间值偏小，将初端右移 { left = mid + 1; } else //中间值偏大则终端左移 { right = mid - 1; } } return left;//如果目标值target比最大值还大，最后left>right，left=nums.size() //如果比最小值还小，最后left值为0，因为right会先减为-1后与left交换，left=0且比right大，跳出循环且符合题意，目标值变为初端 } // 插入排序，时间复杂度是n^2，但是使用二分查找优化后的插入排序复杂度是O(nlogn) void insertSort(vector<int>& arr, int start, int end) { int length = end - start + 1; //将arr[]按升序排列 for (int j = 1; j < length; j++) { //利用二分法查找要插入的位置,计算机算法与分析第三章课后练习第二.1题 //int key = arr[j+ times *5]; int key = arr[j + start]; int k = searchInsert(arr, start, j + start, key);//找到需要插入的位置k // 交换位置 if (k != j + start) { for (int i = j + start; i > k; i--) { arr[i] = arr[i - 1]; } arr[k] = key; } } } /*归并排序的复杂度直接是O(nlogn)*/ void merge(vector<int>& arr, int low, int mid, int high) { //merge函数将两部分，（分别排好序的子数组），合并成一个，再存于原数组arr int h, i, j, k; h = low; i = low; j = mid + 1; // h,j作为游标，i指向temp存放数组元素的游标 /* c++中 利用vector创建一个带有变量的二维数组！！！ */ int len = arr.size(); vector<int> temp(11); // 这个temp数组是local的,长度为数组arr长度 while (h <= mid && j <= high) { // 当两个集合都没有取尽时 if (arr[h] <= arr[j]) { temp[i] = arr[h]; h = h + 1; } else { temp[i] = arr[j]; j++; } i++; } if (h > mid) { // 当第一子组元素被 取尽，而第二组元素未被取尽时 for (int k = j; k <= high; k++) { temp[i] = arr[k]; i++; } } else { // 当第2组取尽，第一组未被取尽时 for (int k = h; k <= mid; k++) { temp[i] = arr[k]; i++; } } for (int k = low; k <= high; k++) {//将临时数组temp中的元素再赋值给arr arr[k] = temp[k]; } } void mergeSort(vector<int>& arr, int low, int high) { // arr[low..high]是一个全程数组，含有high-low+1个待排序元素 if (low < high) { int mid = low+(high-low) / 2; mergeSort(arr, low, mid); mergeSort(arr, mid + 1, high); merge(arr, low, mid, high); } } }; //Ques20200925 int main() { SelectPartitionClass cla = SelectPartitionClass(); vector<int> arrs = { -3,2,5,8,4,3,9,10,6,7,1,0,14 }; int a=cla.Select(arrs, 0,12,6); cout << a; return 0; }-3,0,1,2,3,4,5,6,7,8,9,10,14
第6大的元素是4.
测试了下，好像没太多问题...希望= =
图2 复杂度分析（来源：国科大刘老师PPT）
