Sort for Fun!

来源:转载

看到园子里有人发排序算法的随笔,想起之前发现的一个好网页,日本人写的,用脚本编写的一个算法柱形图演示,很是形象。趁着一时的兴趣,也就自己写了个程序,希望能通过终端实现类似的演示效果。写了一半,最后的图形显示遇到点小麻烦,之后也就忙的没再解决。

程序也简单,将不同的算法模块加进去,比较不同的算法的排序效率。当一百万的随机数用快排在数秒钟搞定,而其他则是花费数倍,甚至十几倍的时间才能出结果时,“效率”两个字便突然间有了很重要的地位。花时间在代码质量方面做做文章,虽不会有立竿见影的效果,但对一个人的编程态度会有很大的改观。米卢不是说了么:“态度决定一切”。

这个是日本人的那个网页链接:

http://jsdo.it/norahiko/oxIy/fullscreen

下面是我的这个小程序,随便一看。

#ifndef _HEAD_H_#define _HEAD_H_#include<stdio.h>#include<stdlib.h>#include<string.h>#include <unistd.h>#include <sys/times.h>#define FOR(i, count) / for(i = 0; i < count; ++i)#endif
#include"head.h"#define COUNT 1000000 //比较的数字个数,randArr[0]有其他用处。#define LEN (COUNT+1)#define ROW #define COL (COUNT+1)#define TIME_VALUE 200000 //改速度#define BLACK 40#define WHITE 47#define RED 41#define PURPLE 45#define GREEN 42#define BLUE 44#define BG BLACK#define FG WHITE int randArr[COUNT+1]; //randArr[0]有其他用处。int dlta[] = {5, 3, 1};typedef enum { StraightInsertion = 0, Shell = 1, Quick = 2, Merge = 3, Bubble = 4, Heap = 5, /*添加算法标志*/}SORTING_STYPE;//------------------------------------------------------------------------typedef int* TYPE; int swap(TYPE a, TYPE b){ *a ^= *b; *b ^= *a; *a ^= *b; return 0;}//------------------------------------------------------------------------void _draw_clr(int which) //which: 把第几个柱子清除{ int i, j; /*draw column*/ FOR(j, ROW) { printf("/33[%d;%dH", j, which); printf("/33[%dm /33[0m", BG); } printf("/33[%d;%dH", ROW, which);}void _draw_col(int which, int color ) //以何种颜色显示第几根柱子{ int i, j; /*clear column*/ _draw_clr(which); /*draw column*/ FOR(j, randArr[which]) { printf("/33[%d;%dH", j, which); printf("/33[%dm /33[0m", color); } printf("/33[%d;%dH", ROW, which); usleep(TIME_VALUE);}//------------------------------------------------------------------------void drawArr(void){ int i, j;#if 0 /*clear and init tty*/ printf("/33[1;1H"); FOR(i, ROW) { FOR(j, COL) { printf("/33[%dm /33[0m", BG); } printf("/n"); } FOR(i, LEN) { FOR(j, randArr[i]) { printf("/33[%d;%dH", j, i+1); printf("/33[%dm /33[0m", FG); } } printf("/33[%d;%dH", ROW-2, 0);#endif#if 1 FOR(j, COUNT) { printf("randArr[%d] = %d/n", j+1, randArr[j+1]); }#endif}void init(void){ int i = 0, j = 0; srand(getpid()); /*80 number*/ FOR(i, COUNT) { randArr[i+1] = rand() % ROW + 1; //randArr[i+1] = i; } //drawArr();}//------------------------------------------------------------------------/*排序参数简化,查找参数要全*//*查找*/int Search_Bin(int low, int high, int key){ int mid = 0; while (low < high) { mid = (low + high) >> 1; if (randArr[mid] == key) { return mid; } else if (randArr[mid] > key) { high = mid - 1; } else { low = mid + 1; } } return 0;}//------------------------------------------------/*排序算法实现*//*排序的图形化演示,未实现,有兴趣可以一试*//*void InsertSort(void){ int i = 0, j = 0; for (i = 2; i <= COUNT; ++i) {_draw_col(i, RED);_draw_col(i-1, GREEN); if(randArr[i] < randArr[i-1]) //not ascend... {_draw_col(i-1, FG);//_draw_col(i-1, BLUE);_draw_clr(i); randArr[0] = randArr[i];_draw_col(0, RED);_draw_clr(i-1); randArr[i] = randArr[i-1];_draw_col(i, GREEN);_draw_col(i, FG); j = i - 1;_draw_col(0, RED);_draw_col(j, GREEN); while(randArr[0] < randArr[j]) {//_draw_col(0, BLUE);_draw_clr(j); randArr[j+1] = randArr[j];_draw_col(j+1, GREEN);_draw_col(i, FG); --j;_draw_col(0, RED);_draw_col(j, GREEN); }_draw_col(j, FG);_draw_clr(0); randArr[j+1] = randArr[0];_draw_col(j+1, RED); }_draw_col(i, FG);_draw_col(i-1, FG); }}*/void InsertSort(void){ int i = 0, j = 0; int tmp = 0; for (i = 2; i <= COUNT; ++i) { if(randArr[i] < randArr[i-1]) { /*放哨兵*/ randArr[0] = randArr[i]; /*找位置*/ j = i - 2; while(randArr[0] < randArr[j]) { --j; } /*整体移动,腾位置*/ tmp = i-1; while(j+1 <= tmp) { randArr[tmp+1] = randArr[tmp]; --tmp; } /*坐位置*/ randArr[j+1] = randArr[0]; } }}//--------------------------------------------void ShellInsert(int dk){ int i = 0, j = 0; int tmp = 0; for (i = dk+1; i <= COUNT; ++i) { if(randArr[i] < randArr[i-1*dk]) { /*放哨兵*/ randArr[0] = randArr[i]; /*找位置*/ j = i - 2*dk; while(randArr[0] < randArr[j]) { j -= dk; } /*整体移动,腾位置*/ tmp = i - 1*dk; while(j+1*dk <= tmp) { randArr[tmp+1*dk] = randArr[tmp]; tmp -= dk; } /*坐位置*/ randArr[j+1*dk] = randArr[0]; } }}void ShellSort(void){ int k = 0; int t = 3; int shellArr[] = {5, 3, 1}; //按增量序列dlta[0..t-1]对顺序表作排序 for (k = 0; k < t; ++k) { ShellInsert(shellArr[k]); }}//------------------------------------------------------------------------int Partition2(int low, int high) //升级版, 取中值{ int tmp = 0; //= randArr[low]; int pivotkey = 0; //= randArr[low]; int mid = 0; mid = (low + high) / 2; swap(&randArr[mid], &randArr[low]); tmp = randArr[low]; pivotkey = randArr[low]; while(low < high) { while(low < high && randArr[high] >= pivotkey) { --high; } randArr[low] = randArr[high]; while(low < high && randArr[low] <= pivotkey) { ++low; } randArr[high] = randArr[low]; } randArr[low] = tmp; return low;}int Partition(int low, int high){ int tmp = randArr[low]; int pivotkey = randArr[low]; while(low < high) { while(low < high && randArr[high] >= pivotkey) { --high; } randArr[low] = randArr[high]; while(low < high && randArr[low] <= pivotkey) { ++low; } randArr[high] = randArr[low]; } randArr[low] = tmp; return low;}void QSort(int low, int high){ int pivotloc; if (low < high) { pivotloc = Partition2(low, high); QSort(low, pivotloc-1); QSort(pivotloc+1, high); }}void QuickSort2(void){ QSort(1, COUNT);}void QuickSort(void){ QSort(1, COUNT);}//------------------------------------------------------------------------void merge(int tmpArr[], int i, int m, int n){ int j = m + 1; int k = i; while(i <= m && j <= n) { if (randArr[i] < randArr[j]) { tmpArr[k++] = randArr[i++]; } else { tmpArr[k++] = randArr[j++]; } } while (i <= m) { tmpArr[k++] = randArr[i++]; } while (j <= n) { tmpArr[k++] = randArr[j++]; }}void copy(int mergeArr[], int l, int r){ int i; for( i = l ; i <= r; i ++ ){ randArr[i] = mergeArr[i]; }}void Msort(int mergeArr[], int left, int right){ int mid; if( left < right ) { mid = ( left + right ) / 2; Msort(mergeArr, left, mid ); Msort(mergeArr, mid + 1, right ); merge (mergeArr, left, mid, right ); copy(mergeArr, left, right ); } }void MergeSort(){ int randArrMerge[COUNT+1]; Msort(randArrMerge, 1, COUNT);}//------------------------------------------------------------------------void BubbleSort(void){ int i, j; FOR(i, COUNT-1) { FOR(j, COUNT - 1 - i) { swap(&randArr[j], &randArr[j+1]); } }}//------------------------------------------------------------------------/* i为根节点,n为节点总数...关键 */void sift(int a[], int i, int n){ int child, tmpParent; for (tmpParent = a[i]; n >= 2 * i; i = child) { /* i的左孩子为2*i,右孩子为2*i+1 */ child = 2 * i; /* 让child指向孩子中较大的一个 */ if (child != n && a[child + 1] > a[child]) { /*i*2之后且=n,表明为左孩子即当前末结点*/ child++; } /* 如果孩子节点大 */ if (tmpParent < a[child]) { /* 交换孩子节点和根节点 */ a[i] = a[child]; } else { /*若比孩子结点大,肯定比孙子大,则不用再比较*/ break; } } /* 将根放在合适位置, tmpParent无需每次移动 */ a[i] = tmpParent;}void heapsort(int a[], int n){ int i; /* 将a[1...n]建成大根堆 */ for (i = n / 2; i >= 1; i--) { sift(a, i, n); } /* 进行n-1趟排序 */ for (i = n; i >= 2; i--) { /* 交换堆顶元素和最后一个元素 */ swap(&a[1], &a[i]); /* 将a[1...i-1]重建为大顶堆 */ sift(a, 1, i-1); }} void HeapSort(void){ heapsort(randArr, COUNT);}//------------------------------------------------------------------------void do_job(int style){ switch(style) { case StraightInsertion: { fprintf(stderr, "/nStraight Insertion Sort:/n"); InsertSort(); break; } case Shell: { fprintf(stderr, "/nShell's Sort:/n"); ShellSort(); break; } case Quick: { fprintf(stderr, "/nQuick Sort:/n"); QuickSort(); break; } case Merge: //超过一百万 堆栈溢出 { fprintf(stderr, "/nMerge Sort:/n"); MergeSort(); break; } case Bubble: { fprintf(stderr, "/nBubble Sort:/n"); BubbleSort(); break; } case Heap: { fprintf(stderr, "/nHeap Sort:/n"); HeapSort(); break; } /*这里添加排序算法*/ default: { break; } }}//------------------------------------------------------------------------int main(void){ clock_t start, end; struct tms tms; int sct; int i; FOR(i, 6) { if (i == 0 || i == 1 || i == 4 || i == 5) //相当于算法控制开关 continue; init(); //drawArr(); start = times(NULL); //drawArr(); do_job(i); //drawArr(); sct = sysconf(_SC_CLK_TCK); end = times(&tms); printf("real: %f/n", (float)(end - start) / sct); printf("sys: %f/n", (float)tms.tms_stime / sct); printf("usr: %f/n", (float)tms.tms_utime / sct); } //drawArr(); return 0;}

分享给朋友:
您可能感兴趣的文章:
随机阅读: