分治法思想介绍和案列

说明

 本文我先写在我的CSDN上后再转到该博客系统的，有些链接会跳转我的CSDN上

分治法基本思想

• 将一个难以直接解决的大问题，分割成一些规模较小的k个相同问题，以便·各个击破，分而治之·。
• 对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为若干个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。
• 将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。

 递归是实现分治算法思想的技术。:point_right:查看递归的介绍

 合并排序的例子

分治法的适用条件

分治法所能解决的问题一般具有以下几个特征：

1. 该问题的规模缩小到一定的程度就可以容易地解决

    因为问题的计算复杂性一般是随着问题规模的增加而增加，大部分问题满足这个特征。

2. 该问题可以分解为若干个规模较小的相同问题

    这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用

3. 利用该问题分解出的子问题的解可以合并为该问题的解

    能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，;而不具备第三条特征，则可以考虑贪心算法或动态规划。

4. 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题

    如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。

分治法的基本步骤

divide-and-conquer(P)
  {
    if ( | P | <= n0) adhoc(P);  //解决小规模的问题, adhoc(P)是基本子算法
    divide P into smaller subinstances P1,P2,...,Pk；//分解问题
    for (i=1,i<=k,i++)
      yi=divide-and-conquer(Pi);  //递归的解各子问题
    return merge(y1,...,yk);  //将各子问题的解合并为原问题的解
  }

| P | 表示问题的规模，n0是规模的阈值，表示当问题P的规模不超过n0时，直接用adhoc(P)算法求解，不必继续分解。

  实践表明，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。

分治法的复杂性分析

• 分治法将规模为n的问题,分成k个规模为n／m的子问题去解。当然并不一定都是n/m。参考快速排序的最坏情况的复杂度
• 设分解规模阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。
• 再设将原问题分解（ divide ）为k个子问题,以及用merge将k个子问题的解合并（merge）为原问题的解,需用f(n)个单位时间。

 用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有：

通过迭代法求得方程的解：

求解步骤:

大整数的乘法

 请设计一个有效的算法，可以进行两个n位二进制大整数的乘法运算

• 小学的方法：O(n2)      ×效率太低

• 分治法:XY = ac 2n + (ad+bc) 2n/2 + bd    O(n^2)    ×效率太低

为了降低时间复杂度，必须减少乘法的次数。

• XY = ac 2^n + ((a-b)(d-c)+ac+bd) 2^n/2 + bd

• XY = ac 2^n + ((a+b)(d+c)-ac-bd) 2^n/2 + bd

细节问题：两个XY的复杂度都是O(nlog3)，但考虑到a+b,d+c可能得到m+1位的结果，使问题的规模变大，故不选择第2种方案。

复杂度分析

参考上面的分治复杂度一般公式

Strassen矩阵乘法

若依此定义来计算A和B的乘积矩阵C，则每计算C的一个元素C[i][j]，需要做n次乘法和n-1次加法。因此，算出矩阵C的n2个元素所需的计算时间为O(n3)

• 传统方法：O(n^3)
• 分治法:
   使用与上例类似的技术，将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为：
  

  由此可得：
      

复杂度分析

为了降低时间复杂度，必须减少乘法的次数。

复杂度分析

  Hopcroft和Kerr已经证明(1971)，计算2个２×２矩阵的乘积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算2×2矩阵的7次乘法这样的方法了。或许应当研究３×３或５×５矩阵的更好算法

  在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是 O(n2.376)

棋盘覆盖问题

问题描述

  棋盘覆盖问题。有一个2k∗2k的方格棋盘，恰有一个方格是黑色的，其他为白色。你的任务是用包含3个方格的L型牌覆盖所有白色方格。黑色方格不能被覆盖，且任意一个白色方格不能同时被两个或更多牌覆盖。如图所示为L型牌的4种旋转方式。

思路分析

分治三步骤
  划分问题：将2k∗2k的棋盘划分为2k−1∗2k−1 这样的子棋盘4块。
   递归求解：递归填充各个格子，填充分为四个情况，在下面会有解释，递归出口为k=0也就是子棋盘方格数为1。
   合并问题：不需要合并子问题。

