问题描述

在统计学领域中,中项是一个非常关键的常用的指标值。序列的中项是指排好序后序列的“中间”元素,中项是指序列的第[n/2]个最小元素。寻找序列中项的问题被称为中项值问题,寻找序列中第k小元素的问题被称为选择问题。

要求:

  1. 元素个数n≥100。

  2. 请利用减治的思想,设计该问题的分治算法。

  3. 采用两种划分的方式:教材上的方法和随机选择的方法,并对比两种方法的性能

问题分析

在平常寻找向量(数组、容器)数值第k个元素时,我们一般使用快速排序将元素按指定规则排序,则第k个元素位置即排好序的第k-1向量位置。这种方法平均时间复杂度为O(nlogn – n +1)。

这里,我们采用分治方法,降低时间复杂度为线性。

算法设计

  1. 先将数组按照每五个分为一组,剩下多余元素排去

  2. 其次将分好的数组用快排排序,时间为cn(c约等于7),所以时间消耗为线性阶

  3. 去各分组数组的中值构成一个新数组,并求出新数组中值mm。时间消耗为线性阶

  4. 根据中值mm,将中值mm设置为基准,原数组根据mm划成三个集合A,B,C。(A中元素值小于mm,B中元素值等于mm,C中元素值大于mm)

  5. 根据如下情况进行下一步

    如果A集合数字个数大于K,则返回select(A,0,high,k)

    如果A + B 集合的数字个数等于K,则mm即位所求,返回mm即可

    否则 select(C,0,high,k)

  6. 分治过程如下

    • 分:将数组分按照mm为三个集合
    • 治:判断k在哪个集合,不同集合治法不同
    • 组合: 这里涉及到了简治,即排除不可能为所寻找元素,降低了时间复杂度
    • 阈值:当集合值为mm时,返回mm。

参考代码

#include <bits/stdc++.h>
using namespace std;
void QuickSort(vector<int> &a, int left, int right) {
if(left < right)
{
int i = left, j = right, k = a[left];
//利用循环,使基准左边数字均小于基准,右边均大于基准
while (i < j) {
while (i < j && a[j] < k) { --j; } //从右向左找到第一个比基准大的数
if (i < j) { a[i++] = a[j]; }
while (i < j && a[i] > k) { ++i; } //从左向右找到第一个比基准小的数
if (i < j) { a[j--] = a[i]; }
}
a[i] = k;
QuickSort(a, left, i - 1); // 排序k左边
QuickSort(a, i + 1, right); // 排序k右边
}
}
void divide(vector<int>&a,int &numa, int & numb ,const int mm){
int i = 0 , j = a.size()-1 , k = mm;
//利用循环,使基准左边数字均小于基准,右边均大于基准
while (i < j) {
while (i < j && a[j] < k) { --j; } //从右向左找到第一个比基准大的数
if (i < j) { a[i++] = a[j]; }
while (i < j && a[i] > k) { ++i; } //从左向右找到第一个比基准小的数
if (i < j) { a[j--] = a[i]; }
}
a[i] = mm;
for(int i = 0 ; i < a.size()-1 ;++i){if(a[i] == mm){numb++;}}
numa = i + 1 ;
}

int Search_K_Element(vector<int>&v,int low,int high,int k){
int p = high - low + 1;
if(p < 44) {
QuickSort(v,low,high);
return v[v.size() / 2];
}
vector<int> m ;
int tmp = 2 , mm = 0,pos = 0;
//分组并排序
int cnt = (high - low + 1)/ 5 ;
int left = low ,right = low + 4 ;
for(int i = 0 ; i < cnt ; ++i){
QuickSort(v,left,right);
left += 5 ;
right += 5 ;
}
//分组中项排序
for(int i = 0 ; i < cnt ; ++i){
m.push_back(v[tmp]);
tmp += 5 ;
}
QuickSort(m,0,m.size()-1);
if(m.size() % 2 == 0){mm = m[m.size() / 2 - 1];}
else {mm = m[(m.size()+1) / 2 - 1];}
//确定mm在原数组的位置
for(int i = 0 ; i < v.size()-1 ; ++i){if(v[i] == mm){pos = i ; break;}}
//分A,B,C三个数组
int numa = 0 , numb = 0 , numc = 0;
divide(v,numa,numb,mm);
numc = v.size() - numa - numb ;
//cout<<mm<<endl;
if(numa > k ){
Search_K_Element(v,low,numa - 1, k);
}
else if(numa + numb >= v.size() / 2 ) {return mm ;}
else {
Search_K_Element(v,numa + numb,numc - 1, k - numa - numb);
}
}

int main()
{
vector<int> v ;
cout<<"请输入待寻找中项数组,以r字母结束"<<endl;
while(1)
{
int tmp = 0 ;
int r =scanf("%d",&tmp);
if(r == 0){break;}
else { v.push_back(tmp);}
}
fflush(stdin);
int k ;
cin >> k ;
int result = Search_K_Element(v,0,v.size()-1,k);
cout<<result<<endl;
for(int i = 0 ; i< v.size() ; ++i) {cout << v[i] << " ";}
return 0;
}

谢谢访问