目录
一、代码二、时间复杂度三、总结一、代码
//编译环境vs #define _CRT_SECURE_NO_WARNINGS#include <stdio.h>#include <iostream>using namespace std;#include <algorithm>int select(int arr[], int low, int high, int k){int p = high - low + 1;//需要select的元素个数 if (p < 6){sort(arr + 1, arr + p+1);//待比较的元素个数为preturn arr[k];//如果数组长度比较小，那就返回}int q = p / 5;//将A分成q组，每组5个元素。如果5不整除p，则排除剩余的元素int M[80] = {0 };//将q组中的每一项单独排序，找出中项。所有中项集合为Mfor (int i = 1; i <= q; i++){sort(arr + 1 + 5 * (i - 1), arr +1+ 5 * i);//数组的话，应该会改变值的吧 M[i] = arr[3 + 5 * (i - 1)];}int mm = select(M, 1, q, q / 2+1);//无论数组多大，递归后的最后总是一个确定的值 int A1[800] = {0 }, A2[800] = {0 }, A3[800] = {0 };//开始划分int r = 0, s = 0, t = 0;for (int i = 1; arr[i] != 0; i++){if (arr[i] < mm)//小于中项的放在A1 {r++;A1[r] = arr[i];}if (arr[i] == mm)//等于中项的放在A2 {s++;A2[s] = arr[i];}if (arr[i] > mm)//大于中项的放在A3 {t++;A3[t] = arr[i];}}if (r >= k) return select(A1, 1, r, k);//为什么是return select，直接select不行吗？不行！！！if (r + s >= k)return mm;if (r + s < k) return select(A3, 1, t, k - r - s);}int main(){int a[800] = {0 };int n,k;scanf("%d",&n);//数列元素个数for (int i = 1; i <= n; i++)//输入数列元素scanf("%d",&a[i]);scanf("%d",&k);printf("%d", select(a,1,25,k));return 0;}
二、时间复杂度
见沙特版【算法设计技巧与分析】P109-111
三、总结
1、本程序采用了分治的思想。
先求出中项——将数组分为5个一组，排好序，然后可以得出每个小组的中项，构成中项集，再将中项集M递归求中项，就得到了原数组的中项mm；
再根据中项将原数组划分为三个数组，A1(<mm)，A2(=mm)，A3(>mm)；
然后判断第k小元素将会出现在三个数组中的哪一个，然后递归。
ps: 中项并不是中位数！ 就算p不能被5整除，也没关系，应为找中项就是为了尽量将原数组划分成三部分——中项左边全部小于中项，中项右边全部大于中项。
2、algorithm库的sort函数用得还不是很熟练。
sort(i，j)，i为待排的起始元素，j为待排的最后一个元素。
例如：
sort(arr,arr+4)是将数组arr的前4个元素排序；
sort(arr+1,arr+4)是将数组arr的第1-4个元素排序。
3、因书上伪代码都是类似A[1···n]，所以为避免混淆，将数组元素A[0]弃用，下标就对应A[1]…A[n]了。