递归填充的四种情况
   如果黑方块在左上子棋盘，则递归填充左上子棋盘；否则填充左上子棋盘的右下角，将右下角看做黑色方块，然后递归填充左上子棋盘。
   如果黑方块在右上子棋盘，则递归填充右上子棋盘；否则填充右上子棋盘的左下角，将左下角看做黑色方块，然后递归填充右上子棋盘。
   如果黑方块在左下子棋盘，则递归填充左下子棋盘；否则填充左下子棋盘的右上角，将右上角看做黑色方块，然后递归填充左下子棋盘。
   如果黑方块在右下子棋盘，则递归填充右下子棋盘；否则填充右下子棋盘的右下角，将左上角看做黑色方块，然后递归填充右下子棋盘。

复杂度分析

   

 :point_right:可参考分治的基本复杂度分析

算法

#include<iostream>

using namespace std;

const int MAXNUM=100;

int chess[MAXNUM][MAXNUM];

//相同的L牌为同一个数字，除了第一个黑色单为0
int cur;

//row为最上边行，column为最左边列，x和y是当前黑色方格的位置，size_是棋盘的大小
//row对应y，column对应x
void chessBoard(int row,int column,int x,int y,int size_){
      if(size_==1){
            return;
      }

      int s=size_/2;

      int cur_=++cur;

      //获取中间的位置
      int row_center=row+s;
      int column_center=column+s;

      //左上角判断
      if(x<column_center&&y<row_center){
            chessBoard(row,column,x,y,s);
      }else{
            chess[column_center-1][row_center-1]=cur_;
            chessBoard(row,column,column_center-1,row_center-1,s);
      }

      //右上角判断
      if(x>=column_center&&y<row_center){
            chessBoard(row,column_center,x,y,s);
      }else{
            chess[column_center][row_center-1]=cur_;
            chessBoard(row,column_center,column_center,row_center-1,s);
      }

      //在下角判断
      if(x<column_center&&y>=row_center){
            chessBoard(row_center,column,x,y,s);
      }else{
            chess[column_center-1][row_center]=cur_;
            chessBoard(row_center,column,column_center-1,row_center,s);
      }

      //右下角判断
      if(x>=column_center&&y>=row_center){
            chessBoard(row_center,column_center,x,y,s);
      }else{
            chess[column_center][row_center]=cur_;
            chessBoard(row_center,column_center,column_center,row_center,s);
      }

}

void print(int len){
      for(int i=0;i<len;i++){
            for(int j=0;j<len;j++){
                  cout<<chess[i][j]<<"\t";
            }
            cout<<endl<<endl<<endl;
      }
}


int main(){
      int row,column,size_;
      cout<<"请输入棋盘的大小：";
      cin>>size_;
      cout<<"请输入棋盘中初始时黑色方格的位置(输入格式：x y):";
      cin>>row>>column;
      if(size_==0){
            return 0;
      }
      cur=1;
      chess[column][row]=0;
      chessBoard(0,0,row,column,size_);
      print(size_);


}

测试结果

二分搜索

问题描述

  给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x。

分析

 是否满足分治法的特征？

  √ 该问题的规模缩小到一定的程度就可以容易地解决；
  √ 该问题可以分解为若干个规模较小的相同问题;
  √ 分解出的子问题的解可以合并为原问题的解；
  √ 分解出的各个子问题是相互独立的。

 给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x。

 分析：如果n=1即只有一个元素，则只要比较这个元素和x就可以确定x是否在表中。因此这个问题满足分治法的第一个适用条件

  √ 该问题的规模缩小到一定的程度就可以容易地解决；

 分析：比较x和a的中间元素a[mid],mid=(left+right)/2

• 若x=a[mid]，则x在L中的位置就是mid；
• 如果x<a[mid]，则x在a[mid]的前面；
• 如果x>a[mid]，则x在a[mid]的后面。

 无论在哪部分查找x，其方法都和在a中查找x一样，只不过是查找的规模缩小了。这就说明此问题满足分治法的第二个和第三个适用条件
  √ 该问题可以分解为若干个规模较小的相同问题;
  √ 分解出的子问题的解可以合并为原问题的解；

 分析：很显然此问题分解出的子问题相互独立，即在a[mid]的前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件:

           a[0,…, mid-1,mid, mid+1,…,n]

  √ 分解出的各个子问题是相互独立的。

二分搜索算法

