以下是最近学习各种算法的代码实现：
#include#include #include #include typedef int EleType;typedef int (*CompFunc)(void *,void *);int IntComp(void * a,void *b){ if(*(int *)a > *(int *)b) return 1; if(*(int *)a == *(int *)b) return 0; if(*(int *)a < *(int *)b) return -1;}void insertion_sort(EleType A[],int N,CompFunc f){ int step; EleType tmp; int i; for(step = 1; step < N; ++step) { tmp = A[step]; for(i = step -1; i >= 0; --i) { if(f(&A[i],&tmp) > 0) { A[i+1] = A[i]; } else //退出！！！！！！！ break; } A[i+1] = tmp; }}void bubble_sort(EleType A[],int N,CompFunc f){ int step,i; EleType tmp; int flag = 0; for(step = 0; step < N-1; ++step) { flag = 0; for(i = N-1; i > step ; --i) { if(f(&A[i-1],&A[i]) > 0) { // swap tmp = A[i-1]; A[i-1] = A[i]; A[i] = tmp; flag = 1; } else continue; } if(!flag) break; }}void shell_sort(EleType A[],int N,CompFunc f){ int step,i,h; EleType tmp; // determine start of h for(h = 1; h < N/9; h = 3*h+1) ; for(; h >=1; h = h/3) { for(step = h; step < N; step++) { tmp = A[step]; for(i = step-h; i >=0; i-=h) { if( f(&tmp,&A[i]) <0 ) { A[i+h] = A[i]; }//退出 else break; } A[i+h] = tmp; } } }// heapsort// 第一个元素位置为0#define LeftChild(i) (2*(i)+1)void print_array(EleType A[],int N){ for(int i = 0; i < N; ++i) printf("%3d",A[i]); printf("\n");}void percdown(EleType A[],int i, int N,CompFunc f){ int Child; EleType tmp; for(tmp = A[i]; LeftChild(i) < N; i = Child) { Child = LeftChild(i); if(Child != N-1 && f(&A[Child+1] ,&A[Child])>0 ) Child++; if(f(&tmp,&A[Child]) < 0) A[i] = A[Child]; else break; } A[i] = tmp;}void heap_sort(EleType A[], int N,CompFunc f){ int i; EleType tmp; for(i = N/2; i >= 0; i--) { percdown(A,i,N,IntComp); //#ifdef DEBUG //print_array(A,N); //#endif } for(i = N-1; i > 0; i--) { tmp = A[i]; A[i] = A[0]; A[0] = tmp; percdown(A,0,i,IntComp); }}// quicksortint qsort_partition(EleType A[],int p,int q,CompFunc f){ int rd = (((double)rand())/((double)RAND_MAX))*(q-p) + p; EleType tmp; tmp = A[p]; A[p] = A[rd]; A[rd] = tmp; int i = p; int j = p+1; while(j <= q) { if( f(&A[p],&A[j]) > 0 ) { ++i; tmp = A[i]; A[i] = A[j]; A[j] = tmp; ++j; } else ++j; } tmp = A[i] ; A[i]=A[p]; A[p] = tmp; return i;}void qsort_recursion(EleType A[],int p, int q, CompFunc f){ if(p < q) { int r = qsort_partition(A,p,q,f); qsort_recursion(A,p,r-1,f); qsort_recursion(A,r+1,q,f); }}void quick_sort(EleType A[],int N,CompFunc f){ srand((unsigned int )time(NULL)); qsort_recursion(A,0,N-1,f);}// selection sortvoid selection_sort(EleType A[], int N, CompFunc f){ EleType tmp; int max_index; for(int i = N-1; i > 0; i--) { max_index = i; for(int j = 0; j < i; ++j) { if( f( &A[max_index] , &A[j] ) < 0 ) { max_index = j; } } tmp = A[max_index]; A[max_index] = A[i]; A[i] = tmp; }}// merge sortvoid merge_divide(EleType A[],int p, int q,CompFunc f){ if( q - p < 1 ) return ; // divide routine int mid = (p + q) /2; merge_divide(A, p , mid, f); merge_divide(A,mid+1, q, f); // merge routine int * tmp =(int *) malloc(sizeof(EleType) * (q - p + 1) ); int i, m, n; m = p; n = mid + 1; i = 0; while(m <= mid && n <= q) { if( f( &A[m], &A[n]) < 0) { tmp[i++] = A[m++]; }else { tmp[i++] = A[n++]; } } while(m <= mid) tmp[i++] = A[m++]; while(n <= q) tmp[i++] = A[n++]; if(i != q - p +1) { printf("Error: p = %d, q = %d\n",p,q); } // copy back int j = p; for(i = 0; i <= q-p; i++) { A[j++] =tmp[i]; } free(tmp);}void merge_sort(EleType A[], int N, CompFunc f){ merge_divide(A,0,N-1,f);}#define ITEMNUM 2000 int main() { int i; int A1[ITEMNUM ],A2[ ITEMNUM],A3 [ITEMNUM],A4[ITEMNUM]; srand((unsigned int )time( NULL)); for(i = 0; i < ITEMNUM; ++i ) { A4[i] = A1 [i]= A2[i]=A3 [i]= rand(); } clock_t start,finish; double d1,d2,d3,d4; merge_sort(A1,ITEMNUM,IntComp); quick_sort(A3,ITEMNUM,IntComp); shell_sort(A4,ITEMNUM,IntComp); for(i = 0; i < ITEMNUM; ++i ) { printf("%5d %5d %5d %5d\n",A2[i],A1[i],A3[i],A4[i]); } //insertion_sort(A1,ITEMNUM,IntComp); //bubble_sort(A2,ITEMNUM,IntComp);/* start = clock(); qsort(A1,ITEMNUM,sizeof(EleType),IntComp); finish = clock(); d1 = finish - start; start = clock(); quick_sort(A2,ITEMNUM,IntComp); finish = clock(); d2 = finish - start; start = clock(); shell_sort(A3,ITEMNUM,IntComp); finish = clock(); d3 = finish - start; start = clock(); heap_sort(A4,ITEMNUM,IntComp); finish = clock(); d4 = finish - start; printf("qsort time spending: %f\n",d1); printf("quick sort time spending:%f\n",d2); printf("shell sort time spending: %f\n", d3); printf("heap sort time spending: %f\n",d4); */ /* for(i = 0; i < ITEMNUM; ++i ) { printf ("%10d%10d%10d\n",A1[i ],A2[ i],A3[i ]); }*/// test heap sort/* int A[] = {3,5,6,8,9,4,1,7,2,0}; int N = sizeof(A)/sizeof(A[0]); print_array(A,N); heap_sort(A,N); printf("result:\n"); print_array(A,N); return 0;*/ }