0006算法笔记——【分治法】线性时间选择

《0006算法笔记——【分治法】线性时间选择》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、线性时间选择问题：给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素，（这里给定的线性集是无序的）。    1、随机划分线性选择    线性时间选择随机划分法可以模仿随机化快速排序算法设计。基本思想是对输入数组进行递归划分，与快速排序不同的是，它只对划分出的子数组之一进行递归处理。    程序清单如下：[cpp] viewplain copy1.//2d9-1 随机划分线性时间选择  2.#include "stdafx.h"  3.#include    4.#incl

2、ude   5.using namespace std;   6.  7.int a[] = {5,7,3,4,8,6,9,1,2};  8.  9.template   10.void Swap(Type &x,Type &y);  11.  12.inline int Random(int x, int y);  13.  14.template   15.int Partition(Type a[],int p,int r);  16.  17.temp

3、late  18.int RandomizedPartition(Type a[],int p,int r);  19.  20.template   21.Type RandomizedSelect(Type a[],int p,int r,int k);  22.  23.int main()  1.{  2.    for(int i=0; i<9; i++)  3.    {  4.        cout<

4、out<  11.void Swap(Type &x,Type &y)  12.{  13.    Type temp = x;  14.    x = y;  15.    y = temp;  16.}  17.  18.inline int Random(int x, int y)  19.{  20.     srand((unsigned)

5、time(0));  21.     int ran_num = rand() % (y - x) + x;  22.     return ran_num;  23.}  24.  25.template   26.int Partition(Type a[],int p,int r)  27.{  28.    int i = p,j = r + 1;  29.    Type x = a[p];  30.  31.    while(true)  32.    {  33.        w

6、hile(a[++i]x);  35.        if(i>=j)  36.        {  37.            break;  38.        }  39.        Swap(a[i],a[j]);  40.    }  41.    a[p] = a[j];  42.    a[j] = x;  43.    return j;  44.}  1.  2.template  3.int Ra

7、ndomizedPartition(Type a[],int p,int r)  4.{  5.    int i = Random(p,r);  6.    Swap(a[i],a[p]);  7.    return Partition(a,p,r);  8.}  9.  10.template   11.Type RandomizedSelect(Type a[],int p,int r,int k)  12.{  13.    if(p == r)  14.    {  15.      

8、  return a[p];  16.    }  17.    int i = RandomizedPartition(a,p,r);  18.    int j = i - p + 1;  19.    if(k <= j)  20.    {  21.        return RandomizedSelec