//二分搜索
int binarySearch(int arr[],int len,int target){
      int left=0;
      int right=len-1;
      int mid;
      while(left<=right){
            mid=(left+right)/2;
            if(target<arr[mid]){
                  right=mid-1;
            }else if(target>arr[mid]){
                  left=mid+1;
            }else if(target==arr[mid]){
                  return mid;
            }

      }

      return -1;
}

完整算法

  :point_right:快排和二分搜索的实验记录

快速排序

基本思想

 基于分治策略的排序在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大（小）的记录一次就能交换到后（前）面单元，总的比较和移动次数较少。

---

 基本思想：对于输入子数组a[p: r]

1. 分解: 以a[p]为基准元素将a[p: r]划分成三段a[p: q-1], a[q] 和a[q+1:r], 使得a[p: q-1]中任一元素<= a[q], a[q+1:r]中任一元素>= a[q]. q在划分过程中确定.
2. 递归求解: 分别对a[p: q-1]和a[q+1:r]进行递归排序.
3. 合并: 将排好序的a[p: q-1]和a[q+1:r]直接合并, 即得a[p: r].

例子

主要算法

template<class Type>
void QuickSort (Type a[ ], int p, int r)
{
      if (p<r) {
        int q=Partition(a,p,r);
            QuickSort (a,p,q-1); //对左半段排序
            QuickSort (a,q+1,r); //对右半段排序
        }
}

template<class Type>
int Partition (Type a[], int p, int r)
{
        int i = p, j = r + 1; 
        Type x=a[p];
        // 将< x的元素交换到左边区域
        // 将> x的元素交换到右边区域
        while (true) {
           while (a[++i] <x);
           while (a[- -j] >x);
           if (i >= j) break; 
           Swap(a[i], a[j]);
           }
       a[p] = a[j];
       a[j] = x;
       return j;
}

上述的Partition (Type a[], int p, int r)适用于指定了某个基准元素,然后以该基准元素进行比较

另一种Partition(),其实思想差不多

int Partition (int arr[],int start_,int end_){
      int value=arr[start_];

      while(start_<end_){
            while(start_<end_&&arr[end_]>=value) end_--;
            arr[start_]=arr[end_];
            while(start_<end_&&arr[start_]<=value) start_++;
            arr[end_]=arr[start_];
      }
      arr[end_]=value;
      return end_;
}

复杂度分析

平均时间复杂度
     
 :point_right: 可参考分治的基本复杂度分析

最坏时间复杂度
  在最坏的情况下，待排序的序列为逆序，每次划分产生的两个区域分别包含(n-1)个元素和1个元素。如果递归树画出来，它就是一棵斜树。此时需要执行（n‐1次）递归调用，且第i次划分需要经过（n‐i）次关键字的比较才能找到第i个记录，也就是基准元素的位置，因此比较次数为

     

针对最坏情况的算法改进

• 快速排序算法的性能取决于划分的对称性。
• 通过修改算法partition，可以设计出采用随机选择策略的快速排序算法。
• 在快速排序算法的每一步中，当数组还没有被划分时，可以在a[p:r]中随机选出一个元素作为划分基准，这样可以使划分基准的选择是随机的，从而可以期望划分是较对称的。

  template<class Type>
  int RandomizedPartition (Type a[ ], int p, int r)
  {
        int i = Random(p,r);
        Swap(a[i], a[p]);
        return Partition (a, p, r);
  }

 :point_right: 如果想研究随机选择策略，可以看一下线性时间选择问题的基本求解

算法

#include<iostream>

using namespace std;

int Partition (int arr[],int start_,int end_);


//先进行快排，将我们的数组进行排序，再进行二分搜索
void quickSort(int arr[],int startV,int endV){
      if(startV<endV){
            int mid=Partition (arr,startV,endV);
            quickSort(arr,startV,mid-1);
            quickSort(arr,mid+1,endV);
      }
}

//获取中间的数
int Partition (int arr[],int start_,int end_){
      int value=arr[start_];

      while(start_<end_){
            while(start_<end_&&arr[end_]>=value) end_--;
            arr[start_]=arr[end_];
            while(start_<end_&&arr[start_]<=value) start_++;
            arr[end_]=arr[start_];
      }
      arr[end_]=value;
      return end_;

}





