各种排序算法的C++实现

wujiuliu 贡献于2013-06-01

作者 shilei  创建于2012-06-04 08:28:00   修改者shilei  修改于2012-06-04 09:42:00字数8678

文档摘要:各种排序算法的C++实现本程序实现数据结构中的常用排序算法,用标准C++函数模板编写,不依赖于任何平台和任何项目,已经在Codeblocks10.05(GCC4.5.1)和VS2010平台上测试通过。
关键词:

各种排序算法的C++实现 本程序实现数据结构中的常用排序算法,用标准C++函数模板编写,不依赖于任何平台和任何项目,已经在Codeblocks 10.05 (GCC4.5.1) 和VS2010平台上测试通过。 01/***************************************************************************** 02 * sort.h 03 * 04 * Some sort algorithms. 05 * 06 * This file includes several usually used sorting algorithm, such as: bubble 07 * sorting, selection sorting, insertion sorting, quick sorting, merging 08 * sorting, and heap sorting. 09 * 10 * Zhang Ming, 2010-07, Xi'an Jiaotong University. 11 *****************************************************************************/ 12 13 14 #ifndef SORT_H 15 #define SORT_H 16 17 18 #include 19 20 21 using namespace std; 22 23 24 namespace itlab 25 { 26 27 template void bubbleSort( vector&, int, int ); 28 template void selectSort( vector&, int, int ); 29 template void insertSort( vector&, int, int ); 30 template void quickSort( vector&, int, int ); 31 template void mergSort( vector&, int, int ); 32 template void heapSort( vector&, int, int ); 33 34 template const Type& median3( vector&, int, int ); 35 template void merg( vector&, int, int, int, int ); 36 template void filterDown( vector&, int, int ); 37 38 39 #include 40 41 } 42 // namespace itlab 43 44 45 #endif 46 // SORT_H 001 /***************************************************************************** 002 * sort-impl.h 004 * Implementation for sort algorithms. 007 *****************************************************************************/ 010 /** 011 * Bubble sort algorithm. // 012 * "a" ----> array of Comparable items. 013 * "left" ----> the left-most index of the subarray. 014 * "right" ----> the right-most index of the subarray. 015 */ 016 template 017 void bubbleSort( vector &a, int left, int right ) 018 { 019 bool cond; 020 for( int i=left; ii; --j ) 024 if( a[j] < a[j-1] ) 025 { 026 swap( a[j], a[j-1] ); 027 cond = true; 028 } 029 030 if( !cond ) 031 return; 032 } 033 } 034 036 /** 037 * Selection sort algorithm. 038 * "a" ----> array of Comparable items. 039 * "left" ----> the left-most index of the subarray. 040 * "right" ----> the right-most index of the subarray. 041 */ 042 template 043 void selectSort( vector &a, int left, int right ) 044 { 045 Type minPos; 046 for( int i=left; i array of Comparable items. 062 * "left" ----> the left-most index of the subarray. 063 * "right" ----> the right-most index of the subarray. 064 */ 065 template 066 void insertSort( vector &a, int left, int right ) 067 { 068 for( int p=left+1; p<=right; p++ ) 069 { 070 Type tmp = a[p]; 071 int j; 072 073 for( j=p; j>left && tmp array of Comparable items. 084 * "left" ----> the left-most index of the subarray. 085 * "right" ----> the right-most index of the subarray. 086 */ 087 template 088 void quickSort( vector &a, int left, int right ) 089 { 090 if( left+20 <= right ) 091 { 092 Type pivot = median3( a, left, right ); 094 // begin partitioning 095 int i = left, j = right-1; 096 for( ; ; ) 097 { 098 while( a[++i] < pivot ) { } 099 while( pivot < a[--j] ) { } 101 if( i < j ) 102 swap( a[i], a[j] ); 103 else 104 break; 105 } 107 // Restore pivot 108 swap( a[i], a[right-1] ); 110 // Sort small elements 111 quickSort( a, left, i-1 ); 113 // Sort large elements 114 quickSort( a, i+1, right ); 115 } 116 else 117 insertSort( a, left, right ); 118 } 121 /** 122 * Merg sort algorithm (nonrecursion). 123 * "a" ----> array of Comparable items. 124 * "left" ----> the left-most index of the subarray. 125 * "right" ----> the right-most index of the subarray.*/ 127 template 128 void mergSort( vector &a, int left, int right ) 129 { 130 int left1, right1, left2, right2, 131 n = right - left + 1, 132 size = 1; 134 while( size < n ) 135 { 136 left1 = left; 138 while( left1+size < n ) 139 { 140 left2 = left1+size; 141 right1 = left2-1; 142 if( left2+size > n ) 143 right2 = right; 144 else 145 right2 = left2+size-1; 147 merg( a, left1, right1, left2, right2 ); 149 left1 = right2+1; 150 } 152 size *= 2; 153 } 154 } 157 /*** Heap sort algorthm. 159 * "a" ----> array of Comparable items. 160 * "left" ----> the left-most index of the subarray. 161 * "right" ----> the right-most index of the subarray. */ 163 template 164 void heapSort( vector &a, int left, int right ) 165 { 166 int n = right-left+1; 167 vector tmp( n ); 168 for( int i=0; i=0; --i ) 172 filterDown( tmp, i, n ); 173 for( int j=n-1; j>0; --j ) 174 { 175 swap( tmp[0], tmp[j] ); 176 filterDown( tmp, 0, j ); 177 } 179 for( int i=0; i 189 const Type& median3( vector &a, int left, int right ) 190 { 191 int center = (left+right) / 2; 193 if( a[center] < a[left] ) 194 swap( a[left], a[center] ); 196 if( a[right] < a[left] ) 197 swap( a[left], a[right] ); 199 if( a[right] < a[center] ) 200 swap( a[center], a[right] ); 202 swap( a[center], a[right-1] ); 204 return a[right-1]; 205 } 208 /** 209 * Merg two subsequence to a bigger one. 210 * The first subsequence is a[left1] ... a[right1], and 211 * The second subsqeuence is a[left2] ... a[right2]. 212 */ 213 template 214 void merg( vector &a, int left1, int right1, int left2, int right2 ) 215 { 216 int k = 0, 217 i = left1, 218 j = left2, 219 n1 = right1-left1+1, 220 n2 = right2-left2+1; 222 Type *tmp = new Type[n1+n2]; 224 while( i <= right1 && j <= right2 ) 225 if( a[i] < a[j] ) 226 tmp[k++] = a[i++]; 227 else 228 tmp[k++] = a[j++]; 230 while( i <= right1 ) 231 tmp[k++] = a[i++]; 232 while( j <= right2 ) 233 tmp[k++] = a[j++]; 235 for( int i=0; i the position from which to percolate down. 247 * "n" ----> the logical size of the binary heap. 248 */ 249 template 250 void filterDown( vector &a, int i, int n ) 251 { 252 int child; 253 Type tmp; 255 for( tmp=a[i]; 2*i+1 11 #include 12 #include 15 using namespace std; 16 using namespace itlab; 19 const int SIZE = 10; 22 template 23 void printVector( const vector &a ) 24 { 25 vector::const_iterator itr = a.begin(); 26 while( itr != a.end() ) 27 cout << *itr++ << "\t"; 29 cout << endl; 30 } 33 int main() 34 { 35 vector a( SIZE ); 36 37 cout << "Unsorted Numbers : " << endl; 38 Random r(127); 39 for( unsigned i=0; i 21 using namespace std; 24 namespace splab 25 { 27 template void bubbleSort( vector&, int, int ); 28 template void selectSort( vector&, int, int ); 29 template void insertSort( vector&, int, int ); 30 template void quickSort( vector&, int, int ); 31 template void mergSort( vector&, int, int ); 32 template void heapSort( vector&, int, int ); 34 template const Type& median3( vector&, int, int ); 35 template void merg( vector&, int, int, int, int ); 36 template void filterDown( vector&, int, int ); 39 #include 41 } 42 // namespace splab 45 #endif 46 // SORT_H

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 2 金币 [ 分享文档获得金币 ] 0 人已下载

下载文档