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

    
            

            




            







												


        


            


            The Fourth Dimension Space
            

            枯葉北風寒，忽然年以殘，念往昔，語默心酸。二十光陰無一物，韶光賤，寐難安； 不畏形影單，道途阻且慢，哪曲折，如渡飛湍。斬浪劈波酬壯志，同把酒，共言歡！  -如夢令
            

            




            
	
					
	
            
		
            
			SortWizard(排序精靈）——我的排序類
		
            
		
            //排序精靈
            //Copyright:abilitytao,Nanjing University Of Science And Technology 





            /////////////////////////BEGIN_TEMPLATE_BY_ABILITYTAO_ACM//////////////////////////////////////
            #include<iostream>
            #include            <cstdio>
            #include            <algorithm>
            #include            <cmath>
            using namespace std;


            template            <class T>
            class SortWizard
            {
            private:
                T             *a;
                            int n;
            public:
                SortWizard()            {    a=NULL;n=0;}
                SortWizard(T             *a,int n){this->a=a;this->n=n;}
                            void Set(T *a,int n){this->a=a;this->n=n;}
                            void InsertSort();
                            void ShellSort();
                            void BubbleSort();
                            void QuickSort();
                            void SelectSort();
                            void MergeSort();
                            void HeapSort();
            }            ;

            template            <class T>
            void SortWizard<T>:: InsertSort()//直接插入排序,時間復雜度為O(n^2)
            {

                            int i,j;
                T temp;
                            for(i=1;i<n;i++)
                            {

                    temp            =a[i];
                                for(j=i-1;j>=0;j--)
                                {
                                    if(temp<a[j])
                            a[j            +1]=a[j];
                                    else
                                        break;
                    }
                    a[j            +1]=temp;
                    
                }
            }



            template            <class T>
            void SortWizard<T>::ShellSort()//希爾排序,時間復雜度為O(n^1.5)
            { 
                            int i,j,d;
                T temp;
                d            =n>>1;
                            while(d>=1)
                            {
                                for(i=d;i<n;i++)
                                { 
                        temp            =a[i];
                                    for(j=i-d;j>=0;j-=d)
                                    {
                                        if(a[j]>temp) 
                                a[j            +d]=a[j];
                                        else 
                                            break;
                        }
                        a[j            +d]=temp;
                    }            //這個while實際上是直接插入排序

                    d            >>=1;//即d右移一位，d除以2；
                }
            }            //ShellSort



            template            <class T>
            void SortWizard<T>::BubbleSort()//冒泡排序,時間復雜度為O(n^2)
            {
                            int i,j;
                T temp;
                            for(i=n-1;i>0;i--)
                            {
                                for(j=0;j<i;j++)
                                {
                                    if(a[j]>a[j+1])
                                    {

                            temp            =a[j];
                            a[j]            =a[j+1];
                            a[j            +1]=temp;
                        }
                    }
                }
            }


            /////////////////////快速排序,時間復雜度為O(nlog2n)///////////////////////
            template<class T>
            int Partion(T a[],int i,int j)//劃分函數
            {  
                T temp;
                temp            =a[i];
                            while(i<j)
                            {  
                                while(i<j && temp<=a[j])  
                            j            --;
                                if(i<j)
                                { 
                        a[i]            =a[j]; 
                        i            ++; 
                    }
                                while(i<j && a[i]<=temp) 
                        i            ++;
                                if(i<j)
                                { 
                        a[j]            =a[i]; 
                        j            --; 
                    }
                }
                a[i]            =temp;
                            return i;
            }


            template             <class T>
            void qsort(T a[],int l,int h)
            {
                            int m;
                            if(l<h) 
                            { 
                    m            =Partion(a,l,h);
                    qsort(a,l,m            -1);
                    qsort(a,m            +1,h); 
                }
            }

            template            <class T>
            void SortWizard<T>::QuickSort()
            {
                qsort(a,            0,n-1);
            }

            ////////////////////QuickSort_O(nlog2n)////////////////////////



            template             <class T>
            void SortWizard<T>::SelectSort()//選擇排序，時間復雜度為O(n^2)
            {
                            int i,j,k;
                T temp;
                            for(i=0;i<n-1;i++)
                            {   
                    k            =i;
                                for(j=i+1;j<n;j++)
                                {
                                    if(a[j]<a[k])
                            k            =j;
                    }
                        temp            =a[k];
                        a[k]            =a[i];
                        a[i]            =temp;
                }
            }

            ///////////////////////堆排序////////////////////////////
            template <class T>
            void Sift(T a[],int k,int m)//k篩選標號，m篩選范圍
            {
                            int i,j;
                T temp;
                i            =k;
                j            =2*i+1;//j指向左兒子;
                temp=a[i];//暫存a[i];
                while(j<=m)
                            { 
                                if(j<m &&a[j]<a[j+1])
                            j            ++;
                                if(temp<a[j])
                                { 
                        a[i]            =a[j];
                        i            =j;
                        (j            <<=1)++;//j*2+1
                    }
                                else 
                                    break;
                }
                a[i]            =temp; 
            }                    


            template             <class T>
            void SortWizard<T>::HeapSort()//堆排序，建堆時間復雜度O(n)，篩選O(nlog2n);

            {
                            int i;
                T temp;
                            for(i=(n>>1)-1;i>=0;i--)
                    Sift(a,i,n            -1);

                            for(i=n-1;i>=1;i--)
                            {  
                    temp            =a[0];
                    a[            0]=a[i];
                    a[i]            =temp;
                    Sift(a,            0,i-1);
                }
            }
            /////////////////////HeapSort_O(nlog2n)///////////////////////////




            ///////////////////////歸并排序,時間復雜度O(nlog2n)/////////////////////////////

            template             <class T>
            void Merge(T sr[],T tr[],int l,int m,int n)
            {
                            int i,j,k;
                i            =l;
                j            =m+1;
                k            =l-1;
                            while(i<=m && j<=n)
                            {
                                if(sr[i]<sr[j]) 
                        tr[            ++k]=sr[i++];
                                else 
                        tr[            ++k]=sr[j++];
                }
                                while(i<=m)
                        tr[            ++k]=sr[i++];
                                while(j<=n)
                        tr[            ++k]=sr[j++];
                                for(i=l;i<=n;i++) 
                        sr[i]            =tr[i];
            }

            template             <class T>
            void Msort(T a[],T st[],int s,int t)
            {
                            int m;
                            if(s<t) 
                            { 
                    m            =(s+t)>>1;
                    Msort(a,st,s,m);
                    Msort(a,st,m            +1,t);
                    Merge(a,st,s,m,t);
                }
            }

            template             <class T>
            void SortWizard<T>::MergeSort()
            { 
                T             *st=new T[n];
                Msort(a,st,            0,n-1);  
                delete  [ ]st;
            }
            //////////////////////MergeSort_O(nlog2n)///////////////////////////////


            /////////////////////////END_TEMPLATE_BY_ABILITYTAO_ACM//////////////////////////////////////





            int main ()
            {
                SortWizard            <double>test;
                            double test1[]={10.4,9.1,8.4,7,6,5,4,3,2,1};
                test.Set(test1,            sizeof(test1)/sizeof(double));
                test.InsertSort();
                            double test2[]={10.4,9.1,8.4,7,6,5,4,3,2,1};
                test.Set(test2,            sizeof(test2)/sizeof(double));
                test.ShellSort();
                            double test3[]={10.4,9.1,8.4,7,6,5,4,3,2,1};
                test.Set(test3,            sizeof(test3)/sizeof(double));
                test.BubbleSort();
                            double test4[]={10.4,9.1,8.4,7,6,5,4,3,2,1};
                test.Set(test4,            sizeof(test4)/sizeof(double));
                test.QuickSort();
                            double test5[]={10.4,9.1,8.4,7,6,5,4,3,2,1};
                test.Set(test5,            sizeof(test5)/sizeof(double));
                test.SelectSort();
                            double test6[]={10.4,9.1,8.4,7,6,5,4,3,2,1};
                test.Set(test6,            sizeof(test6)/sizeof(double));
                test.HeapSort();
                            double test7[]={10.4,9.1,8.4,7,6,5,4,3,2,1};
                test.Set(test7,            sizeof(test7)/sizeof(double));
                test.MergeSort();
                            return 0;
            }






            

            如果您認為還可以改進的話 請留言告訴我:-)

		
            
			posted on 2009-05-07 18:54 abilitytao 閱讀(1879) 評論(14)  編輯 收藏 引用  
		
            
	
            
	
	





            
	    
    


            

            評論
            
	
	
			
            
				# re: SortWizard(排序精靈）——我的排序類
					
						2009-05-07 20:55
					
				adon
			
            
			
            
				我想遞減怎么辦  回復  更多評論
				  
			
            
		
			
            
				# re: SortWizard(排序精靈）——我的排序類
					
						2009-05-07 21:55
					
				zhaoyg
			
            
			
            
				博主可否做成成員函數是模板函數的非模板類，這樣可以用一個對象來處理所有類型的排序  回復  更多評論
				  
			
            
		
			
            
				# re: SortWizard(排序精靈）——我的排序類
					
						2009-05-07 22:41
					
				abilitytao
			
            
			
            
				@adon

            不知道您有什么高見呢 我現在的方法是 重載運算符 不過這個對基本數據類型不管用  回復  更多評論
				  
			
            
		
			
            
				# re: SortWizard(排序精靈）——我的排序類
					
						2009-05-07 22:47
					
				abilitytao
			
            
			
            
				@zhaoyg

            您的意思是不是讓我拿掉私有成員變量？把它作為類里面函數的參數？  回復  更多評論
				  
			
            
		
			
            
				# re: SortWizard(排序精靈）——我的排序類
					
						2009-05-08 12:45
					
				zhaoyg
			
            
			
            
				@abilitytao

            恩,是這樣的.

            不知你意下如何  回復  更多評論
				  
			
            
		
			
            
				# re: SortWizard(排序精靈）——我的排序類
					
						2009-05-08 12:47
					
				zhaoyg
			
            
			
            
				不過感覺像我這樣一弄，好像也就沒必要造這個類了，直接用庫函數就是了。  回復  更多評論
				  
			
            
		
			
            
				# re: SortWizard(排序精靈）——我的排序類[未登錄]
					
						2009-05-08 12:58
					
				Charlie
			
            
			
            
				@abilitytao
            可以使用policy based做比較

            template<typename element_t>
            struct less_than {
              static bool compare(const element_t lhs, const element_t rhs) {
                return lhs<rhs;
              }
            };

            template<typename element_t, typename cmp_policy = less_than<element_t> >
            struct sort_wirzad {
              void easy_sort() {
                ...
                //做比較
                if ( cmp_policy::compare(e1,e2) ) { /* do sth */ }
              }
            };

            用戶可以自定義自己的 compare_policy
            比如定義一個 greater_than 可以這樣傳遞給sort_wizard:

            sort_wizard<int,greater_than> instance;  回復  更多評論
				  
			
            
		
			
            
				# re: SortWizard(排序精靈）——我的排序類
					
						2009-05-08 15:36
					
				abilitytao
			
            
			
            
				@Charlie

            這個就是常用的cmp函數吧 呵呵 我還不是很理解呢   回復  更多評論
				  
			
            
		
			
            
				# re: SortWizard(排序精靈）——我的排序類
					
						2009-05-08 20:07
					
				Chuck
			
            
			
            
				
            @abilitytao
            這招很常用……特別是對使用模版的程序
            假想我做了一個高精度整數類，這個整數在C++里面用字符串來表示字面值，我做一個累加的程序，當然是泛型的~
            這些東西存在一個std::vector里面
            

            template<typename element_t>
            struct accum {
              static element_t accumlate(const std::vector<element_t>& container) {
                std::vector<element_t>::const_iterator i = container.begin();
                std::vector<element_t>::const_iterator end = container.end();
                
                element_t total = 0; /***注意這一行***/
                while ( i != end ) {
                  total += *i;
                  ++i;
                }
              }
            };
            

            前面的total = 0 對于普通數值類型不會出錯，但是如果是對于我的big_int類
            要把big_int初始化為0，應該是：
            

            big_int = "0";
            

            那么這個accum就不管用了
            

            該怎么辦呢？ 利用一個東西來完成……
            

            template<typename element_t>
            struct init_zero {
              static element_t zero() {
                return 0;
              }
            };
            


            // 一個偏特化
            template<>
            struct init_zero<big_int> {
              static big_int zero() {
                return big_int("0");
              }
            };
            

            那么之前的代碼就可以寫成這樣：
            

            template<typename element_t, typename init_zeror = init_zero<element_t> >
            struct accum {
              static element_t accumlate(const std::vector<element_t>& container) {
                std::vector<element_t>::const_iterator i = container.begin();
                std::vector<element_t>::const_iterator end = container.end();
                
                element_t total = init_zeror::zero();
                while ( i != end ) {
                  total += *i;
                  ++i;
                }
              }
            };
            
  回復  更多評論
				  
			
            
		
			
            
				# re: SortWizard(排序精靈）——我的排序類
					
						2009-05-08 20:08
					
				Chuck
			
            
			
            
				
            by the way
            

            我是之前那個charlie
            
  回復  更多評論
				  
			
            
		
			
            
				# re: SortWizard(排序精靈）——我的排序類
					
						2009-05-08 20:10
					
				Chuck
			
            
			
            
				哦~ 我忘記return total了~ 不好意思~ 不傷大雅就OK~  回復  更多評論
				  
			
            
		
			
            
				# re: SortWizard(排序精靈）——我的排序類
					
						2009-05-08 21:41
					
				abilitytao
			
            
			
            
				@Chuck

            多謝呵 講解的很詳細:-) 

            PS:話說BIG_INT我也有一個 不過要是有高精浮點類就好了 呵呵  回復  更多評論
				  
			
            
		
			
            
				# re: SortWizard(排序精靈）——我的排序類
					
						2009-11-20 12:11
					
				tiny
			
            
			
            
				qsort

            實現的太過簡單。。。。。。沒啥實際價值。  回復  更多評論
				  
			
            
		
			
            
				# re: SortWizard(排序精靈）——我的排序類[未登錄]
					
						2009-11-21 19:42
					
				abilitytao
			
            
			
            
				@tiny

            請問您有什么改進的建議嗎 當時寫這個只是為了完成數據結構的作業呢 呵呵  回復  更多評論
				  
			
            
		

            




            






            

				

            


    
    







            
	   
	



