学步园

前一段时间需要任职资格考试，于是又拿起丢了几年的数据结构书看了看，温习了一下常见的几个排序算法。今天特把我写的学习代码贴了出来。

排序的算法常见有插入排序，选择排序与交换排序，较复杂一点还有归并排序与基数排序，概念性的东西我就不多说了，大家可以找一本严老师数据结构书看看。读大学时不觉得怎么样，现在再来看看，又结合这几年的编程经验，觉得写得还是蛮有水平的。

 1.先来一个排序中的比较函数子，实现是左值小于右值。

 template<typename T><br /> struct CmpFuctor<br /> {<br /> bool operator()(const T& lhs, const T& rhs)<br /> {<br /> return lhs < rhs;<br /> }<br /> };

 2.交换排序中用到的交换两个元素的函数。

 template<typename T><br /> void swap(T* lhs, T* rhs)<br /> {<br /> T tmp = *lhs;<br /> *lhs = *rhs;<br /> *rhs = tmp;<br /> }

 3.  排序前后，我们自然要观察前后元素的顺序，那也少了下面这个函数。即遍历整个数组，再回调函数指针func，把元素通过引用传递出来。

 template<typename T><br /> void traverse(T* pArray, const int size, void (*func)(T&) )<br /> {<br /> for(int idx =0; idx< size; idx++)<br /> {<br /> func(pArray[idx]);<br /> }<br /> }

 4.我们先来看一个最简单的插入排序。

 template<typename T, typename CMP ><br /> void insertsort(T* pArray, const int size, CMP cmp)<br /> {<br /> for(int idx =0; idx< size; idx++)<br /> {<br /> T temp = pArray[idx];<br /> int pos = idx -1;<br /> while( pos >= 0 && cmp(temp, pArray[pos]) ) // <<br /> {<br /> pArray[pos+1] = pArray[pos];<br /> pos--;<br /> }<br /> pArray[pos+1] = temp;<br /> }<br /> }<br />

 5.再对上面的插入排序改进，查找为折半插入排序。

 template<typename T, typename CMP><br /> void binaryinsertsort(T* pArray, const int size, CMP cmp)<br /> {<br /> for(int idx = 1; idx < size; idx++)<br /> {<br /> int left = 0;<br /> int right = idx -1;<br /> T temp = pArray[idx];<br /> while( left <= right)<br /> {<br /> int middle = (left + right) / 2;</p> <p> if ( cmp(temp, pArray[middle] )) // <<br /> {<br /> right = middle - 1;<br /> }<br /> else<br /> {<br /> left = middle + 1;<br /> }<br /> }</p> <p> int j = idx-1;<br /> for(; j >= right+1; j--)<br /> {<br /> pArray[j+1] = pArray[j];<br /> }<br /> pArray[right+1] = temp;</p> <p> }<br /> }

 6.再来一个改进版的插入排序。是希尔排序。希尔排序的基本思想是：先将整个待排记录序列分割成若干小组（子序列），分别在组内进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。 

 template<typename T, typename CMP><br /> void shellsort(T* pArray, const int size, CMP cmp)<br /> {<br /> int j = 0;<br /> int d = size / 2;</p> <p> //通过增量控制排序的执行过程<br /> while( d > 0 )<br /> {<br /> for(int i = d; i< size;i++)<br /> {<br /> j = i - d;<br /> while(j >= 0)<br /> {<br /> // 对各个分组进行处理<br /> if ( cmp(pArray[j+d], pArray[j]) )<br /> {<br /> swap(&pArray[j], &pArray[j+d]);<br /> j -= d;<br /> }<br /> else<br /> {<br /> j = -1;<br /> }<br /> }<br /> }<br /> d /= 2; //递减增量d<br /> }<br /> }

 7.下面是一种简单选择排序算法。

 template<typename T, typename CMP><br /> void selectsort(T* pArray, const int size, CMP cmp)<br /> {<br /> for(int idx = 0; idx < size; idx++)<br /> {<br /> for(int pos = idx + 1; pos < size; pos++)<br /> {<br /> if( cmp(pArray[pos], pArray[idx]) ) // <<br /> {<br /> swap(&pArray[pos], &pArray[idx]);<br /> }<br /> }<br /> }<br /> }

8.交换排序中最简单的冒泡排序。

 template<typename T, typename CMP><br /> void bubblesort(T* pArray, const int size, CMP cmp)<br /> {<br /> for(int idx =0; idx < size; idx++)<br /> {<br /> for(int pos = 0; pos <= size - idx;pos++)<br /> {<br /> if( cmp(pArray[pos+1], pArray[pos]) ) // <<br /> {</p> <p> swap(&pArray[pos], &pArray[pos+1]);<br /> }<br /> }<br /> }<br /> }

 9.交换排序中最简单的快速排序。

 template<typename T, typename CMP><br /> int partition(T* pArray, int p, int r, CMP cmp)<br /> {<br /> int i = p - 1;<br /> int j = 0;<br /> for(j = p; j < r; j++)<br /> {<br /> if(cmp(pArray[j], pArray[r])) //pArray[j] >= pArray[r]<br /> {<br /> i++;<br /> swap(&pArray[i], &pArray[j]);<br /> }<br /> }<br /> swap(&pArray[i + 1], &pArray[r]);<br /> return i + 1;<br /> }</p> <p>template<typename T, typename CMP><br /> void quicksort(T* pArray, int p, int r, CMP cmp)<br /> {<br /> int i = 0;<br /> if(p < r)<br /> {<br /> i = partition(pArray, p, r, cmp);<br /> quicksort(pArray, 0, i - 1, cmp);<br /> quicksort(pArray, i + 1, r, cmp);<br /> }<br /> }<br />

 10.测试代码

 void print(int& a)<br /> {<br /> printf("%d/t", a);<br /> }</p> <p>int genrandom(int min, int max)<br /> {<br /> return (min + (int)(((float)rand()/RAND_MAX)*(max - min)));<br /> }</p> <p>void random(int& a )<br /> {<br /> a = genrandom(-50, 100);<br /> }</p> <p>void sort_test()<br /> {<br /> int A[] = {4, 1, 44, -12, 5, 125, 30};<br /> int len = sizeof(A) / sizeof(int);<br /> //<br /> traverse(A, len, print);<br /> printf("/n");<br /> insertsort(A, len, CmpFuctor<int>() );<br /> traverse(A, len, print);<br /> printf("/n");</p> <p> //<br /> traverse(A, len, random);<br /> traverse(A, len, print);<br /> printf("/n");<br /> binaryinsertsort(A, len, CmpFuctor<int>() );<br /> traverse(A, len, print);<br /> printf("/n");</p> <p> //<br /> traverse(A, len, random);<br /> traverse(A, len, print);<br /> printf("/n");<br /> shellsort(A, len, CmpFuctor<int>() );<br /> traverse(A, len, print);<br /> printf("/n");</p> <p> //<br /> traverse(A, len, random);<br /> traverse(A, len, print);<br /> printf("/n");<br /> bubblesort(A, len, CmpFuctor<int>() );<br /> traverse(A, len, print);<br /> printf("/n");</p> <p> //<br /> traverse(A, len, random);<br /> traverse(A, len, print);<br /> printf("/n");<br /> selectsort(A, len, CmpFuctor<int>() );<br /> traverse(A, len, print);<br /> printf("/n");</p> <p> //<br /> traverse(A, len, random);<br /> traverse(A, len, print);<br /> printf("/n");<br /> quicksort(A, 0, len, CmpFuctor<int>() );<br /> traverse(A, len, print);<br /> printf("/n");</p> <p>}

Note: 上面的函数有C风格的函数指针与C++风格函数子（Functor，有时也叫函数对象），函数使用了C++中模板的一些特性，测试环境为eclipse+cdt+gcc。使用VC6的兄弟姐妹可能会编译不过，如其中的traverse(A, len, print);应该需要修改为traverse<int>(A, len, print);