本文共 4946 字，大约阅读时间需要 16 分钟。

• 没有实现计数、基数排序等线性复杂度的算法；
• 各算法只是对算法思想的一次简单模拟，没有过多的优化；
• 各排序主程序接口参数均为整型数组及元素个数；
• 程序计时使用了glibc的gettimeofday()，因此。。。；
• 归并排序中，每次调用都申请和释放堆空间，因此比较耗时。可以采用原地归并、使用全局/静态的方法加以优化；
• 快速排序中，对待排子序列的长度进行的了判断，对短序列进行优先排序可以减小函数的递归深度（而不是次数）；
• 希尔排序中，为了简洁，步长因子统一取做2.2（11/5）。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
          //~ gettimeofday() typedef void (*SORTFUN)(int *a, int n); #define ASIZE 24*1024 //~ array size#define SCOUNT 6 //~ number of sort methodenum {BUBBLE, INSERT, QSORT, HEAP, MERGE, SHELL};char *fname[SCOUNT] = { "Bubble", "Insert", "Qsort", "Heap", "Merge", "Shell" }; SORTFUN fpointer[SCOUNT]; //~ pointers to sort functions int array[SCOUNT][ASIZE]; //~ array(s) under sort. long timeused[SCOUNT]; //~ time taken by every sort function /*******************Generate random data*********************/voidgen_data(void){ srand(time(NULL)); //~ rand seeding for(int i = 0; i < ASIZE; ++i) //~ generate random array[0] { array[0][i] = rand() % ASIZE; } for(int i = 1; i < SCOUNT; ++i) //~ copy array[0] to the rest { for(int j = 0; j < ASIZE; ++j) { array[i][j] = array[i-1][j]; } } //NOTE: using TWO loops to maximize caching} /***********************Time the time**********************/longtimer(void) //~ Current Time by millisecond{ struct timeval tv; gettimeofday(&tv, NULL); return (tv.tv_sec * 1000 + tv.tv_usec / 1000);}intmain(int AC, char **AV) //~ Both of AC and AV are fascinating ^_^{ gen_data(); //NOTE: to disable a function, just comment it out below. fpointer[BUBBLE] = bubble_sort; fpointer[INSERT] = insert_sort; fpointer[QSORT] = quick_sort; fpointer[HEAP] = heap_sort; fpointer[MERGE] = merge_sort; fpointer[SHELL] = shell_sort; for(int i = 0; i < SCOUNT; ++i) { long starttime = timer(); SORTFUN fp = fpointer[i]; if(fp) fp(array[i], ASIZE); timeused[i] = timer() - starttime; } //~ Header printf("%%Method\t\t%%Time\t\t%%Elements\n"); printf("-----------------------------------------\n"); //~ result for(int i = 0; i < SCOUNT; ++i) { printf("%s\t\t%ld\t\t%d\n", fname[i], timeused[i], ASIZE); } printf("\n"); return 0;}　　各种排序，/************************Bubble Sort**************************/voidbubble_sort(int *a, int n){ for(int i = n - 1; i > 0; --i) { int issorted = 0; //~ flag, for some optimition for(int j = 0; j < i; ++j) { if(a[j] > a[j+1]) { issorted = 1; int tmp = a[j]; a[j] = a[j+1]; a[j+1] = tmp; } } if(!issorted) break; }} /************************Insert Sort**************************/voidinsert_sort(int *a, int n){ for(int i = 0; i < n - 1; ++i) { int j = i + 1; int tmp = a[j]; while(j > 0 && tmp < a[j-1]) { a[j] = a[j-1]; --j; } a[j] = tmp; }} /************************Quick Sort**************************/intpartition(int *a, int n) //~ seperate a[], using a[0] as pivot{ int l = 0, r = n; int pivot = a[l]; while(l < r) { while( l < r && a[--r] > pivot) ; a[l] = a[r]; while(l < r && a[++l] < pivot) ; a[r] = a[l]; } a[l] = pivot; return l; //~ return the final index of pivot}voidquick_sort(int *a, int n){ if(n <= 1) return; int m = partition(a, n); if(m <= n / 2) { quick_sort(a, m); quick_sort(a + m + 1, n - m - 1); } else { quick_sort(a + m + 1, n - m - 1); quick_sort(a, m); }} /************************Quik Sort**************************/voidsift(int *a, int i, int n) //~ sift to rebuild the heap rooted by a[i]{ int tmp = a[i]; while(2*i + 1 < n) { int j = 2*i + 1; if(j + 1 < n && a[j+1] > a[j]) ++j; if(a[j] > tmp) { a[i] = a[j]; i = j; } else break; } a[i] = tmp;}voidheap_sort(int *a, int n){ for(int i = (n-2) / 2; i >= 0; --i) //~ build heap { sift(a, i, n); } for(int i = 1; i < n; ++i) //~ rebuild the decreasing heap over and over { int tmp = a[0]; a[0] = a[n-i]; a[n-i] = tmp; sift(a, 0, n - i); }} /***********************Merge Sort**********************/voidmerge_sort(int *a, int n){ if(n == 1) return; int *ext = (int*)malloc(sizeof(int) * n / 2); merge_sort(a, n / 2); merge_sort(a + n / 2, (n + 1) / 2); memcpy(ext, a, n / 2 * sizeof(int)); int i = 0, j = n / 2, k = 0; while(i < n / 2 && j < n) { if(a[j] < ext[i]) a[k++] = a[j++]; else a[k++] = ext[i++]; } while(i < n / 2) a[k++] = ext[i++]; while(j < n) a[k++] = a[j++]; free(ext);} /***********************Shell Sort**********************/voidshell_sort(int * a, int n){ int step = n / 2; while(step > 0) { for(int i = step; i < n; ++i) { int tmp = *(a + i); int j = i - step; while(j >= 0 && tmp < *(a + j)) { *(a + j + step) = *(a + j); j -= step; } *(a + j + step) = tmp; } if(step == 2) step = 1; else step = step * 11 / 5; //~ integer is better }}
        
       
      
     
    
   

转载地址：https://blog.csdn.net/iteye_21199/article/details/82478687 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！