【计算机算法设计与分析】线性时间选择（C++_分治递归）

问题描述

给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素。

思路

线性时间选择有两种方法：
（1）随机选择快排的标准元素。
（2）将集合分为n个由五个元素组成的集合，对每个五元素集合求其中位数，再对所有的五元素集合的中位数求其中位数，作为快排的标准元素。

Code

V-1（RandomizedSelect）

#include<bits/stdc++.h>
#define M 100
using namespace std;
int a[M]={6, 7, 5, 2, 5, 8, 3, 5, 1};
int n=9;
int RandomizedPatition(int l, int r){
    srand((unsigned)time(NULL));
    int t=rand()%(r-l)+l;
    swap(a[t], a[l]);//随机元素作为标准
    int flag=a[l];
    while(l<r){
        while(l<r&&a[r]>=flag)
            r--;
        if(l<r){
            swap(a[r], a[l]);
        }
        while(l<r&&a[l]<=flag)
            l++;
        if(l<r){
            swap(a[r], a[l]);
        }
    }
    a[l]=flag;
    return l;

}
int RandomizedSelect(int l, int r, int k)
{
    if(l==r)
        return a[r]; 
    int p=RandomizedPatition(l, r);//将数组分成两部分
    int s=p-l+1;
    if(k<=s)
        RandomizedSelect(l, p, k);
    else{
        RandomizedSelect(p+1, r, k-s);
    }
    
}
int main()
{
    cout<<RandomizedSelect(0, n-1, 8);
    getchar();
    return 0;
}

V-2（Select）

#include<bits/stdc++.h>
#define M 1000
using namespace std;
int a[M]={3,1,7,6,5,9,8,2,0,4,13,11,17,16,15,19,18,12,10,14,23,21,27,26,25,29,28,22,20,24,33,31,37,36,35,39,38,32,30,34,43,41,47,46,45,49,48,42,40,44,53,51,57,56,55,59,58,52,50,54,63,61,67,66,65,69,68,62,60,64,73,71,77,76,75,79,78,72,70,74}, n=80;
void Sort(int l, int r){
    for(int i=l;i<=r;i++){
        for(int j=i+1;j<=r;j++){
            if(a[i]>a[j]){
                swap(a[i], a[j]);
            }
        }
    }
}
int partition(int l, int r){
    int flag=a[l];
    while(l<r){
        while(l<r&&a[r]>=flag)
            r--;
        if(l<r){
            swap(a[r], a[l]);
        }
        while(l<r&&a[l]<=flag)
            l++;
        if(l<r){
            swap(a[r], a[l]);
        }
    }
    a[l]=flag;
    return l;
}
int Select(int l, int r, int k){
    if(r-l+1<75){//小于75个直接冒泡排序即可
        Sort(l, r);
        return l+k-1;
    }
    for(int i=0;i<=(r-l-4)/5;i++){//55分组求中位数
        int temp=Select(l+5*i, l+5*i+4, 3);
        swap(a[temp], a[l+i]);
    }
    int s=Select(l, l+(r-l-4)/5, l+(r-l-4)/10);//找出中位数的中位数
    swap(a[s], a[l]);//交换至首位作为快排标准
    int p=partition(l, r);
    int t=p-l+1;//前半部分的元素个数
    if(k<=t){
        return Select(l, p, k);
    }else{
        return Select(p+1, r, k-t);
    }
}
int main()
{
    cout<<Select(0, n-1, 60)<<endl;
    getchar();
    return 0;
}