By SmartPtr(http://www.shnenglu.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[] = {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++模板的應用，在此完成結合。
改進建議：
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 閱讀(1802)
評論(9) 編輯 收藏 引用