区久久AAA片69亚洲|
久久这里只有精品久久|
四虎国产永久免费久久|
久久91精品国产91久久小草
|
久久天天躁狠狠躁夜夜av浪潮|
久久久精品2019免费观看|
久久精品午夜一区二区福利|
少妇熟女久久综合网色欲|
久久精品国产久精国产果冻传媒|
久久久国产99久久国产一|
久久精品国产免费观看三人同眠|
伊人久久大香线焦AV综合影院
|
国产精品久久久久影视不卡|
久久91综合国产91久久精品|
成人精品一区二区久久久|
精品综合久久久久久88小说|
一本大道久久东京热无码AV|
狠狠色噜噜色狠狠狠综合久久|
久久综合噜噜激激的五月天|
色综合久久88色综合天天
|
久久精品国产福利国产琪琪|
久久精品视频一|
韩国免费A级毛片久久|
久久国产成人午夜aⅴ影院|
久久强奷乱码老熟女网站
|
久久www免费人成看片|
久久亚洲精品视频|
久久久久久国产精品美女|
国产精品一久久香蕉国产线看
|
国产免费久久精品99久久|
久久婷婷是五月综合色狠狠|
avtt天堂网久久精品|
久久综合日本熟妇|
久久国产精品久久久|
久久精品日日躁夜夜躁欧美|
久久精品国产精品亚洲人人|
久久久女人与动物群交毛片
|
久久精品国产91久久综合麻豆自制|
久久久久无码中|
国产精品久久久久久久久鸭|
久久精品aⅴ无码中文字字幕不卡|