SmartPtr
本博客已搬至:http://www.cnblogs.com/baiyanhuang/
posts - 29,comments - 176,trackbacks - 0
By SmartPtr(http://www.cppblog.com/SmartPtr/)

    这几天在网上看到有人总结了4种比较常见简单的排序的算法,并用C#实现了出来。看了之后不由的想起了大学时候学<<数据结构>>的情景, 忍不住用C++实现了一遍,除了冒泡排序, 选择排序, 插入排序,希尔排序之外, 还包括了算法复杂度较好的快速排序与堆排序。 然后用C++强大的模板功能实现了一个基于policy的Sort函数, 很明显,这个Sort函数是以排序算法为policy的。 这里利用了不同的模板技术实作出多个版本的Sort函数,并比较了它们的优劣。
好了,闲话不说, 下面给出6种排序算法, 每种算法用一个class包装, 代码的注释应该能很好的解释这些算法。

// sort type: bubble sort
// complexity: O(n^2)
// Algorithm: compare adjcent elements and swap if not meet the compare criterion.
template<typename T>
struct BubbleSorter
{
    
void Sort(T list[], int n)
    {
        
bool bIsDone = false;
        
for(int i = n-1; i > 0 && !bIsDone; --i)
        {
            bIsDone 
= true// if no sway happened, then this list is already sorted.
            for(int j = 0; j < i; ++j)
            {
                
if(list[j+1< list[j])
                {
                    bIsDone 
= false

                    
int tmp = list[j+1];
                    list[j
+1= list[j];
                    list[j] 
= tmp;
                }
            }
        }
    }
};

// sort type: selection sort
// complexity: O(n^2)
// Algorithm: select the minimum element and move it to the front.
template<typename T>
struct SelectionSorter
{
    
void Sort(T list[], int n)
    {
        
int nIndexOfMin;
        
for(int i = 0; i < n-1++i)
        {
            nIndexOfMin 
= i;
            
for(int j = i+1; j < n; ++j)
            {
                
if(list[j] < list[nIndexOfMin])
                    nIndexOfMin 
= j;
            }

            
// swap the minimum element with the front element
            if(nIndexOfMin != i)
            {
                
int tmp = list[i];
                list[i] 
= list[nIndexOfMin];
                list[nIndexOfMin] 
= tmp;
            }
            
        }
    }
};

// sort type: insert sort
// complexity: O(n^2)
// Algorithm:  insert the n+1 element to an already sorted n element array
template <typename T>
struct InsertionSorter
{
    
void Sort(T list[], int n)
    {
        
for(int i = 1; i <= n-1++i)
        {
            
int nInsert = list[i];
            
int j = i - 1;
            
while(j >= 0 && list[j] > nInsert)
            {
                list[j
+1= list[j];
                
--j;
            }
            list[j
+1= nInsert;
        }
    }
};


// sort type: shell sort
// complexity: O(n^1.5...)
// Algorithm:  separate the list into several sublist and sort them respectively
// then decrease the number of sublist and sort until only one sublist.
template <typename T>
struct ShellSorter
{
    
void Sort(T list[], int n)
    {
        
int gap = n / 2;
        
// decrease the gap: gap = gap / 2
        while(gap > 0)
        {
            
// insertion sort in each gap
            
// in first execution, gap is the second sublist's first element
            for(int i = gap; i <= n-1++i) // sub list execute insertion sort in turn.
            {
                
int tmp = list[i];  // store the element to insert
                int j = i;
                
while(j >= gap && list[j-gap] > tmp) // important: j >= gap, or else j<0 when out of the loop
                {
                    list[j] 
= list[j-gap];
                    j 
= j-gap;
                }
                list[j] 
= tmp;
            }

            gap 
/= 2// decrease gap
        }
    }
};

// sort type: quick sort
// complexity: O(n*logn)
// Algorithm: partite the list in 2 sub list based on its first element, pivot, one list greater than pivot
// and another less than pivot, this time pivot is in this right position. do this to each sublist recusively
// until the sublist length equals 0
template <typename T>
struct QuickSorter
{
    
void Sort(T list[], int n)
    {
        QuickSort(list, 
0, n-1);
    }

private:
    
// partite the list in 2 sublists, nPivot will be in the right position.
    int Partition(T list[], int low, int high)
    {
        
int nPivot = list[low];
        
int nPivotPos = low;
        
for(int i = low + 1; i <= high ; ++i)
        {
            
if(list[i] < nPivot && ++nPivotPos != i) //++pivotpos != i is very tricky
            {
                
int tmp = list[nPivotPos];
                list[nPivotPos] 
= list[i];
                list[i] 
= tmp;
            }
        }
        
// in the previous loop, we just calculate the final pivot position and move the large number
        
// to the 2nd sublist, small number to the 1st sublist by swap. and after doing that, we put the 
        
// pivot in the right position here.
        int t = list[nPivotPos];
        list[nPivotPos] 
= list[low];
        list[low] 
= t;

        
return nPivotPos;
    }

    
void QuickSort(T list[], int first, int last)
    {
        
if(first < last)// end condition-this sublist just has 1 element
        {
            
int nPivotPos = Partition(list, first, last);
            QuickSort(list, first, nPivotPos
-1);
            QuickSort(list, nPivotPos
+1, last);
        }
    }
};


// sort type: Heap sort
// complexity: O(n*logn)
// Algorithm: construct a max heap from the list, swap the first element (the heap root) with the last
// element. adjust the previous (n-1) elements to a heap again and swap to its end again, do it 
// until the heap has only one element
template <typename T>
struct HeapSorter
{
    
void Sort(T list[], int n)
    {
        
// make the heap. n/2 is the last non-leaf node.
        for(int i = n / 2; i >= 0--i) FilterDown(list, i, n-1);

        
// move the root element (the last) to the end one by one as the heap decrease its size...
        for(int i = n-1; i >= 1--i)
        {
            
int tmp = list[0];
            list[
0= list[i];
            list[i] 
= tmp;
            
            
// adjust the heap to be a max heap
            FilterDown(list, 0, i-1);
        }
    }

private:
    
void FilterDown(T list[], int nStart, int nEndOfHeap)
    {
        
int i = nStart, j = 2*i+1;
        
int temp = list[i];
        
while(j <= nEndOfHeap)
        {
            
if(j+1 <= nEndOfHeap && list[j] < list[j+1]) j++;  //get the larger subnode
            if(temp >= list[j]) break;  // do we need swap the larger subnode with the parent node
            else{list[i] = list[j]; i = j; j = 2*i+1;} // adjust its subnode because it is modified
        }
        list[i] 
= temp;
    }
};

OK, 下面我们希望能用一个模板函数来灵活的调用这些算法,细细一看,我们有两个参数:排序算法与被排序元素类型, 于是, 我们第一个Sort函数的版本应声而出:

// trick: normal template parameter
// usage: Sort1<BubbleSorter<int>, int>(list, sizof(list)/sizeof(list[0]));
template <class SortPolicy, typename T>
void Sort1(T list[], int n)
{
    SortPolicy().Sort(list, n);
};

但是正如注释中所言, 我们要这么调用这个函数:Sort1<BubbleSorter<int>, int>(list, sizof(list)/sizeof(list[0]))这么些模板参数要制定,实在是太不方便了, 而且我们可以看到这里两个int就是冗余了,如果把他们写成不同的类型,就无法保证其正确性(或编译或运行)。我们有必要消除这个冗余, 也许你注意到SortPolicy中的那个int应该可以由第二个模板T参数提供,一个模板参数由另一个模板参数决定,对, 我们需要的就是模板模板参数(template template paramter):

// trick: template template paramter
// usage: Sort2<int, BubbleSorter>(list, sizeof(list)/sizeof(list[0]));
template<typename T, template <typename U> class SortPolicy>
void Sort2(T list[], int n)
{
    SortPolicy
<T>().Sort(list, n);
}

这样我们就可以这么使用: Sort2<int, BubbleSorter>(list, sizeof(list)/sizeof(list[0])); 嗯, 比Sort1要好些了,但是因为我们知道list的元素类型了,如果这个int能够直接从list推出了, 我们就只需要写一个模板参数了,解决方法出奇的简单,调换模板参数的声明顺序:

// trick: template template paramter, make the second parameter deduced fromt the parameter
// usage: Sort3<BubbleSorter>(list, sizeof(list)/sizeof(list[0]));
template<template <typename U> class SortPolicy, typename T>
void Sort3(T list[], int n)
{
    SortPolicy
<T>().Sort(list, n);
}

试试Sort3<BubbleSorter>(list, sizeof(list)/sizeof(list[0]));是不是很更简单了:)

当然,C++中模板太灵活了, 我们还可以有其他实现,并且有的还不比Sort3这个版本差.(如下Sort5). 首先, Sort4用了类似于trait的技巧,排序的元素类型从排序的类中得出:

//to use this sort function, define sort classes like this:
//template<typename T>
//struct BubbleSorter
//{
//    typedef T elementtype;
//    void Sort(T list[], int n){...}
//};
// trick: type trait
// usage: Sort4<BubbleSorter<int> >(list, sizeof(list)/sizeof(list[0]));
template<class SortPolicy>
void Sort4(typename SortPolicy::elementtype list[], int n)
{
    SortPolicy().Sort(list, n);
};

代码应该能很好的解释它自己了。当然,它还不能从list的元素类型来推出SortPolicy类的模板参数类型。下一个版本Sort5, 可以与Sort3相媲美, 它采用的是成员模板参数:

 

//to use this sort function, define sort classes like this:
//struct BubbleSorter
//{
//    template<typename T>
//    void Sort(T list[], int n){...}
//};
// trick: member template 
// usage: Sort5<BubbleSorter>(list, sizeof(list)/sizeof(list[0]));
template<class SortPolicy, typename T>
void Sort5(T list[], int n)
{
    SortPolicy().Sort(list, n);
}

这里, 我们的排序的类不再是模板类,但其Sort函数为成员模板函数。这样,该模板函数就能根据其参数list元素类型推导其模板参数类型。

具体使用如下:

 

template<typename T>
void Output(const string& strSortType, T list[], int n)
{
    cout
<<strSortType<<":";
    
for(int i = 0; i < n; ++i) cout<<list[i]<<" ";
    cout
<<endl;
}
int main(int argc, char *argv[])
{
    
int list[] = {12570126700 ,3,6,9};
    
int n = sizeof(list)/sizeof(list[0]);
    
//Bubble Sort
    Sort1<BubbleSorter<int>int>(list, n);    Output("Bubble Sort", list, n);
    Sort2
<int, BubbleSorter>(list, n);    Output("Bubble Sort", list, n);
    Sort3
<BubbleSorter>(list, n);                Output("Bubble Sort", list, n);
    
//Sort4<BubbleSorter<int> >(list, n);        Output("Bubble Sort", list, n);
    
//Sort5<BubbleSorter>(list, n);            Output("Bubble Sort", list, n);
    

    
//Quick Sort
    Sort1<QuickSorter<int>int>(list, n);    Output("Quick Sort", list, n);
    Sort2
<int, QuickSorter>(list, n);        Output("Quick Sort", list, n);
    Sort3
<QuickSorter>(list, n);                Output("Quick Sort", list, n);
    
//Sort2<QuickSorter<int> >(list, n);    Output("Quick Sort", list, n);
    
//Sort3<QuickSorter>(list, n);            Output("Quick Sort", list, n);
    
    
return 0;
}

好了,至此, 6种排序算法,5种C++模板的应用,在此完成结合。 

改进建议:
1. 交换两个元素最好用std::swap
这里,我交换两个元素的代码是:

  int tmp = list[j+1];
  list[j
+1= list[j];
  list[j] 
= tmp;

除了没有用swap外,还有一个致命的错误就是直接写了int, 而不是模板类型T,这是因为考虑不仔细,且测试不完全(只测试了int一种类型)所导致的。

2. 因为各个排序类并不存储任何数据,其存在的意义就在于区别算法类型,因此可以把所有函数声明为static,这样在排序模板函数中调用时只要直接调用static函数,而不用生成一个排序类的对象了。以Sort1为例:

// trick: normal template parameter
// usage: Sort1<BubbleSorter<int>, int>(list, sizof(list)/sizeof(list[0]));
template <class SortPolicy, typename T>
void Sort1(T list[], int n)
{
    SortPolicy::Sort(list, n);
};
posted on 2007-07-05 17:44 SmartPtr 阅读(1613) 评论(9)  编辑 收藏 引用

FeedBack:
# re: 经典排序算法的C++ template封装
2007-07-05 20:59 | czxskell
效率如何??
我以前写过,数据太多的话,效率还是大打折扣
还是c语言实现的最快  回复  更多评论
  
# re: 经典排序算法的C++ template封装
2007-07-05 21:56 | SmartPtr
为什么C实现会比这个快呢, 他们的区别在哪里, 是什么影响了其效率?  回复  更多评论
  
# re: 经典排序算法的C++ template封装
2007-07-05 23:27 | czxskell
不好意思,看错了,我以为你用了STL那一套东西,
这个不错哦,这个能否借用表达式模板呢?估计不知  回复  更多评论
  
# re: 经典排序算法的C++ template封装
2007-07-06 08:32 | SmartPtr
不好意思, 对表达式模板不太清楚, 可否介绍一下先?  回复  更多评论
  
# re: 经典排序算法的C++ template封装
2007-07-06 13:39 | SuperPlayeR
貌似第一个排序类 BubbleSorter中的
if(list[j+1] < list[j])
{
bIsDone = false;

int tmp = list[j+1];
list[j+1] = list[j];
list[j] = tmp;
}
其中int tmp应该是T tmp吧?
后面的用到交换的好像都有这个问题。
哦,原来作者在文章结尾的时候说明了,呵呵~~~怪我太着急还没看完就评论了。哎~下次要改掉这个坏习惯。  回复  更多评论
  
# re: 经典排序算法的C++ template封装
2007-07-06 22:50 | pass86
赞一个。  回复  更多评论
  
# re: 经典排序算法的C++ template封装
2007-07-08 01:54 | 天津大学计算机学院 常兴龙
很不错,赞一个!  回复  更多评论
  
# re: 经典排序算法的C++ template封装
2007-07-10 09:22 | anders06
Lz 可否考虑用template 模式实现呢  回复  更多评论
  
# re: 经典排序算法的C++ template封装
2007-07-10 10:11 | SmartPtr
To aders06:

你是说template method吗, 这么做有什么好处?  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理