int main(){
      int len;  //数组长度

      cout<<"请输入长度:";
      cin>>len;
      int* arr=new int[len];
      cout<<endl<<"请输入数字：";
      for(int i=0;i<len;i++){
            cin>>arr[i];
      }

      quickSort(arr,0,len-1);
      cout<<"排序后的数组： ";
      for(int i=0;i<len;i++){
            cout<<arr[i]<<"  ";
      }
}

测试样例

输入

请输入长度:10
请输入数字：2 8 9 4 3 50 10 66 0 8

删除

排序后的数组： 0 2 3 4 8 8 9 10 50 66

---

合并排序

基本思想

 将n个元素分成2个大小相同的子集合，分别对子集合进行排序，最终将排好序的子集合合并为有序集合。n=1时中止。

算法分析

 当最小规模为4时，进行排序和归并,将已经比较好的较小的值依次排好序放在一个临时的数组中

 上面的是规模为4时的分析，归并算法中，一般把规模缩小到2，并开始进行排序和归并

归并算法

复杂度分析

 :point_right: 可参考分治的基本复杂度分析

  计算过程

  原式等价于 T(n)=2T(n/2)+n
  递推得: 2T(n/2)=2(2T(n/2^2^)+n/2)=22T(n/2^2^)+n
       T(n)= 2^2^T(n/2^2^)+2n
   又有: 2^2^T(n/2)=2^3^T(n/2^3^)+n
    故: T(n)= 2^3^T(n/2^3^)+3n
     ………………….
      T(n)=2^k^T(n/2^k^)+kn
    令k=logn，即n/2^k^=1 得：
      T(n)=nT(1)+nlogn=O(nlogn)

自然排序

 自然排序是合并排序算法的一个变形。eg：{4,8,3,7,1,5,6,2}

1. 用一次对初始数组的扫描找出所有已排好序的子数组段;{4,8},{3,7},{1,5,6},{2}
2. 将相邻排好序的数组两两合并,直至完成整个数组的排序. {3,4,7,8},{1,2,5,6}, …………

 算法MergeSort平均时间复杂度：O(nlogn)(logn次合并)

 最好时间复杂度：O(n) (初始已排好序)

算法

#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;
void Merge(int a[], int left, int mid, int right)
{
    int t_pos = 0, low = left, high = mid + 1;
    int lenth = right - left + 1;
    int temp[lenth];
    while(low <= mid && high <= right)
    {
        if(a[low] < a[high])
        {
            temp[t_pos++] = a[low++];
        }
        else
        {
            temp[t_pos++] = a[high++];
        }
    }
    while(low <= mid)
    {
        temp[t_pos++] = a[low++];
    }
    while(high <= right)
    {
        temp[t_pos++] = a[high++];
    }
    for(int i = 0; i < lenth; ++i)
    {
        a[left++] = temp[i];
    }
}
void MergeSort(int a[], int left, int right)
{
    if(left >= right)
        return;
    else
    {
        int mid = (left + right) / 2;
        MergeSort(a, left, mid);
        MergeSort(a, mid + 1, right);
        Merge(a, left, mid, right);
    }
}
int main()
{
    int a[MAX];
    int num;
    cout<<"请输入数字的个数：";
    cin>>num;
    cout<<"请输入要排序的数字：";
    for(int i = 0; i < num; ++i)
    {
        cin>>a[i];
    }

    MergeSort(a, 0, num - 1);
    cout<<"归并排序后的数字：";
     for(int i = 0; i < num; ++i)
    {
        cout<<a[i]<<" ";
    }
}

测试样例

输入

请输入数字的个数：10
请输入要排序的数字：2 8 9 4 3 50 10 66 0 8

输出

归并排序后的数字：0 2 3 4 8 8 9 10 50 66

线性时间选择

问题描述

 给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素。在线性时间内O（n）？

• k=1; 最小元素 O(n)
• k=n; 最大元素 O(n)
• k=(n+1)/2: 中位数 O(n)?

算法思想

 线性时间选择问题的分治法：模仿快速排序算法，找第k小元素。

 思想:对输入数组递归划分，但仅对划分出的子数组之一进行递归处理。

主要算法

template<class Type>
Type RandomizedSelect(Type a[ ], int p, int r, int k)
{
     if (p==r) return a[p];
      //一次快速排序，随机选择基准元素，划分数组
     int i=RandomizedPartition(a,p,r), 
     j=i-p+1;        // j为a[p,i]中元素个数
     if (k<=j) return RandomizedSelect(a,p,i,k);
        //返回第k-j小元素
      else return RandomizedSelect(a,i+1,r,k-j);
}

