最近闲得无聊,就写了3个常用的排序算法来打发时间,只是能够实现其功能,尚不完善,先发上来做个备份。毕竟水平不济,写个程序太费劲了。
/*插入排序法*/template <class _T>void insert_sort( _T *array, int length ){ for ( int i = 1; i < length; i++ ) { _T key = array[i];
int j = i - 1; while ( j >= 0 && array[j] < key) { array[j+1] = array[j]; j--; } array[j+1] = key; }}
/*选择排序法*/template <class _T>void choose_sort( _T *array, int length){ for ( int i = 0; i < length - 1; i++) { _T key = array[i]; int index = i;
int j = i + 1; while ( j < length ) { if ( key > array[j]) { key = array[j]; index = j; } j++; } array[index] = array[i]; array[i] = key; }}
/*合并函数*/template <class _T>void merge( _T *array, int p, int q, int r ) /*对数组A[p.q.r]进行合并*/{ int n1 = q - p + 1; int n2 = r - q;
std::auto_ptr<_T> array_left( new _T[n1+1] ); std::auto_ptr<_T> array_right( new _T[n2+1] );
for (int i = 0; i < n1; i++) (array_left.get())[i] = array[ p + i ]; for (int j = 0; j < n2; j++) (array_right.get())[j] = array[ q + j + 1];
(array_left.get())[n1] = 11000; (array_right.get())[n2] = 11000;
i = j = 0; for (int k = p; k <= r; k++) { if ( (array_left.get())[i] < (array_right.get())[j] ) array[k] = (array_left.get())[i++]; else array[k] = (array_right.get())[j++]; }}/*合并排序法*/template <class _T>void merge_sort( _T *array, int p, int r ) /*对子数组A[p..r]排序*/{ if ( p < r ) { int q = ( p + r) / 2; merge_sort( array, p, q ); merge_sort( array, q+1, r ); merge( array, p, q, r ); }}