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

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

ID:37955490

大小:127.30 KB

页数:9页

时间:2019-06-03

0006算法笔记——【分治法】线性时间选择_第1页
0006算法笔记——【分治法】线性时间选择_第2页
0006算法笔记——【分治法】线性时间选择_第3页
0006算法笔记——【分治法】线性时间选择_第4页
0006算法笔记——【分治法】线性时间选择_第5页
资源描述:

《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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。