• <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>

            學習筆記

            C++、Linux

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

            導讀:http://www.cnblogs.com/zhjp11/archive/2010/02/26/1674227.html

             

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

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

            下面是一個運行時間的對比圖,selectKth的運行時間有很明顯的優勢。

             



             

            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 閱讀(336) 評論(0)  編輯 收藏 引用
            …久久精品99久久香蕉国产| 一本久道久久综合狠狠躁AV| 精品久久久久成人码免费动漫| 97精品国产97久久久久久免费| 久久精品人人槡人妻人人玩AV | 久久精品无码一区二区三区日韩| 狠狠干狠狠久久| 好属妞这里只有精品久久| 99久久精品国产麻豆| 99国产欧美精品久久久蜜芽| 国产精品一久久香蕉产线看| 久久精品成人免费看| 久久久精品人妻无码专区不卡| 久久久国产精品| 偷偷做久久久久网站| 久久久久亚洲AV无码麻豆| 国产精品久久波多野结衣| 夜夜亚洲天天久久| 久久综合偷偷噜噜噜色| 久久久久亚洲AV成人片| 国产精品欧美久久久久无广告| 欧美日韩精品久久久久| 久久影院综合精品| 久久99精品国产麻豆蜜芽| 亚洲国产美女精品久久久久∴| 91精品国产乱码久久久久久| 久久久久国产日韩精品网站| 久久人人爽人人人人片av| 91久久成人免费| 久久婷婷是五月综合色狠狠| 精品久久久久久无码专区 | 久久er热视频在这里精品| 香蕉99久久国产综合精品宅男自 | 久久久久久久女国产乱让韩| 91久久精品91久久性色| 久久综合色老色| 久久激情五月丁香伊人| 国产成人精品久久二区二区| 久久久一本精品99久久精品88| 青青热久久综合网伊人| 久久久久久久亚洲Av无码|