小例子

 有一个数组:{ 4, 2, 5, 7, 4, 9, 6, 21 }

复杂度分析

平均时间复杂度

        

 可以证明，算法randomizedSelect可以在O(n)平均时间内找出n个输入元素中的第k小元素

最坏时间复杂度

 在最坏情况下（找最小，但总在最大处划分），算法randomizedSelect需要O(n^2^)计算时间。
      

        

完整算法

//2d9-1 随机划分线性时间选择
#include "stdafx.h"
#include <iostream> 
#include <ctime>
using namespace std; 

int a[] = {5,7,3,4,8,6,9,1,2};

template <class Type>
    void Swap(Type &x,Type &y);

inline int Random(int x, int y);

template <class Type>
    int Partition(Type a[],int p,int r);

template<class Type>
    int RandomizedPartition(Type a[],int p,int r);

template <class Type>
    Type RandomizedSelect(Type a[],int p,int r,int k);

int main()
{
    for(int i=0; i<9; i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;
    cout<<RandomizedSelect(a,0,8,3)<<endl;
}

template <class Type>
    void Swap(Type &x,Type &y)
{
    Type temp = x;
    x = y;
    y = temp;
}

inline int Random(int x, int y)
{
    srand((unsigned)time(0));
    int ran_num = rand() % (y - x) + x;
    return ran_num;
}

template <class Type>
    int Partition(Type a[],int p,int r)
{
    int i = p,j = r + 1;
    Type x = a[p];

    while(true)
    {
        while(a[++i]<x && i<r);
        while(a[--j]>x);
        if(i>=j)
        {
            break;
        }
        Swap(a[i],a[j]);
    }
    a[p] = a[j];
    a[j] = x;
    return j;
}

template<class Type>
    int RandomizedPartition(Type a[],int p,int r)
{
    int i = Random(p,r);
    Swap(a[i],a[p]);
    return Partition(a,p,r);
}

template <class Type>
    Type RandomizedSelect(Type a[],int p,int r,int k)
{
    if(p == r)
    {
        return a[p];
    }
    int i = RandomizedPartition(a,p,r);
    int j = i - p + 1;
    if(k <= j)
    {
        return RandomizedSelect(a,p,i,k);
    }
    else
    {
        //由于已知道子数组a[p:i]中的元素均小于要找的第k小元素
        //因此，要找的a[p:r]中第k小元素是a[i+1:r]中第k-j小元素。
        return RandomizedSelect(a,i+1,r,k-j);
    }
}

别急！这个算法有很大的缺陷，接下来我们来解决一下最坏时间复杂度的问题

最坏时间复杂度的问题思考

 若能在O(n)内找到一个划分基准，使得所划分的2个子数组长度，都至少为原数组长度的ε倍(0<ε <1 )，则在最坏情况下用O(n)时间完成选择任务。

 例如，若ε=9/10，算法递归调用所产生的子数组的长度至少缩短1/10。所以，在最坏情况下，算法所需的计算时间T(n)满足递归式：
           T(n)≤T(9n/10)+O(n)

           由此可得T(n)=O(n)

 是不是一下子就把最坏时间复杂度从O(n^2^)变成了O(n)。接下来的问题就是如何寻找划分基准?

寻找划分基准-O(n)算法

基本思想

• 定义查找第k小元素算法为 Select(Type a[], int p, int r, int k)
• 将n个输入元素划分成$\lceil n/5 \rceil$个组，每组5个元素，只可能有一个 组不是5个元素。
• 用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共$\lceil n/5 \rceil$个。
• 递归调用算法select来对$\lceil n/5 \rceil$个组按照中位数排序，同时，找 出这$\lceil n/5 \rceil$个中位数元素的中位数。
• 如果$\lceil n/5 \rceil$是偶数，就找它的2个中位数中较大的一个。以这个 元素作为划分基准。

将中位数的中位数x，作为基准元素

      

 简单划分案列

计算大于和小于基准X的元素数目

 组中除了中位数，小于基准x的元素个数有：

 中位数中小于基准x的个数为：

---

 因此，小于基准x的元素个数至少为：

 同理，大于基准x的元素个数至少为：

红框表示的是一定小于基准X的元素
蓝框表示的是一定大于基准X的元素
两者的值理论上是相等的

 要注意一下n≥75的情况

  当n≥75时，3(n-5)/10≥n/4。所以，按此基准划分所得的2个子数组的长度都至少缩短1/4。

主要算法

Type Select(Type a[], int p, int r, int k)
{   
    if (r-p<75) {
        //用某个简单排序算法对数组a[p:r]排序;
        return a[p+k-1];
    };
    for ( int i = 0;  i<=(r-p-4)/5;  i++ ) // i代表组数
    {
        //将元素每5个分成一组，分别排序
        BubbleSort(a, p+5*i, p+5*i+4); 
        //将该组中位数与a[p+i]交换位置,即： 将a[p+5*i] 至a[p+5*i+4]的第3小元素与a[p+i]交换位置;
        Swap(a[p+5*i+2], a[p+i]); 
    }  //  O(n)
    //找中位数的中位数
    Type x = Select(a, p, p+(r-p-4)/5, (r-p-4)/10); // T(n/5)
    int i=Partition(a, p, r,  x), //  O(n)
    j=i-p+1;
    if (k<=j) return Select(a, p, i, k);
    else return Select(a,i+1,r,k-j);     
}  

复杂度分析

 设找第K小元素的算法的时间复杂性是: T(n)

 找中位数的中位数:  T(n/5)

 调用快速排序partition函数对每个数组进行排序:  O(n):

 按照上述方法所选的基准x进行划分，得到的两个子数组分别至多有3n/4个元素：T(3n/4)

     

算法

//中位数线性时间选择
#include <ctime>
#include<stdlib.h>
#include <iostream>
#include<algorithm>
using namespace std;

template <class Type>
void Swap(Type &x,Type &y);

inline int Random(int x, int y);

template <class Type>
void BubbleSort(Type a[],int p,int r);

template <class Type>
int Partition(Type a[],int p,int r,Type x);

template <class Type>
Type Select(Type a[],int p,int r,int k);

int main()
{
    //初始化数组
    int a[100];

    //数字索引
    int k;

    //必须放在循环体外面
    srand((unsigned)time(0));

    for(int i=0; i<100; i++)
    {
        a[i] = Random(0,500);
        cout<<"a["<<i<<"]:"<<a[i]<<" ";
    }
    cout<<endl;


    cout<<"请输入您要获取的数字索引(从1开始)：";
    cin>>k;


    cout<<"第"<<k<<"个元素是"<<Select(a,0,100,k)<<endl;



    //重新排序，对比结果
    BubbleSort(a,0,100);

    for(int i=0; i<100; i++)
    {
        cout<<"a["<<i<<"]:"<<a[i]<<" ";
    }
    cout<<endl;
}

template <class Type>
void Swap(Type &x,Type &y)
{
    Type temp = x;
    x = y;
    y = temp;
}

inline int Random(int x, int y)
{
     int ran_num = rand() % (y - x) + x;
     return ran_num;
}

//冒泡排序
template <class Type>
void BubbleSort(Type a[],int p,int r)
{
     //记录一次遍历中是否有元素的交换
     bool exchange;
     for(int i=p; i<r-1;i++)
     {
        exchange = false ;
        for(int j=0; j<r-1-i; j++)
        {
            if(a[j]>a[j+1])
            {
                Swap(a[j],a[j+1]);
                exchange = true;
            }
        }
        //如果这次遍历没有元素的交换,那么排序结束
        if(false == exchange)
        {
             break ;
        }
     }

}

template <class Type>
int Partition(Type a[],int p,int r,Type x)
{
    int i = p-1,j = r ;

    while(true)
    {
        while(a[++i]<x && i<r);
        while(a[--j]>x);
        if(i>=j)
        {
            break;
        }
        Swap(a[i],a[j]);
    }
    return j;
}


template <class Type>
Type Select(Type a[],int p,int r,int k)
{
    if(r-p<75)
    {

        //BubbleSort(a,p,r);
        sort(a + p, a + r);
        return a[p+k-1];
    }


    for(int i=0; i<=(r-p-4)/5; i++)
    {
        //将元素每5个分成一组，分别排序，并将该组中位数与a[p+i]交换位置
        //使所有中位数都排列在数组最左侧，以便进一步查找中位数的中位数
        //BubbleSort(a,p+5*i,p+5*i+4);
        sort(a+p+i*5,a+p+5*i+4);
        Swap(a[p+5*i+2],a[p+i]);
    }


    //找中位数的中位数
    Type x = Select(a,p,p+(r-p-4)/5,(r-p-4)/10);




     int i = Partition(a,p,r,x);


    int j = i-p+1;



    if(k<=j)
    {
        return Select(a,p,i,k);
    }
    else
    {
        return Select(a,i+1,r,k-j);
    }

}

该代码还是有一些小bug，输出的值有时候有一些偏差，并且用冒泡算法代替sort()也有一些小问题。暂时不想去改了，以后有时间再看吧。

测试用例

随机产生的100个数据
a[0]:402 a[1]:436 a[2]:336 a[3]:309 a[4]:130 a[5]:154 a[6]:348 a[7]:96 a[8]:141 a[9]:168 a[10]:375 a[11]:159 a[12]:253 a[13]:269 a[14]:137 a[15]:228 a[16]:254 a[17]:385 a[18]:301 a[19]:185 a[20]:169 a[21]:48 a[22]:472 a[23]:131 a[24]:353 a[25]:457 a[26]:360 a[27]:315 a[28]:211 a[29]:278 a[30]:395 a[31]:430 a[32]:489 a[33]:296 a[34]:108 a[35]:489 a[36]:255 a[37]:78 a[38]:433 a[39]:320 a[40]:370 a[41]:213 a[42]:53 a[43]:319 a[44]:469 a[45]:294 a[46]:444 a[47]:63 a[48]:101 a[49]:351 a[50]:89 a[51]:270 a[52]:151 a[53]:306 a[54]:171 a[55]:5 a[56]:159 a[57]:164 a[58]:215 a[59]:472 a[60]:103 a[61]:78 a[62]:405 a[63]:499 a[64]:297 a[65]:314 a[66]:129 a[67]:296 a[68]:262 a[69]:27 a[70]:32 a[71]:386 a[72]:175 a[73]:136 a[74]:479 a[75]:424 a[76]:234 a[77]:434 a[78]:159 a[79]:100 a[80]:485 a[81]:397 a[82]:341 a[83]:82 a[84]:348 a[85]:234 a[86]:12 a[87]:351 a[88]:277 a[89]:486 a[90]:365 a[91]:303 a[92]:151 a[93]:381 a[94]:291 a[95]:115 a[96]:243 a[97]:324 a[98]:279 a[99]:319

输入
请输入您要获取的数字索引(从1开始)：25

输出
第25个元素是151

排序好的数组
a[0]:5 a[1]:12 a[2]:27 a[3]:32 a[4]:48 a[5]:53 a[6]:63 a[7]:78 a[8]:78 a[9]:82 a[10]:89 a[11]:96 a[12]:100 a[13]:101 a[14]:103 a[15]:108 a[16]:115 a[17]:129 a[18]:130 a[19]:131 a[20]:136 a[21]:137 a[22]:141 a[23]:151 a[24]:151 a[25]:154 a[26]:159 a[27]:159 a[28]:159 a[29]:164 a[30]:168 a[31]:169 a[32]:171 a[33]:175 a[34]:185 a[35]:211 a[36]:213 a[37]:215 a[38]:228 a[39]:234 a[40]:234 a[41]:243 a[42]:253 a[43]:254 a[44]:255 a[45]:262 a[46]:269 a[47]:270 a[48]:277 a[49]:278 a[50]:279 a[51]:291 a[52]:294 a[53]:296 a[54]:296 a[55]:297 a[56]:301 a[57]:303 a[58]:306 a[59]:309 a[60]:314 a[61]:315 a[62]:319 a[63]:319 a[64]:320 a[65]:324 a[66]:336 a[67]:341 a[68]:348 a[69]:348 a[70]:351 a[71]:351 a[72]:353 a[73]:360 a[74]:365 a[75]:370 a[76]:375 a[77]:381 a[78]:385 a[79]:386 a[80]:395 a[81]:397 a[82]:402 a[83]:405 a[84]:424 a[85]:430 a[86]:433 a[87]:434 a[88]:436 a[89]:444 a[90]:457 a[91]:469 a[92]:472 a[93]:472 a[94]:479 a[95]:485 a[96]:486 a[97]:489 a[98]:489 a[99]:499