By SmartPtr(http://m.shnenglu.com/SmartPtr/)
這幾天在網(wǎng)上看到有人總結(jié)了4種比較常見(jiàn)簡(jiǎn)單的排序的算法，并用C#實(shí)現(xiàn)了出來(lái)。看了之后不由的想起了大學(xué)時(shí)候?qū)W<<數(shù)據(jù)結(jié)構(gòu)>>的情景， 忍不住用C++實(shí)現(xiàn)了一遍，除了冒泡排序， 選擇排序， 插入排序，希爾排序之外， 還包括了算法復(fù)雜度較好的快速排序與堆排序。 然后用C++強(qiáng)大的模板功能實(shí)現(xiàn)了一個(gè)基于policy的Sort函數(shù)， 很明顯，這個(gè)Sort函數(shù)是以排序算法為policy的。 這里利用了不同的模板技術(shù)實(shí)作出多個(gè)版本的Sort函數(shù)，并比較了它們的優(yōu)劣。
好了，閑話不說(shuō)， 下面給出6種排序算法， 每種算法用一個(gè)class包裝， 代碼的注釋?xiě)?yīng)該能很好的解釋這些算法。
// 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, 下面我們希望能用一個(gè)模板函數(shù)來(lái)靈活的調(diào)用這些算法，細(xì)細(xì)一看，我們有兩個(gè)參數(shù)：排序算法與被排序元素類型， 于是， 我們第一個(gè)Sort函數(shù)的版本應(yīng)聲而出：
// 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);
};
但是正如注釋中所言， 我們要這么調(diào)用這個(gè)函數(shù)：Sort1<BubbleSorter<int>, int>(list, sizof(list)/sizeof(list[0]))這么些模板參數(shù)要制定，實(shí)在是太不方便了， 而且我們可以看到這里兩個(gè)int就是冗余了，如果把他們寫(xiě)成不同的類型，就無(wú)法保證其正確性（或編譯或運(yùn)行）。我們有必要消除這個(gè)冗余, 也許你注意到SortPolicy中的那個(gè)int應(yīng)該可以由第二個(gè)模板T參數(shù)提供，一個(gè)模板參數(shù)由另一個(gè)模板參數(shù)決定，對(duì)， 我們需要的就是模板模板參數(shù)(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要好些了，但是因?yàn)槲覀冎纋ist的元素類型了，如果這個(gè)int能夠直接從list推出了， 我們就只需要寫(xiě)一個(gè)模板參數(shù)了，解決方法出奇的簡(jiǎn)單，調(diào)換模板參數(shù)的聲明順序：
// 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]));是不是很更簡(jiǎn)單了:)
當(dāng)然，C++中模板太靈活了， 我們還可以有其他實(shí)現(xiàn)，并且有的還不比Sort3這個(gè)版本差.(如下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);
};
代碼應(yīng)該能很好的解釋它自己了。當(dāng)然，它還不能從list的元素類型來(lái)推出SortPolicy類的模板參數(shù)類型。下一個(gè)版本Sort5, 可以與Sort3相媲美， 它采用的是成員模板參數(shù)：
//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函數(shù)為成員模板函數(shù)。這樣，該模板函數(shù)就能根據(jù)其參數(shù)list元素類型推導(dǎo)其模板參數(shù)類型。
具體使用如下：
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[] = {1, 2, 5, 7, 0, 12, 67, 0, 0 ,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++模板的應(yīng)用，在此完成結(jié)合。
改進(jìn)建議：
1. 交換兩個(gè)元素最好用std::swap
這里，我交換兩個(gè)元素的代碼是：
int tmp = list[j+1];
list[j+1] = list[j];
list[j] = tmp;
除了沒(méi)有用swap外，還有一個(gè)致命的錯(cuò)誤就是直接寫(xiě)了int, 而不是模板類型T，這是因?yàn)榭紤]不仔細(xì)，且測(cè)試不完全(只測(cè)試了int一種類型)所導(dǎo)致的。
2. 因?yàn)楦鱾€(gè)排序類并不存儲(chǔ)任何數(shù)據(jù)，其存在的意義就在于區(qū)別算法類型，因此可以把所有函數(shù)聲明為static，這樣在排序模板函數(shù)中調(diào)用時(shí)只要直接調(diào)用static函數(shù)，而不用生成一個(gè)排序類的對(duì)象了。以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 閱讀(1776)
評(píng)論(9) 編輯 收藏 引用