青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

學(xué)習(xí)筆記

C++、Linux

  C++博客 :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理 ::
  0 隨筆 :: 1 文章 :: 0 評論 :: 0 Trackbacks

導(dǎo)讀:http://www.cnblogs.com/zhjp11/archive/2010/02/26/1674227.html

 

現(xiàn)在要選擇第k小的數(shù)字,一種比較簡單的方法就是先排序,然后根據(jù)下標(biāo)找出第k小的數(shù)字,這個時間復(fù)雜度為O(nlogn)

selectKth有點(diǎn)類似于快速排序,不過他的時間復(fù)雜度為O(n)。(就是導(dǎo)讀中的解法3)

下面是一個運(yùn)行時間的對比圖,selectKth的運(yùn)行時間有很明顯的優(yōu)勢。

 



 

main.cpp
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include "Record.h"
#include "Rand.h"
#include "SelectKth.h"
using namespace std;
const int MaxSize=1000000;
const int Step=5000;
int main()
{
    Record record;
    int A[MaxSize],B[MaxSize],C[MaxSize];
    int curLen,i,kth;
    for(curLen=Step;curLen<MaxSize;curLen+=Step)
    {
        for(i=0;i<curLen;i++)
        {
            A[i]=RandIn(0,1234567);
            B[i]=A[i];
            C[i]=A[i];
        }
        kth=RandIn(0,curLen)+1;
        cout<<curLen<<"\t";
        //sort
        record.StartRecord();
        sort(B,B+curLen);
        cout<<B[kth-1]<<"\t";
        record.PrintCostTime();
        //select kth
        record.StartRecord();
        cout<<"\t"<<SelectKth(C,0,curLen-1,kth)<<"\t";
        record.PrintCostTime();
        cout<<endl;
    }
    return 0;
}

Record.h
#ifndef RECORD__HH
#define RECORD__HH
#include<iostream>
#include<ctime>
#include<fstream>
#include<string>
#include<cstring>
#include<iomanip>
using namespace std;

class Record
{

public:

    Record()
    {
        StartRecord();
    }
    void StartRecord()  {   startTime=clock();  }  /*重置開始時間*/
    void PrintCostTime()
    {
        curTime=clock();
        cout<<(curTime-startTime)/1000;
    }
    private:
    unsigned int startTime,curTime;
};


#endif

Rand.h
#ifndef RAND__HH__HH
#define RAND__HH__HH
#include<cstdlib>
#include<ctime>
using namespace std;
int RandIn(int left,int right)
{

    if(left>=right)
        return left;
    int res=rand();
    res=res%(right-left);
    res+=left;
    return res;
}
#endif

SelectKth.h

template <class T>
int SelectMiddle(T A[],int left,int right)
{
    int middle=((left+right)>>1),p;
    if( A[left]<A[middle] )
    {
        if(A[middle] <= A[right])
            p=middle;
        else    //A[middle] is the biggest
            p=(A[left] < A[right]) ? right :left;
    }
    else    //A[left]>=A[middle]
    {
        if(A[right]>A[left])
            p=left;
        else    //A[left] is the biggest
            p=(A[middle]< A[right]) ? right :middle;
    }
    return p;
}

template <class T>
T SelectKth(T A[],int left,int right,int kth)
{
    int i, store;
    int p=SelectMiddle(A,left,right);
    swap(A[p],A[right]);
    store = left;
    for (i = left; i < right; i++)
        if (A[i] <= A[right])
            swap(A[store++], A[i]);
    swap(A[store], A[right]);
    if(store+1==kth)
        return A[store];
    else if(store+1<kth)
        return SelectKth(A,store+1,right,kth);
    else    //sotre+1>kth
        return SelectKth(A,left,store-1,kth);
}






