• <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)  編輯 收藏 引用 所屬分類: 算法與數據結構
            久久99精品久久久久久噜噜| 一级女性全黄久久生活片免费| 久久亚洲中文字幕精品一区四 | 久久综合久久美利坚合众国| 一本久久久久久久| 婷婷久久综合九色综合98| 91精品国产9l久久久久| 国产午夜精品理论片久久影视 | 亚洲国产日韩欧美久久| 蜜臀久久99精品久久久久久| 亚洲精品综合久久| 久久国产色av免费看| 久久婷婷五月综合97色一本一本 | 香蕉99久久国产综合精品宅男自| 青青热久久综合网伊人| 精品久久久久久无码人妻热| 久久午夜综合久久| 久久无码高潮喷水| 久久人人爽人人爽人人AV东京热| 久久精品a亚洲国产v高清不卡| 97久久综合精品久久久综合| 91久久香蕉国产熟女线看| 无码任你躁久久久久久老妇| 人人狠狠综合久久88成人| 国内精品久久久久影院优| 久久精品亚洲精品国产欧美| 亚洲欧美日韩久久精品| 久久精品天天中文字幕人妻| 国产综合免费精品久久久| 久久国产免费直播| 国产精品美女久久久免费| 久久九九久精品国产免费直播| 国内精品人妻无码久久久影院| 婷婷久久综合九色综合绿巨人| 亚洲中文字幕无码久久精品1| 国产一级持黄大片99久久| 久久久国产99久久国产一| 久久99国产精一区二区三区| 伊人情人综合成人久久网小说| 69久久精品无码一区二区| 久久久精品人妻一区二区三区蜜桃|