Chinaunix首页 | 论坛 | 博客
  • 博客访问: 78812
  • 博文数量: 83
  • 博客积分: 10
  • 博客等级: 民兵
  • 技术积分: 20
  • 用 户 组: 普通用户
  • 注册时间: 2012-03-30 00:36
文章分类

全部博文(83)

文章存档

2014年(83)

我的朋友

分类: C/C++

2014-07-17 14:42:45

原文地址:10种常见排序算法实现 作者:bjpiao

点击(此处)折叠或打开

  1. #include <unistd.h>
  2. #include <stdlib.h>
  3. #include <stdio.h>
  4. #include <fcntl.h>
  5. #include <sched.h>
  6. #include <wait.h>
  7. #include <assert.h>
  8. #include <errno.h>
  9. #include <signal.h>
  10. #include <string.h>
  11. #include <pthread.h>

  12. #include <sys/mman.h>
  13. #include <sys/types.h>
  14. #include <sys/stat.h>
  15. #include <sys/time.h>
  16. #include <sys/resource.h>
  17. #include <sys/socket.h>

  18. #include <iostream>

  19. using namespace std;

  20. #define TIMER(val) do{
  21.         struct timeval tm;
  22.         gettimeofday(&tm, NULL);
  23.         val = tm.tv_sec * 1000 + tm.tv_usec/1000;
  24. }
  25. while(0)

  26. unsigned int seed = 0;

  27. int is_sorted(int *array, int size)
  28. {
  29.         int sorted = 1;
  30.         for(int i=0; i<size-1; i++)
  31.         {
  32.                 if(array[i]<=array[i+1])
  33.                         continue;
  34.                 else
  35.                 {
  36.                         sorted = 0;
  37.                         break;
  38.                 }
  39.         }
  40.         return sorted;
  41. }

  42. //insert sort
  43. int insert_sort(int array[], int size)
  44. {
  45.         for(int i=1; i<size; i++)
  46.         {
  47.                 int sentinel = array[i];
  48.                 int j;
  49.                 for(j=i-1; j>=0; j--)
  50.                 {
  51.                         if(sentinel < array[j])
  52.                         {
  53.                                 array[j+1] = array[j];
  54.                         }
  55.                         else
  56.                         {
  57.                                 break;
  58.                         }
  59.                 }
  60.                 if(j+1 != i)
  61.                         array[j+1] = sentinel;
  62.         }
  63.         assert(is_sorted(array, size)==1);
  64.         return 0;
  65. }

  66. //shell basic
  67. int shell_basic_sort(int array[], int size, int step)
  68. {
  69.         for(int i=1; i<=step; i++)
  70.         {
  71.                 //jump insert sort
  72.                 for(int j=i; j<=size; j+=step)
  73.                 {
  74.                         int sentinel = array[j-1];
  75.                         int k;
  76.                         for(k=j-step; k>=i; k-=step)
  77.                         {
  78.                                 if(sentinel < array[k-1])
  79.                                 {
  80.                                         array[k+step-1] = array[k-1];
  81.                                 }
  82.                                 else
  83.                                 {
  84.                                         break;
  85.                                 }
  86.                         }
  87.                         array[k+step-1] = sentinel;
  88.                 }
  89.         }
  90.         return 0;
  91. }

  92. int shell_sort(int array[], int size)
  93. {
  94.         int step = size;
  95.         while(step>=1)
  96.         {
  97.                 shell_basic_sort(array, size, step);
  98.                 step/=2;
  99.         }

  100.         assert(is_sorted(array, size)==1);
  101.         return 0;
  102. }

  103. void swap(int *a, int *b)
  104. {
  105.         int t = *a;
  106.         *a = *b;
  107.         *b = t;
  108. }


  109. //bubble sort
  110. int bubble_sort(int array[], int size)
  111. {
  112.         int sorted;

  113.         for(int i=size-1; i>0; i--)
  114.         {
  115.                 sorted = 1;
  116.                 for(int j=0; j<i; j++)
  117.                 {
  118.                         if(array[j] > array[j+1])
  119.                         {
  120.                                 swap(&array[j], &array[j+1]);
  121.                                 sorted = 0;
  122.                         }
  123.                 }
  124.                 if(1==sorted)
  125.                         break;
  126.         }

  127.         assert(is_sorted(array, size)==1);
  128.         return 0;
  129. }

  130. int pivot(int array[], int first, int last)
  131. {
  132.         int f = array[first];
  133.         while(first<last)
  134.         {

  135.                 while(first < last && array[last]>=f)
  136.                         last--;
  137.                 array[first] = array[last];
  138.                 while(first < last && array[first]<=f)
  139.                         first++;
  140.                 array[last] = array[first];
  141.         }
  142.         array[first] = f;
  143.         return;
  144. }


  145. int quick_sort(int array[], int first, int last)
  146. {
  147.         if(first>=last)
  148.                 return 0;

  149.         int size = last - first + 1;
  150.         int rand = (int)rand_r(&seed) % size;
  151.         swap(&array[first], &array[first+rand]);

  152.         int mid = pivot(array, first, last);
  153.         quick_sort(array, first, mid-1);
  154.         quick_sort(array, mid+1, last);
  155.         return 0;
  156. }

  157. typedef struct stack
  158. {
  159.         int low;
  160.         int high;
  161. }stack;

  162. int quick_sort2(int array[], int first, int last)
  163. {
  164.         int top = 0;
  165.         stack *pstack = (stack *)malloc(sizeof(stack) * (last-first+1));
  166.         if(pstack==NULL)
  167.                 return -1;
  168.         memset(pstack, (last-first+1), 0);

  169.         int size = last - first + 1;
  170.         int rand = (int)rand_r(&seed) % size;
  171.         swap(&array[first], &array[first+rand]);
  172.         int mid = pivot(array, first, last);

  173.         pstack[top].low = mid+1;
  174.         pstack[top].high = last;
  175.         top++;
  176.         //1

  177.         pstack[top].low = first;
  178.         pstack[top].high = mid-1;
  179.         top++;
  180.         //2

  181.         while(top>0)
  182.         {
  183.                 top--;
  184.                 int low = pstack[top].low;
  185.                 int high = pstack[top].high;
  186.                 if(low<high)
  187.                 {
  188.                         int size = high - low + 1;
  189.                         int rand = (int)rand_r(&seed) % size;
  190.                         swap(&array[low], &array[low+rand]);
  191.                         int mid = pivot(array, low, high);
  192.         
  193.                         pstack[top].low = mid+1;
  194.                         pstack[top].high = high;
  195.                         top++;

  196.                         pstack[top].low = low;
  197.                         pstack[top].high = mid-1;
  198.                         top++;
  199.                 }
  200.         }

  201.         free(pstack);
  202.         return 0;
  203. }

  204. int find_max(int array[], int size)
  205. {
  206.         int max_index = 0;
  207.         int sentinel = array[0];
  208.         for(int j=1; j<size; j++)
  209.         {
  210.                 if(array[j]>sentinel)
  211.                 {
  212.                         sentinel = array[j];
  213.                         max_index = j;
  214.                 }
  215.         }
  216.         return max_index;
  217. }

  218. int select_sort(int array[], int size)
  219. {
  220.         for(int i=size; i>=1; i--)
  221.         {
  222.                 int max_index = find_max(array, i);
  223.                 if(max_index!=i-1)
  224.                 {
  225.                         swap(&array[max_index], &array[i-1]);
  226.                 }
  227.         }
  228.         assert(is_sorted(array, size)==1);
  229.         return 0;
  230. }

  231. int heapify(int array[], int index, int size)
  232. {
  233.         while(index<=size/2)
  234.         {
  235.                 int left = 2*index;
  236.                 int right = left+1;
  237.                 int max_index = left;
  238.                 if( (right<=size) && array[left-1] < array[right-1])
  239.                         max_index = right;
  240.                 if(array[index-1] < array[max_index-1])
  241.                 {
  242.                         swap(&array[index-1], &array[max_index-1]);
  243.                         index = max_index;
  244.                 }
  245.                 else
  246.                         break;
  247.         }
  248.         return 0;
  249. }

  250. int heap_sort(int array[], int size)
  251. {
  252.         //build heap, heapify
  253.         int mid = size/2;
  254.         for(int i=mid; i>0; i--)
  255.                 heapify(array, i, size);
  256.         for(int i=size; i>0; )
  257.         {
  258.                 swap(&array[0], &array[i-1]);
  259.                 i--;
  260.                 if(i>0)
  261.                         heapify(array, 1, i);
  262.         }
  263.         assert(is_sorted(array, size)==1);
  264.         return 0;
  265. }

  266. //(start, mid-1)
  267. //(mid, end)
  268. int merge(int array[], int start, int mid, int end, int temparray[])
  269. {
  270.         int size1 = mid -start;
  271.         int size2 = end - mid +1;
  272.         int size = size1 > size2 ? size2 : size1;

  273.         int i,j,k;
  274.         i = j = k =0;
  275.         while( i<size1 && j<size2 )
  276.         {
  277.                 if(array[start+i] <array[mid+j])
  278.                 {
  279.                         temparray[j++] = array[start+i];
  280.                         i++;
  281.                 }
  282.                 else
  283.                 {
  284.                         temparray[j++] = array[mid+j];
  285.                         j++;
  286.                 }
  287.         }
  288.         if(i==size1)
  289.         {
  290.                 memcpy(array+size, &array[mid+j], size1-j);
  291.         }
  292.         else
  293.         {
  294.                 memcpy(array+size, &array[start+i], size1-i);
  295.         }
  296.         memcpy(array, temparray, sizeof(int)*size);
  297.         return 0;
  298. }


  299. int merge_sort(int array[], int start, int end, int temparray[])
  300. {
  301.         if(start>=end)
  302.                 return 0;

  303.         int size = end - start + 1;
  304.         int mid = start + size/2;

  305.         merge_sort(array, start, mid-1, temparray);
  306.         merge_sort(array, mid, end, temparray);
  307.         merge(array, start, mid, end, temparray);
  308.         return 0;
  309. }

  310. int Merge_sort(int array[], int start, int end)
  311. {
  312.         int size = end-start+1;
  313.         int *temparray = (int *)malloc(sizeof(int) *size);
  314.         assert(array!=NULL);
  315.         merge_sort(array, start, end, temparray);
  316.         free(temparray);
  317.         return 0;
  318. }


  319. ///////////////////////////////////////////////////////////////////////////////////////////////////////////
  320. typedef struct queue_elem
  321. {
  322.         int value;
  323.         struct queue_elem *next;
  324. }queue_elem;

  325. typedef struct queue
  326. {
  327.         queue_elem *first;
  328.         queue_elem *last;
  329.         int queue_size;
  330. }queue;

  331. typedef struct radix_queue
  332. {
  333.         queue qvalue[10];
  334. }radix_queue;

  335. radix_queue radix;
  336. queue_elem *g_alloc;
  337. int begin_alloc;
  338. int max_size;

  339. void init_queue_elm(queue_elem *qe)
  340. {
  341.         qe->value = 0;
  342.         qe->next = NULL;
  343. }

  344. int init_queue(queue *q)
  345. {
  346.         q->first = q->last = NULL;
  347.         q->queue_size = 0;
  348. }

  349. queue_elem *get_queue_elem()
  350. {
  351.         if(begin_alloc>=max_size)
  352.         {
  353.                 cout << "get queue elem error2" << endl;
  354.                 return NULL;
  355.         }
  356.         int curr = begin_alloc++;
  357.         queue_elem * p = g_alloc + curr;
  358.         init_queue_elm(p);
  359.         return p;
  360. }

  361. int init_radix(radix_queue *radix)
  362. {
  363.         for(int i=0; i<10; i++)
  364.                 init_queue(&radix->qvalue[i]);
  365. }

  366. int insert_queue(queue *q, int value)
  367. {
  368.         queue_elem *elem = get_queue_elem();
  369.         if(elem==NULL)
  370.         {
  371.                 cout << "get queue elem error" << endl;
  372.                 return -1;
  373.         }
  374.         elem->value = value;
  375.         elem->next = NULL;
  376.         if(q->queue_size==0)
  377.                 q->first = q->last = elem;
  378.         else
  379.                 q->last->next = elem;

  380.         q->last = elem;
  381.         q->queue_size++;
  382.         return 0;
  383. }
  384. int collect(radix_queue radix, int array[])
  385. {
  386.         int i = 0;
  387.         for(int j=0; j<10; j++)
  388.         {
  389.                 queue q = radix.qvalue[j];
  390.                 queue_elem *first = q.first;
  391.                 while(first!=NULL)
  392.                 {
  393.                         array[i++] = first->value;
  394.                         first = first->next;
  395.                 }
  396.         }
  397.         return 0;
  398. }

  399. int power(int base, int m)
  400. {
  401.         int value = 1;
  402.         for(int i=0; i<m; i++)
  403.                 value *= base;
  404.         return value;
  405. }

  406. int radix_sort(int array[], int size)
  407. {
  408.         max_size = size;
  409.         begin_alloc = 0;
  410.         g_alloc = (queue_elem *)malloc(sizeof(queue_elem) * size);
  411.         assert(g_alloc);

  412.         int maxvalue = array[0];
  413.         for(int i=1; i<size; i++)
  414.                 if(array[i]>maxvalue)
  415.                         maxvalue = array[i];
  416.         int max_step = 0;
  417.         while(maxvalue>0)
  418.         {
  419.                 max_step++;
  420.                 maxvalue = maxvalue/10;
  421.         }

  422.         for(int i=0; i<max_step; i++)
  423.         {
  424.                 init_radix(&radix);

  425.                 int div = power(10, i);
  426.                 for(int j=0; j<size; j++)
  427.                 {
  428.                         int temp = array[j]/div;
  429.                         int index = temp - temp/10 *10;
  430.                         insert_queue(&radix.qvalue[index], array[j]);
  431.                 }
  432.                 collect(radix, array);
  433.                 begin_alloc = 0;
  434.         }

  435.         free(g_alloc);
  436.         assert(is_sorted(array, size)==1);
  437.         return 0;
  438. }


  439. int counting_sort(int array[], int size)
  440. {
  441.         int max = array[0];
  442.         for(int i=1; i<size; i++)
  443.                 if(array[i]>max)
  444.                         max = array[i];
  445.         int *temparray = (int *)malloc(sizeof(int) * (max+1));
  446.         assert(temparray!=NULL);
  447.         memset(temparray, 0, sizeof(int)*(max+1));

  448.         int *array2 = (int *)malloc(sizeof(int) * (size));
  449.         assert(array2!=NULL);
  450.         memset(array2, 0, sizeof(int)*(size));

  451.         for(int i=0; i<size; i++)
  452.         {
  453.                 temparray[array[i]]++;
  454.         }
  455.         for(int i=1; i<=max; i++)
  456.         {
  457.                 temparray[i] += temparray[i-1];
  458.         }
  459.         for(int i=0; i<size; i++)
  460.         {
  461.                 array2[--temparray[array[i]]] = array[i];
  462.         }
  463.         memcpy(array, array2, sizeof(int) * size);
  464.         free(temparray);
  465.         free(array2);
  466.         return 0;
  467. }

  468. int mypower(int base, int p)
  469. {
  470.         int ret = 1;
  471.         while(p-->0)
  472.                 ret *= base;
  473.         return ret;
  474. }

  475. int getindexvalue(int num, int index)
  476. {
  477.         if(index<1)
  478.                 return -1;

  479.         int p = mypower(10, index);
  480.         int q = p/10;
  481.         return ( num - num /p * p ) / q;
  482. }

  483. int radix_sort2(int array[], int size)
  484. {
  485.         int *p = array;
  486.         int maxvalue = array[0];
  487.         for(int i=1; i<size; i++)
  488.                 if(array[i]>maxvalue)
  489.                         maxvalue = array[i];
  490.         int max_step = 0;
  491.         while(maxvalue>0)
  492.         {
  493.                 max_step++;
  494.                 maxvalue = maxvalue/10;
  495.         }

  496.         int *array2 = (int *)malloc(sizeof(int) * (size));
  497.         assert(array2!=NULL);
  498.         memset(array2, 0, sizeof(int)*(size));

  499.         for(int i=1; i<=max_step; i++)
  500.         {
  501.                 int tempbuf[10] = {0};
  502.                 for(int j=0; j<=size; j++)
  503.                         tempbuf[getindexvalue(p[j], i)]++;
  504.                 for(int j=1; j<10; j++)
  505.                         tempbuf[j] += tempbuf[j-1];
  506.                 for(int j=0; j<size; j++)
  507.                         array2[--tempbuf[getindexvalue(p[j],i)]] = p[j];
  508.                 int *t = p;
  509.                 p = array2;
  510.                 array2 = t;
  511.         }
  512.         if(p!=array)
  513.         {
  514.                 memcpy(array, p, sizeof(int)*size);
  515.         }

  516.         free(array2);
  517.         return 0;
  518. }


  519. /*
  520.    in this file, we test the sort funcion.
  521.  */
  522. int main(int argc, char **argv)
  523. {
  524.         int *array = NULL;
  525.         int size = 100000;
  526.         array = (int *)malloc(sizeof(int) *size);
  527.         assert(array!=NULL);

  528.         int *array_bak = (int *)malloc(sizeof(int) *size);
  529.         assert(array_bak!=NULL);

  530.         seed = time(NULL);
  531.         int mod = 1000000;

  532.         long starttime, endtime;

  533.         //init
  534.         for(int i=0; i<size; i++)
  535.         {
  536.                 array[i] = rand_r(&seed) % mod;
  537.         }
  538.         memcpy(array_bak, array, sizeof(int)*size);

  539.         //1. insert sort
  540.         TIMER(starttime);
  541.         insert_sort(array, size);
  542.         TIMER(endtime);
  543.         cout << "insert sort time: " << endtime-starttime << endl;
  544.         memcpy(array, array_bak, sizeof(int)*size);

  545.         //2. shell sort
  546.         TIMER(starttime);
  547.         shell_sort(array, size);
  548.         TIMER(endtime);
  549.         cout << "shell sort time: " << endtime-starttime << endl;
  550.         memcpy(array, array_bak, sizeof(int)*size);

  551.         //3. bubble sort
  552.         TIMER(starttime);
  553.         bubble_sort(array, size);
  554.         TIMER(endtime);
  555.         cout << "bubble sort time: " << endtime-starttime << endl;
  556.         memcpy(array, array_bak, sizeof(int)*size);

  557.         //4. quick sort
  558.         TIMER(starttime);
  559.         quick_sort(array, 0, size-1);
  560.         assert(is_sorted(array, size)==1);
  561.         TIMER(endtime);
  562.         cout << "quick sort time: " << endtime-starttime << endl;
  563.         memcpy(array, array_bak, sizeof(int)*size);

  564.         //4.1 quick sort without recursion
  565.         TIMER(starttime);
  566.         quick_sort2(array, 0, size-1);
  567.         assert(is_sorted(array, size)==1);
  568.         TIMER(endtime);
  569.         cout << "quick sort 2 time: " << endtime-starttime << endl;
  570.         memcpy(array, array_bak, sizeof(int)*size);

  571.         //5. select sort
  572.         TIMER(starttime);
  573.         select_sort(array, size);
  574.         TIMER(endtime);
  575.         cout << "select sort time: " << endtime-starttime << endl;
  576.         memcpy(array, array_bak, sizeof(int)*size);

  577.         //6. heap sort
  578.         TIMER(starttime);
  579.         heap_sort(array, size);
  580.         TIMER(endtime);
  581.         cout << "heap sort time: " << endtime-starttime << endl;
  582.         memcpy(array, array_bak, sizeof(int)*size);

  583.         //7. merge sort
  584.         TIMER(starttime);
  585.         Merge_sort(array, 0, size-1);
  586.         TIMER(endtime);
  587.         cout << "merge sort time: " << endtime-starttime << endl;
  588.         memcpy(array, array_bak, sizeof(int)*size);

  589.         //8. radix sort
  590.         TIMER(starttime);
  591.         radix_sort(array, size);
  592.         TIMER(endtime);
  593.         cout << "radix sort time: " << endtime-starttime << endl;
  594.         memcpy(array, array_bak, sizeof(int)*size);

  595.         //9. radix sort 2 using counting sort
  596.         TIMER(starttime);
  597.         radix_sort2(array, size);
  598.         TIMER(endtime);
  599.         cout << "radix sort 2 time: " << endtime-starttime << endl;
  600.         memcpy(array, array_bak, sizeof(int)*size);


  601.         //10. counting sort
  602.         TIMER(starttime);
  603.         counting_sort(array, size);
  604.         TIMER(endtime);
  605.         cout << "counting sort time: " << endtime-starttime << endl;
  606.         memcpy(array, array_bak, sizeof(int)*size);

  607.         //destroy the memory
  608.         free(array);
  609.         free(array_bak);
  610.         return 0;
  611. }

阅读(223) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~