中位数与顺序统计量

一：最小值和最大值

在有n个元素的集合中如果想找最小值，最优也就是n-1次，但如果同时找最大值和最小值，最优可以不是2(n-1)次而是3*(n/2)次，基本思路是成对的比较，先两个数之间比较，较小值与最小值比较，较大值与最大值比较，注意奇数偶数要分开讨论。

#include<iostream> #include<algorithm> using namespace std;int main() {int size;cin >> size;int *p = new int[size];for (int i = 0; i < size; i++)cin >> p[i];int MIN, MAX;if (size % 2 == 1)//奇偶要分开来讨论，奇数直接将p[0]作为最大和最小值，后面成对比较{MIN = MAX = p[0];for (int i = 1; i < size; i += 2){int tempmin, tempmax;if (p[i] > p[i + 1]){tempmin = p[i + 1];tempmax = p[i];}else{tempmin = p[i];tempmax = p[i + 1];}MIN = min(tempmin, MIN);MAX = max(tempmax, MAX);}}else{MIN = min(p[0], p[1]);MAX = max(p[0], p[1]);for (int i = 2; i < size; i += 2){int tempmin, tempmax;if (p[i] > p[i + 1]){tempmin = p[i + 1];tempmax = p[i];}else{tempmin = p[i];tempmax = p[i + 1];}MIN = min(tempmin, MIN);MAX = max(tempmax, MAX);}}cout << "max=" << MAX << endl;cout << "min=" << MIN << endl;delete[] p;return 0; }

二：期望为线性时间的选择算法

要从n个元素的集合中选出第i大的元素，基本思路是利用快排中的Partition函数，这个函数调用后可以知道某一个数的大小在集合中具体的位置，这样经过二分就可以递归用线性时间得到第i大的元素。因为这里只要取其中一支递归，所以RandSelect的T(n)=O(1)，总期望运行时间只有Partition的O(n)。
#include<iostream> #include<algorithm> using namespace std;int Partition(int a[], int p, int r); int RandSelect(int a[], int p, int r, int pos);int main() {int n,pos;cout << "Enter the length of array and the specific elements" << endl;cin >> n;int *a = new int[n+1];for (int i = 1; i <= n; i++)cin >> a[i];cout << "Enter the position of number you want to select" << endl;cin >> pos;int ans=RandSelect(a, 1, n, pos);cout << "the answer is " << ans << endl;delete[] a;return 0; }int RandSelect(int a[], int p, int r, int pos) {if (p == r)return a[p];int q = Partition(a, p, r);int k = q - p + 1;//已知的排第k的数if (pos == k)return a[q];else if (pos < k)return RandSelect(a, p, q - 1, pos);elsereturn RandSelect(a, q + 1, r, pos-k); } int Partition(int a[], int p, int r)//就是快排的分区函数 {int x = a[r];int i = p - 1;for(int j=p;j<r;j++)if (a[j] <= x){i++;swap(a[i], a[j]);}swap(a[i + 1], a[r]);return i + 1; }

转载于:https://www.cnblogs.com/seasonal/p/10343710.html

总结

以上是生活随笔为你收集整理的中位数与顺序统计量的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。