類別:算法 查看評論
posted on 2011-01-21 22:51 YcdoiT 閱讀(339) 評論(0)  編輯 收藏 引用
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            亚洲特级毛片| 免费视频最近日韩| 国产精品久久一卡二卡| 国产精品99久久久久久白浆小说| 亚洲精品视频一区二区三区| 欧美视频中文字幕在线| 欧美一级专区免费大片| 久久精品国产综合精品| 亚洲精品视频一区| 一本一本久久| 国产一区999| 亚洲国产精品成人精品| 欧美日韩国产综合久久| 久久精品青青大伊人av| 免费在线欧美黄色| 午夜精品久久| 老司机免费视频一区二区| 一本久道久久综合狠狠爱| 亚洲免费在线电影| 亚洲国产天堂久久综合网| 一区二区精品在线| 在线观看精品| 亚洲视频在线观看一区| 樱花yy私人影院亚洲| 日韩亚洲欧美高清| 伊人精品成人久久综合软件| 亚洲另类一区二区| 精品成人国产| 中国av一区| 亚洲精品一区二区三区不| 亚洲专区在线视频| 日韩亚洲精品在线| 久久久青草青青国产亚洲免观| 中国成人亚色综合网站| 久久欧美肥婆一二区| 亚洲欧美日韩在线播放| 欧美国产视频在线| 久久久久免费视频| 国产精品九九| 亚洲日本免费| 亚洲精品国精品久久99热| 欧美亚洲视频一区二区| 亚洲性av在线| 欧美人与禽猛交乱配| 欧美成人xxx| 狠狠色狠狠色综合日日tαg| 宅男精品视频| 亚洲视频成人| 欧美激情亚洲一区| 亚洲福利电影| 亚洲国产高清在线| 久久精品成人一区二区三区| 欧美一区二区高清在线观看| 欧美性片在线观看| 99re66热这里只有精品4| 亚洲毛片一区| 欧美日韩国产大片| 亚洲欧洲久久| 亚洲免费观看视频| 欧美激情国产日韩| 亚洲国产成人在线播放| 亚洲国产免费看| 麻豆成人在线播放| 欧美大片网址| 亚洲区中文字幕| 欧美刺激午夜性久久久久久久| 欧美成人精品三级在线观看| 亚洲动漫精品| 欧美激情视频在线免费观看 欧美视频免费一 | 亚洲精品网站在线播放gif| 亚洲第一综合天堂另类专| 欧美一区在线直播| 欧美不卡三区| 亚洲精品免费在线播放| 欧美日韩欧美一区二区| 夜夜精品视频一区二区| 午夜精品久久久久久久白皮肤| 国产精品资源| 久久精品国产亚洲aⅴ| 欧美插天视频在线播放| av成人免费观看| 国产精品美女久久久浪潮软件| 亚洲欧美另类国产| 久久综合给合| 99视频精品| 国产欧美欧洲在线观看| 久久久久**毛片大全| 欧美国产高清| 亚洲欧美国产视频| 一区二区三区我不卡| 欧美国产免费| 亚洲男女自偷自拍| 欧美成人综合在线| 亚洲一区在线看| 国模精品娜娜一二三区| 欧美国产日本| 欧美一区二区在线| 亚洲人成7777| 欧美中文字幕久久| 亚洲精品综合精品自拍| 国产精品日韩一区二区三区| 久久综合色婷婷| 中文亚洲字幕| 亚洲成人中文| 久久精品日韩| 亚洲一区二区三区免费在线观看| 激情久久一区| 国产精品www| 欧美国产日韩一二三区| 欧美一区二区三区四区在线观看地址| 欧美国产综合| 久久国产精品亚洲va麻豆| 亚洲精品欧美| 欲色影视综合吧| 国产精品久久久久久久一区探花| 美女性感视频久久久| 午夜精品久久久久久久久久久| 亚洲国产精品99久久久久久久久| 欧美一级专区| 亚洲一区二区3| 日韩一区二区精品视频| 亚洲第一久久影院| 国内精品久久久久国产盗摄免费观看完整版| 欧美风情在线观看| 久久五月天婷婷| 性做久久久久久久久| 亚洲视频在线观看网站| 亚洲精品美女在线观看| 欧美激情视频给我| 免费观看在线综合色| 久久久国际精品| 欧美亚洲一区三区| 午夜精品久久久久久久白皮肤 | 娇妻被交换粗又大又硬视频欧美| 国产精品久久影院| 国产精品久线观看视频| 国产精品高清在线| 国产精品播放| 国产精品日韩欧美一区| 国产精品萝li| 国产欧美亚洲精品| 国产视频一区欧美| 国产一区二区精品丝袜| 国产偷国产偷精品高清尤物| 国产精品影音先锋| 国产麻豆一精品一av一免费| 国产精品入口尤物| 国产日韩一区欧美| 国内精品免费在线观看| 精品69视频一区二区三区| 在线观看三级视频欧美| 亚洲国产一区二区精品专区| 亚洲精品久久久久久久久久久| 亚洲精品久久| 中文日韩电影网站| 午夜久久一区| 可以免费看不卡的av网站| 欧美大片一区| 一本色道久久99精品综合| 亚洲一区一卡| 久久久噜噜噜久噜久久| 欧美成人免费在线观看| 欧美天天综合网| 国产乱码精品一区二区三区av| 国产亚洲欧美一级| 亚洲欧洲一区二区三区在线观看| 99这里只有精品| 久久精品国产77777蜜臀| 毛片av中文字幕一区二区| 亚洲激情欧美| 午夜精品在线| 欧美成人国产| 国产九九视频一区二区三区| 亚洲第一网站| 亚洲一区二区三区欧美| 米奇777超碰欧美日韩亚洲| 亚洲精品在线视频观看| 久久riav二区三区| 欧美日韩日本国产亚洲在线| 国产一区欧美日韩| 在线亚洲成人| 男女激情久久| 亚洲免费在线看| 欧美承认网站| 狠狠色丁香久久婷婷综合_中| 99精品国产在热久久| 久久综合中文字幕| 亚洲一区二区三区精品视频| 欧美成人69av| 韩国av一区| 亚洲欧美文学| 99精品国产在热久久下载| 久久精品国产亚洲高清剧情介绍| 欧美三区在线| 亚洲理伦电影| 欧美二区在线看| 欧美在线网站| 国产日韩一级二级三级| 亚洲午夜影视影院在线观看| 亚洲第一精品久久忘忧草社区|