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

            Problem Solving using C++

            Algorithm Study using C++

            選擇算法--Random Select

            從一個亂序數組A[1....n]中選擇排第i的數,就是經典的選擇select問題
            最Naive的辦法就是先對整個數組進行排序(可以使用quicksort/merge sort/heap sort)但是其算法復雜度為O(nlogn),如果使用quicksort的partition的變種的話,其最差復雜度為O(n^2),但是平均復雜度為O(n).其核心算法如下:
            int randselect(int p,int r,int i)
            {
                if(p==r)
                      return arr[p];
               int q = partition(p,r);//調用quicksort里面的partition
               int k = q-p+1;
               if(i==k)
                       return arr[q];
               if(i<k)
                       return randselect(p,q-1,i);
               if(i>k)
                       return randselect(q+1,r,i-k);
            }

            代碼如下:

            #include <iostream>
            #include 
            <iterator>
            #include 
            <algorithm>
            #include 
            <cstdlib>

            using namespace std;

            #define MAXSIZE    
            100
            int arr[MAXSIZE];

            void fillarray()
            {
                
            for(int i=0;i<MAXSIZE;i++)
                {
                    arr[i]
            =rand()%MAXSIZE;
                }
            }

            void print(bool flag=true)
            {
                
            if(flag)
                {
                    copy(arr,arr
            +MAXSIZE,ostream_iterator<int>(cout," "));
                    cout
            <<endl;
                }
            }

            int partition(int p,int r)
            {
                
            int pivot = arr[r];
               
                
            int i=p-1;
                
            for(int j=p;j<r;j++)
                {
                    
            if(arr[j]<pivot)
                    {
                        i
            ++;
                       
                        
            int temp = arr[j];
                        arr[j]
            =arr[i];
                        arr[i]
            =temp;
                    }
                }
               
                arr[r]
            =arr[i+1];
                arr[i
            +1]=pivot;
               
                
            return i+1;
            }

            void quicksort(int p,int r)
            {
                
            if(p<r)
                {
                    
            int q=partition(p,r);
                    quicksort(p,q
            -1);
                    quicksort(q
            +1,r);
                }
            }

            int randselect(int p,int r,int i)
            {
                
            if(p==r)
                    
            return arr[p];
                   
                
            int q = partition(p,r);
                
            int k = q-p+1;
                
            if(i==k)
                    
            return arr[q];
                
            if(i<k)
                    
            return randselect(p,q-1,i);
                
            if(i>k)
                    
            return randselect(q+1,r,i-k);
            }

            int main(int argc,char* argv[])
            {
                fillarray();
                print();
               
                
            //quicksort(0,MAXSIZE-1);
                
            //print();
                for(int i=0;i<MAXSIZE;i++)
                    cout
            <<randselect(0,MAXSIZE-1,i+1)<<" ";
               
                cout
            <<endl;
               
                system(
            "pause");
                
            return 0;
            }

            posted on 2007-08-23 10:35 Kingoal Lee's Alogrithm Study using cplusplus 閱讀(885) 評論(0)  編輯 收藏 引用

            My Links

            Blog Stats

            常用鏈接

            留言簿(1)

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久久一本精品99久久精品66| 国产精品久久久久久福利69堂| 免费国产99久久久香蕉| 精品精品国产自在久久高清| 国产精品99久久不卡| 99久久无色码中文字幕人妻| 91视频国产91久久久| 久久久久亚洲AV综合波多野结衣| 亚洲精品午夜国产VA久久成人| 久久免费美女视频| 久久天天躁狠狠躁夜夜avapp| 91久久婷婷国产综合精品青草 | 欧美精品九九99久久在观看| 久久精品嫩草影院| 熟妇人妻久久中文字幕| 久久国产视频网| 国产成人久久激情91| 午夜精品久久久久9999高清| 中文字幕亚洲综合久久2| 亚洲国产另类久久久精品小说 | 99999久久久久久亚洲| 一本一道久久a久久精品综合| 老司机国内精品久久久久| 久久久久亚洲av无码专区喷水| 蜜桃麻豆www久久国产精品| 国产精品青草久久久久福利99| 99久久精品日本一区二区免费| 久久99久国产麻精品66| 亚洲国产精品成人久久蜜臀 | 亚洲精品无码专区久久久| 久久亚洲色一区二区三区| 国产激情久久久久影院老熟女免费 | 久久九九有精品国产23百花影院| 中文字幕乱码人妻无码久久| 久久久无码精品亚洲日韩京东传媒| 久久久中文字幕日本| 久久伊人色| 色青青草原桃花久久综合| 囯产精品久久久久久久久蜜桃| 人妻无码精品久久亚瑟影视 | 精品99久久aaa一级毛片|