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

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            亚洲国产精品无码久久久久久曰| 午夜精品久久久久久毛片| 久久久无码精品亚洲日韩京东传媒| 久久国产精品免费一区二区三区 | 久久国产精品无码HDAV| 久久久久亚洲av无码专区| 国内精品久久久久久久97牛牛| 国产精自产拍久久久久久蜜| 国产午夜精品久久久久九九| 久久AV无码精品人妻糸列| 精品熟女少妇aⅴ免费久久| 99久久无色码中文字幕人妻| 亚洲伊人久久综合中文成人网| 久久国产精品无码一区二区三区| 精品久久久无码中文字幕天天 | 午夜视频久久久久一区| 欧美伊香蕉久久综合类网站| 性欧美大战久久久久久久久| 国产精品内射久久久久欢欢| 久久棈精品久久久久久噜噜| 无码人妻久久一区二区三区蜜桃 | 久久这里有精品| 日本加勒比久久精品| 国产精品久久久久久一区二区三区| 人妻丰满AV无码久久不卡| 久久国产精品无| 韩国三级中文字幕hd久久精品| 精品久久人妻av中文字幕| 久久久久av无码免费网| 亚洲精品国产自在久久| 日本亚洲色大成网站WWW久久| 狠狠色丁香婷婷综合久久来来去| 日本福利片国产午夜久久| 91精品国产高清久久久久久91| 精品久久久久久国产牛牛app| 国产精品一区二区久久精品| 日本精品久久久久中文字幕| 久久99精品久久只有精品 | 久久精品99久久香蕉国产色戒| 中文字幕久久精品无码| 久久综合给合久久狠狠狠97色|