• <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>
            小四的海市蜃樓
            Never surrender to complexity
            posts - 21,comments - 59,trackbacks - 0

            在程序設計實踐上看到這個簡單的快速排序,用模板重新寫了一遍,加深一下印象。平均算法復雜度為O(nlogn)。

            其中尋找支點元素pivot有多種方法,不同的方法會導致快速排序的不同性能。根據分治法平衡子問題的思想,希望支點元素可以使p[m..n]盡量平均地分為兩部分,但實際上很難做到。下面給出幾種尋找pivot的方法。

            1.選擇p[m..n]的第一個元素p[m]的值作為pivot;
            2.選擇p[m..n]的最后一個元素p[n]的值作為pivot;
            3.選擇p[m..n]中間位置的元素p[k]的值作為pivot;
            4.選擇p[m..n]的某一個隨機位置上的值p[random(n-m)+m]的值作為pivot;
              按照第4種方法隨機選擇pivot的快速排序法又稱隨機化版本的快速排序法,在實際應用中該方法的性能也是最好的。本程序使用第4種方法。要求節點類型支持比較運算符。


            template<typename T>
            void quicksort(T* v, int n)
            {
                
            if (n<=1)
                    
            return;
                
            int last = 0;
                
            int pivot = rand()%n;
                swap(v, 
            0, pivot);
                
            for (int i = 1; i < n; i++)
                
            {
                    
            if (v[i]<v[0])
                        swap(v, 
            ++last, i);
                }

                swap(v, last, 
            0);
                quicksort(v, last);
                quicksort(v
            +last+1, n-last-1);
            }


            template
            <typename T>
            void swap(T* v, int i, int j)
            {
                T tmp 
            = v[i];
                v[i] 
            = v[j];
                v[j] 
            = tmp;    
            }


            隨手寫一個不太好看的測試程序

            struct str
            {
                str(
            const char* a)
                
            {
                    assert(a);
                    v 
            = new char[strlen(a)+1];
                    strcpy(v, a);
                }

                str(
            const str& a)
                
            {
                    assert(a.v);
                    v 
            = new char[strlen(a.v)+1];
                    strcpy(v, a.v);
                }

                
            ~str()
                
            {
                    delete [] v;
                }

                
            void operator = (const str& a)
                
            {
                    
            if (this == &a)
                        
            return;
                    assert(a.v);
                    delete [] v;
                    v 
            = new char[strlen(a.v)+1];
                    strcpy(v, a.v);
                }

                
            bool operator == (const str& a) const
                
            {
                    
            return (strcmp(v, a.v)==0);
                }

                
            bool operator > (const str& a) const 
                
            {
                    
            return (strcmp(v, a.v)>0);
                }

                
            bool operator < (const str& a) const
                
            {
                    
            return (strcmp(v, a.v)<0);
                }

                
            char* v;
            }
            ;


            int main(int argc, char* argv[])
            {
                
            int* array = new int [10];
                
            for(int i = 0; i < 10; i++)
                    array[i] 
            = rand();
                quicksort(array, 
            10);
                
            for(i = 0; i < 10; i++)
                
            {
                    cout
            <<array[i]<<endl;
                }


                str s[] 
            = {"bd""e""ba""a"};
                quicksort(s, 
            4);
                
            for(i = 0; i < 4; i++)
                
            {
                    cout
            <<s[i].v<<endl;
                }

                
            return 0;
            }


            posted on 2007-12-29 14:31 小四 閱讀(412) 評論(0)  編輯 收藏 引用 所屬分類: 算法與數據結構
            久久er99热精品一区二区| 亚洲va久久久噜噜噜久久男同 | 99久久国产宗和精品1上映| 国产亚洲精久久久久久无码AV| 久久99国产精一区二区三区| 国产精品一久久香蕉产线看| 99999久久久久久亚洲| 亚洲成色999久久网站| 久久人妻少妇嫩草AV无码蜜桃| 亚洲精品美女久久久久99小说 | 久久国产高清一区二区三区| 日批日出水久久亚洲精品tv| 99精品久久精品一区二区| 久久久久久亚洲Av无码精品专口 | 精品人妻伦九区久久AAA片69| 日韩精品久久无码人妻中文字幕| 国产亚洲婷婷香蕉久久精品| 四虎影视久久久免费观看| 久久久久久毛片免费播放| 久久精品无码专区免费| 午夜精品久久久久久久| 国产69精品久久久久9999| 无码国内精品久久综合88| 欧美伊香蕉久久综合类网站| 久久人人爽人人爽人人片AV不| 免费观看久久精彩视频| 思思久久精品在热线热| 丰满少妇人妻久久久久久4| 午夜人妻久久久久久久久| 亚洲欧美一级久久精品| 国产精品丝袜久久久久久不卡 | 久久久久国产亚洲AV麻豆| 久久精品国产亚洲AV无码娇色 | 欧美丰满熟妇BBB久久久| 久久青青草原精品国产软件| 国产精品久久久久天天影视| 国产成人精品综合久久久| 亚洲人成网站999久久久综合| 国产高潮久久免费观看| 久久夜色tv网站| 日本福利片国产午夜久久|