• <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久久夜色精品国产网站| 久久青青草视频| 亚洲va久久久噜噜噜久久天堂| 久久亚洲sm情趣捆绑调教| 亚洲伊人久久精品影院| 91久久成人免费| 亚洲精品高清国产一线久久| 麻豆精品久久精品色综合| 久久九九久精品国产免费直播| 婷婷久久五月天| 无码精品久久一区二区三区| 亚洲va久久久噜噜噜久久男同| 99久久国产主播综合精品| 精品综合久久久久久888蜜芽| 精品久久久久久无码免费| 久久久国产精品网站| 99精品久久久久久久婷婷| 欧美成人免费观看久久| 久久精品中文字幕一区| 理论片午午伦夜理片久久| 国产精品日韩深夜福利久久 | 国产成人无码久久久精品一| 亚洲日韩欧美一区久久久久我| 欧美精品丝袜久久久中文字幕 | 99久久精品费精品国产一区二区| 久久人妻AV中文字幕| 午夜不卡久久精品无码免费| 色偷偷91久久综合噜噜噜噜| 一本大道久久香蕉成人网| 精品久久久久久久久免费影院| 伊人久久国产免费观看视频| 无码国内精品久久综合88| 99久久婷婷免费国产综合精品| 91精品国产色综久久| 久久人与动人物a级毛片| 久久精品夜夜夜夜夜久久| 久久免费视频6| 97久久精品无码一区二区| 日产精品久久久久久久| 久久国产乱子伦免费精品|