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

學(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视频在线精品国自产拍免费观看| 欧美日本不卡高清| 性欧美精品高清| 久久精品99国产精品日本| 亚洲国产经典视频| 亚洲精品三级| 国产日韩欧美在线播放| 美女精品在线观看| 欧美色区777第一页| 久久成人免费日本黄色| 免费在线观看成人av| 亚洲综合二区| 久久亚洲一区二区三区四区| 一区二区高清视频在线观看| 香蕉久久夜色精品| 日韩图片一区| 久久精品免费观看| 亚洲一区二区三区乱码aⅴ| 久久成人在线| 亚洲欧美影院| 欧美激情一区二区三区高清视频| 久久se精品一区精品二区| 欧美国产日本在线| 久久精品伊人| 国产精品任我爽爆在线播放| 欧美激情精品久久久久久免费印度| 国产精品人成在线观看免费| 亚洲国产精品va在线看黑人| 国产精品日本欧美一区二区三区| 欧美高清不卡| 好看的日韩视频| 亚洲视频欧美在线| 日韩一级裸体免费视频| 久久久久青草大香线综合精品| 亚洲欧美制服中文字幕| 欧美日本高清| 亚洲七七久久综合桃花剧情介绍| 精品成人在线视频| 欧美一区二区三区四区视频| 亚洲一区三区在线观看| 欧美巨乳波霸| 亚洲破处大片| 亚洲精品韩国| 欧美承认网站| 亚洲国产日韩美| 亚洲欧洲一区二区在线播放| 久久野战av| 欧美成人一区二区三区| 亚洲高清视频在线| 久久久综合激的五月天| 免费观看久久久4p| 在线成人黄色| 久久亚洲国产精品一区二区| 美女精品在线| 亚洲国产mv| 免费日韩视频| 最新国产成人在线观看| 亚洲精品美女在线观看播放| 欧美va天堂va视频va在线| 欧美肥婆bbw| 亚洲老司机av| 欧美午夜精品理论片a级按摩| 夜夜嗨一区二区| 欧美一级片一区| 国产亚洲成精品久久| 久久精品国产99精品国产亚洲性色| 久久中文字幕导航| 亚洲福利免费| 欧美日韩免费在线观看| 中文一区二区| 久久久久久**毛片大全| 在线观看一区视频| 欧美日韩成人精品| 亚洲欧美日韩国产综合| 久久久久久久999精品视频| 亚洲高清视频的网址| 欧美激情一区二区三区| 亚洲一区高清| 欧美sm视频| 亚洲一区二区三区午夜| 国产亚洲欧美中文| 欧美www在线| 亚洲欧美国产精品va在线观看| 开心色5月久久精品| 日韩视频第一页| 国产日本亚洲高清| 欧美激情影音先锋| 亚洲欧美在线一区| 亚洲大胆av| 欧美一区二区在线看| 亚洲人成网站999久久久综合 | 久久精品1区| 亚洲黄色在线| 国产日本欧洲亚洲| 欧美激情一二三区| 欧美一区二区在线免费播放| 亚洲清纯自拍| 蜜桃久久av| 欧美一区二区在线免费播放| 亚洲激情中文1区| 国产区精品视频| 欧美日韩精品不卡| 久久一二三国产| 亚洲免费在线电影| 日韩视频免费观看高清在线视频| 久久人人爽人人| 欧美亚洲免费高清在线观看| 亚洲乱码精品一二三四区日韩在线| 国产色产综合产在线视频| 欧美日韩国产综合视频在线观看中文| 欧美在线综合| 午夜老司机精品| 亚洲视频高清| 99精品99久久久久久宅男| 欧美国产日韩精品免费观看| 久久久爽爽爽美女图片| 欧美一区综合| 亚洲欧美日韩国产中文| 制服丝袜激情欧洲亚洲| 亚洲精品免费在线观看| 亚洲电影免费| 在线观看中文字幕不卡| 国内精品久久久久影院薰衣草| 国产精品视频xxxx| 国产精品理论片| 国产精品成人在线观看| 欧美手机在线| 国产精品久久久久久久浪潮网站| 欧美日韩黄色大片| 欧美色网在线| 国产精品麻豆va在线播放| 国产精品福利网| 国产精品久久久久久久久免费桃花| 欧美午夜不卡视频| 国产精品久久97| 国产欧美在线观看| 国产视频精品免费播放| 国产视频不卡| 伊甸园精品99久久久久久| 在线免费观看视频一区| 1024欧美极品| 99re热这里只有精品视频| 一区二区三区av| 欧美一区二区成人| 久久嫩草精品久久久精品| 欧美成人精品福利| 亚洲精品偷拍| 亚洲午夜视频| 久久久水蜜桃| 欧美日本一区| 国产精品自拍视频| 欲香欲色天天天综合和网| 亚洲精品乱码久久久久久日本蜜臀| 99re热精品| 欧美一区二区三区免费看| 久久全球大尺度高清视频| 免费在线成人av| 一本色道久久88综合亚洲精品ⅰ | 亚洲国产视频一区| 一区二区三区四区在线| 欧美亚洲三区| 欧美电影在线观看完整版| 国产精品国产成人国产三级| 国产一区久久| 一区二区高清| 久久婷婷蜜乳一本欲蜜臀| 亚洲日本中文字幕| 午夜日韩激情| 欧美另类视频| 狠狠色狠狠色综合日日小说| 99精品国产在热久久婷婷| 久久精品91| 亚洲免费大片| 久久午夜激情| 国产精品一区在线观看你懂的| 在线观看日韩av电影| 午夜精品999| 亚洲黑丝一区二区| 欧美综合国产| 国产精品成人在线| 亚洲精品一区二区三区福利| 欧美一区二区私人影院日本| 亚洲欧洲一区二区三区| 久久大综合网| 国产精品丝袜xxxxxxx| 99热免费精品| 欧美freesex8一10精品| 亚洲欧美视频在线观看视频| 欧美连裤袜在线视频| 亚洲国产99精品国自产| 久久精品毛片| 亚洲免费中文| 国产精品毛片大码女人| 一区二区成人精品 | 99国产精品久久|