10种常见排序算法实现

1710阅读　0评论2013-06-10　bjpiao
分类：C/C++

点击(此处)折叠或打开

  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>

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

  20. #include <iostream>

  22. using namespace std;

  24. #define TIMER(val) do{
  25.         struct timeval tm;
  26.         gettimeofday(&tm, NULL);
  27.         val = tm.tv_sec * 1000 + tm.tv_usec/1000;
  28. }
  29. while(0)

  31. unsigned int seed = 0;

  33. int is_sorted(int *array, int size)
  34. {
  35.         int sorted = 1;
  36.         for(int i=0; i<size-1; i++)
  37.         {
  38.                 if(array[i]<=array[i+1])
  39.                         continue;
  40.                 else
  41.                 {
  42.                         sorted = 0;
  43.                         break;
  44.                 }
  45.         }
  46.         return sorted;
  47. }

  49. //insert sort
  50. int insert_sort(int array[], int size)
  51. {
  52.         for(int i=1; i<size; i++)
  53.         {
  54.                 int sentinel = array[i];
  55.                 int j;
  56.                 for(j=i-1; j>=0; j--)
  57.                 {
  58.                         if(sentinel < array[j])
  59.                         {
  60.                                 array[j+1] = array[j];
  61.                         }
  62.                         else
  63.                         {
  64.                                 break;
  65.                         }
  66.                 }
  67.                 if(j+1 != i)
  68.                         array[j+1] = sentinel;
  69.         }
  70.         assert(is_sorted(array, size)==1);
  71.         return 0;
  72. }

  74. //shell basic
  75. int shell_basic_sort(int array[], int size, int step)
  76. {
  77.         for(int i=1; i<=step; i++)
  78.         {
  79.                 //jump insert sort
  80.                 for(int j=i; j<=size; j+=step)
  81.                 {
  82.                         int sentinel = array[j-1];
  83.                         int k;
  84.                         for(k=j-step; k>=i; k-=step)
  85.                         {
  86.                                 if(sentinel < array[k-1])
  87.                                 {
  88.                                         array[k+step-1] = array[k-1];
  89.                                 }
  90.                                 else
  91.                                 {
  92.                                         break;
  93.                                 }
  94.                         }
  95.                         array[k+step-1] = sentinel;
  96.                 }
  97.         }
  98.         return 0;
  99. }

  101. int shell_sort(int array[], int size)
  102. {
  103.         int step = size;
  104.         while(step>=1)
  105.         {
  106.                 shell_basic_sort(array, size, step);
  107.                 step/=2;
  108.         }

  110.         assert(is_sorted(array, size)==1);
  111.         return 0;
  112. }

  114. void swap(int *a, int *b)
  115. {
  116.         int t = *a;
  117.         *a = *b;
  118.         *b = t;
  119. }


  122. //bubble sort
  123. int bubble_sort(int array[], int size)
  124. {
  125.         int sorted;

  127.         for(int i=size-1; i>0; i--)
  128.         {
  129.                 sorted = 1;
  130.                 for(int j=0; j<i; j++)
  131.                 {
  132.                         if(array[j] > array[j+1])
  133.                         {
  134.                                 swap(&array[j], &array[j+1]);
  135.                                 sorted = 0;
  136.                         }
  137.                 }
  138.                 if(1==sorted)
  139.                         break;
  140.         }

  142.         assert(is_sorted(array, size)==1);
  143.         return 0;
  144. }

  146. int pivot(int array[], int first, int last)
  147. {
  148.         int f = array[first];
  149.         while(first<last)
  150.         {

  152.                 while(first < last && array[last]>=f)
  153.                         last--;
  154.                 array[first] = array[last];
  155.                 while(first < last && array[first]<=f)
  156.                         first++;
  157.                 array[last] = array[first];
  158.         }
  159.         array[first] = f;
  160.         return;
  161. }


  164. int quick_sort(int array[], int first, int last)
  165. {
  166.         if(first>=last)
  167.                 return 0;

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

  173.         int mid = pivot(array, first, last);
  174.         quick_sort(array, first, mid-1);
  175.         quick_sort(array, mid+1, last);
  176.         return 0;
  177. }

  179. typedef struct stack
  180. {
  181.         int low;
  182.         int high;
  183. }stack;

  185. int quick_sort2(int array[], int first, int last)
  186. {
  187.         int top = 0;
  188.         stack *pstack = (stack *)malloc(sizeof(stack) * (last-first+1));
  189.         if(pstack==NULL)
  190.                 return -1;
  191.         memset(pstack, (last-first+1), 0);

  193.         int size = last - first + 1;
  194.         int rand = (int)rand_r(&seed) % size;
  195.         swap(&array[first], &array[first+rand]);
  196.         int mid = pivot(array, first, last);

  198.         pstack[top].low = mid+1;
  199.         pstack[top].high = last;
  200.         top++;
  201.         //1

  203.         pstack[top].low = first;
  204.         pstack[top].high = mid-1;
  205.         top++;
  206.         //2

  208.         while(top>0)
  209.         {
  210.                 top--;
  211.                 int low = pstack[top].low;
  212.                 int high = pstack[top].high;
  213.                 if(low<high)
  214.                 {
  215.                         int size = high - low + 1;
  216.                         int rand = (int)rand_r(&seed) % size;
  217.                         swap(&array[low], &array[low+rand]);
  218.                         int mid = pivot(array, low, high);
  219.         
  220.                         pstack[top].low = mid+1;
  221.                         pstack[top].high = high;
  222.                         top++;

  224.                         pstack[top].low = low;
  225.                         pstack[top].high = mid-1;
  226.                         top++;
  227.                 }
  228.         }

  230.         free(pstack);
  231.         return 0;
  232. }

  234. int find_max(int array[], int size)
  235. {
  236.         int max_index = 0;
  237.         int sentinel = array[0];
  238.         for(int j=1; j<size; j++)
  239.         {
  240.                 if(array[j]>sentinel)
  241.                 {
  242.                         sentinel = array[j];
  243.                         max_index = j;
  244.                 }
  245.         }
  246.         return max_index;
  247. }

  249. int select_sort(int array[], int size)
  250. {
  251.         for(int i=size; i>=1; i--)
  252.         {
  253.                 int max_index = find_max(array, i);
  254.                 if(max_index!=i-1)
  255.                 {
  256.                         swap(&array[max_index], &array[i-1]);
  257.                 }
  258.         }
  259.         assert(is_sorted(array, size)==1);
  260.         return 0;
  261. }

  263. int heapify(int array[], int index, int size)
  264. {
  265.         while(index<=size/2)
  266.         {
  267.                 int left = 2*index;
  268.                 int right = left+1;
  269.                 int max_index = left;
  270.                 if( (right<=size) && array[left-1] < array[right-1])
  271.                         max_index = right;
  272.                 if(array[index-1] < array[max_index-1])
  273.                 {
  274.                         swap(&array[index-1], &array[max_index-1]);
  275.                         index = max_index;
  276.                 }
  277.                 else
  278.                         break;
  279.         }
  280.         return 0;
  281. }

  283. int heap_sort(int array[], int size)
  284. {
  285.         //build heap, heapify
  286.         int mid = size/2;
  287.         for(int i=mid; i>0; i--)
  288.                 heapify(array, i, size);
  289.         for(int i=size; i>0; )
  290.         {
  291.                 swap(&array[0], &array[i-1]);
  292.                 i--;
  293.                 if(i>0)
  294.                         heapify(array, 1, i);
  295.         }
  296.         assert(is_sorted(array, size)==1);
  297.         return 0;
  298. }

  300. //(start, mid-1)
  301. //(mid, end)
  302. int merge(int array[], int start, int mid, int end, int temparray[])
  303. {
  304.         int size1 = mid -start;
  305.         int size2 = end - mid +1;
  306.         int size = size1 > size2 ? size2 : size1;

  308.         int i,j,k;
  309.         i = j = k =0;
  310.         while( i<size1 && j<size2 )
  311.         {
  312.                 if(array[start+i] <array[mid+j])
  313.                 {
  314.                         temparray[j++] = array[start+i];
  315.                         i++;
  316.                 }
  317.                 else
  318.                 {
  319.                         temparray[j++] = array[mid+j];
  320.                         j++;
  321.                 }
  322.         }
  323.         if(i==size1)
  324.         {
  325.                 memcpy(array+size, &array[mid+j], size1-j);
  326.         }
  327.         else
  328.         {
  329.                 memcpy(array+size, &array[start+i], size1-i);
  330.         }
  331.         memcpy(array, temparray, sizeof(int)*size);
  332.         return 0;
  333. }


  336. int merge_sort(int array[], int start, int end, int temparray[])
  337. {
  338.         if(start>=end)
  339.                 return 0;

  341.         int size = end - start + 1;
  342.         int mid = start + size/2;

  344.         merge_sort(array, start, mid-1, temparray);
  345.         merge_sort(array, mid, end, temparray);
  346.         merge(array, start, mid, end, temparray);
  347.         return 0;
  348. }

  350. int Merge_sort(int array[], int start, int end)
  351. {
  352.         int size = end-start+1;
  353.         int *temparray = (int *)malloc(sizeof(int) *size);
  354.         assert(array!=NULL);
  355.         merge_sort(array, start, end, temparray);
  356.         free(temparray);
  357.         return 0;
  358. }


  361. ///////////////////////////////////////////////////////////////////////////////////////////////////////////
  362. typedef struct queue_elem
  363. {
  364.         int value;
  365.         struct queue_elem *next;
  366. }queue_elem;

  368. typedef struct queue
  369. {
  370.         queue_elem *first;
  371.         queue_elem *last;
  372.         int queue_size;
  373. }queue;

  375. typedef struct radix_queue
  376. {
  377.         queue qvalue[10];
  378. }radix_queue;

  380. radix_queue radix;
  381. queue_elem *g_alloc;
  382. int begin_alloc;
  383. int max_size;

  385. void init_queue_elm(queue_elem *qe)
  386. {
  387.         qe->value = 0;
  388.         qe->next = NULL;
  389. }

  391. int init_queue(queue *q)
  392. {
  393.         q->first = q->last = NULL;
  394.         q->queue_size = 0;
  395. }

  397. queue_elem *get_queue_elem()
  398. {
  399.         if(begin_alloc>=max_size)
  400.         {
  401.                 cout << "get queue elem error2" << endl;
  402.                 return NULL;
  403.         }
  404.         int curr = begin_alloc++;
  405.         queue_elem * p = g_alloc + curr;
  406.         init_queue_elm(p);
  407.         return p;
  408. }

  410. int init_radix(radix_queue *radix)
  411. {
  412.         for(int i=0; i<10; i++)
  413.                 init_queue(&radix->qvalue[i]);
  414. }

  416. int insert_queue(queue *q, int value)
  417. {
  418.         queue_elem *elem = get_queue_elem();
  419.         if(elem==NULL)
  420.         {
  421.                 cout << "get queue elem error" << endl;
  422.                 return -1;
  423.         }
  424.         elem->value = value;
  425.         elem->next = NULL;
  426.         if(q->queue_size==0)
  427.                 q->first = q->last = elem;
  428.         else
  429.                 q->last->next = elem;

  431.         q->last = elem;
  432.         q->queue_size++;
  433.         return 0;
  434. }
  435. int collect(radix_queue radix, int array[])
  436. {
  437.         int i = 0;
  438.         for(int j=0; j<10; j++)
  439.         {
  440.                 queue q = radix.qvalue[j];
  441.                 queue_elem *first = q.first;
  442.                 while(first!=NULL)
  443.                 {
  444.                         array[i++] = first->value;
  445.                         first = first->next;
  446.                 }
  447.         }
  448.         return 0;
  449. }

  451. int power(int base, int m)
  452. {
  453.         int value = 1;
  454.         for(int i=0; i<m; i++)
  455.                 value *= base;
  456.         return value;
  457. }

  459. int radix_sort(int array[], int size)
  460. {
  461.         max_size = size;
  462.         begin_alloc = 0;
  463.         g_alloc = (queue_elem *)malloc(sizeof(queue_elem) * size);
  464.         assert(g_alloc);

  466.         int maxvalue = array[0];
  467.         for(int i=1; i<size; i++)
  468.                 if(array[i]>maxvalue)
  469.                         maxvalue = array[i];
  470.         int max_step = 0;
  471.         while(maxvalue>0)
  472.         {
  473.                 max_step++;
  474.                 maxvalue = maxvalue/10;
  475.         }

  477.         for(int i=0; i<max_step; i++)
  478.         {
  479.                 init_radix(&radix);

  481.                 int div = power(10, i);
  482.                 for(int j=0; j<size; j++)
  483.                 {
  484.                         int temp = array[j]/div;
  485.                         int index = temp - temp/10 *10;
  486.                         insert_queue(&radix.qvalue[index], array[j]);
  487.                 }
  488.                 collect(radix, array);
  489.                 begin_alloc = 0;
  490.         }

  492.         free(g_alloc);
  493.         assert(is_sorted(array, size)==1);
  494.         return 0;
  495. }


  498. int counting_sort(int array[], int size)
  499. {
  500.         int max = array[0];
  501.         for(int i=1; i<size; i++)
  502.                 if(array[i]>max)
  503.                         max = array[i];
  504.         int *temparray = (int *)malloc(sizeof(int) * (max+1));
  505.         assert(temparray!=NULL);
  506.         memset(temparray, 0, sizeof(int)*(max+1));

  508.         int *array2 = (int *)malloc(sizeof(int) * (size));
  509.         assert(array2!=NULL);
  510.         memset(array2, 0, sizeof(int)*(size));

  512.         for(int i=0; i<size; i++)
  513.         {
  514.                 temparray[array[i]]++;
  515.         }
  516.         for(int i=1; i<=max; i++)
  517.         {
  518.                 temparray[i] += temparray[i-1];
  519.         }
  520.         for(int i=0; i<size; i++)
  521.         {
  522.                 array2[--temparray[array[i]]] = array[i];
  523.         }
  524.         memcpy(array, array2, sizeof(int) * size);
  525.         free(temparray);
  526.         free(array2);
  527.         return 0;
  528. }

  530. int mypower(int base, int p)
  531. {
  532.         int ret = 1;
  533.         while(p-->0)
  534.                 ret *= base;
  535.         return ret;
  536. }

  538. int getindexvalue(int num, int index)
  539. {
  540.         if(index<1)
  541.                 return -1;

  543.         int p = mypower(10, index);
  544.         int q = p/10;
  545.         return ( num - num /p * p ) / q;
  546. }

  548. int radix_sort2(int array[], int size)
  549. {
  550.         int *p = array;
  551.         int maxvalue = array[0];
  552.         for(int i=1; i<size; i++)
  553.                 if(array[i]>maxvalue)
  554.                         maxvalue = array[i];
  555.         int max_step = 0;
  556.         while(maxvalue>0)
  557.         {
  558.                 max_step++;
  559.                 maxvalue = maxvalue/10;
  560.         }

  562.         int *array2 = (int *)malloc(sizeof(int) * (size));
  563.         assert(array2!=NULL);
  564.         memset(array2, 0, sizeof(int)*(size));

  566.         for(int i=1; i<=max_step; i++)
  567.         {
  568.                 int tempbuf[10] = {0};
  569.                 for(int j=0; j<=size; j++)
  570.                         tempbuf[getindexvalue(p[j], i)]++;
  571.                 for(int j=1; j<10; j++)
  572.                         tempbuf[j] += tempbuf[j-1];
  573.                 for(int j=0; j<size; j++)
  574.                         array2[--tempbuf[getindexvalue(p[j],i)]] = p[j];
  575.                 int *t = p;
  576.                 p = array2;
  577.                 array2 = t;
  578.         }
  579.         if(p!=array)
  580.         {
  581.                 memcpy(array, p, sizeof(int)*size);
  582.         }

  584.         free(array2);
  585.         return 0;
  586. }


  589. /*
  590.    in this file, we test the sort funcion.
  591.  */
  592. int main(int argc, char **argv)
  593. {
  594.         int *array = NULL;
  595.         int size = 100000;
  596.         array = (int *)malloc(sizeof(int) *size);
  597.         assert(array!=NULL);

  599.         int *array_bak = (int *)malloc(sizeof(int) *size);
  600.         assert(array_bak!=NULL);

  602.         seed = time(NULL);
  603.         int mod = 1000000;

  605.         long starttime, endtime;

  607.         //init
  608.         for(int i=0; i<size; i++)
  609.         {
  610.                 array[i] = rand_r(&seed) % mod;
  611.         }
  612.         memcpy(array_bak, array, sizeof(int)*size);

  614.         //1. insert sort
  615.         TIMER(starttime);
  616.         insert_sort(array, size);
  617.         TIMER(endtime);
  618.         cout << "insert sort time: " << endtime-starttime << endl;
  619.         memcpy(array, array_bak, sizeof(int)*size);

  621.         //2. shell sort
  622.         TIMER(starttime);
  623.         shell_sort(array, size);
  624.         TIMER(endtime);
  625.         cout << "shell sort time: " << endtime-starttime << endl;
  626.         memcpy(array, array_bak, sizeof(int)*size);

  628.         //3. bubble sort
  629.         TIMER(starttime);
  630.         bubble_sort(array, size);
  631.         TIMER(endtime);
  632.         cout << "bubble sort time: " << endtime-starttime << endl;
  633.         memcpy(array, array_bak, sizeof(int)*size);

  635.         //4. quick sort
  636.         TIMER(starttime);
  637.         quick_sort(array, 0, size-1);
  638.         assert(is_sorted(array, size)==1);
  639.         TIMER(endtime);
  640.         cout << "quick sort time: " << endtime-starttime << endl;
  641.         memcpy(array, array_bak, sizeof(int)*size);

  643.         //4.1 quick sort without recursion
  644.         TIMER(starttime);
  645.         quick_sort2(array, 0, size-1);
  646.         assert(is_sorted(array, size)==1);
  647.         TIMER(endtime);
  648.         cout << "quick sort 2 time: " << endtime-starttime << endl;
  649.         memcpy(array, array_bak, sizeof(int)*size);

  651.         //5. select sort
  652.         TIMER(starttime);
  653.         select_sort(array, size);
  654.         TIMER(endtime);
  655.         cout << "select sort time: " << endtime-starttime << endl;
  656.         memcpy(array, array_bak, sizeof(int)*size);

  658.         //6. heap sort
  659.         TIMER(starttime);
  660.         heap_sort(array, size);
  661.         TIMER(endtime);
  662.         cout << "heap sort time: " << endtime-starttime << endl;
  663.         memcpy(array, array_bak, sizeof(int)*size);

  665.         //7. merge sort
  666.         TIMER(starttime);
  667.         Merge_sort(array, 0, size-1);
  668.         TIMER(endtime);
  669.         cout << "merge sort time: " << endtime-starttime << endl;
  670.         memcpy(array, array_bak, sizeof(int)*size);

  672.         //8. radix sort
  673.         TIMER(starttime);
  674.         radix_sort(array, size);
  675.         TIMER(endtime);
  676.         cout << "radix sort time: " << endtime-starttime << endl;
  677.         memcpy(array, array_bak, sizeof(int)*size);

  679.         //9. radix sort 2 using counting sort
  680.         TIMER(starttime);
  681.         radix_sort2(array, size);
  682.         TIMER(endtime);
  683.         cout << "radix sort 2 time: " << endtime-starttime << endl;
  684.         memcpy(array, array_bak, sizeof(int)*size);


  687.         //10. counting sort
  688.         TIMER(starttime);
  689.         counting_sort(array, size);
  690.         TIMER(endtime);
  691.         cout << "counting sort time: " << endtime-starttime << endl;
  692.         memcpy(array, array_bak, sizeof(int)*size);

  694.         //destroy the memory
  695.         free(array);
  696.         free(array_bak);
  697.         return 0;
  698. }

上一篇：Crit-bit Tree概述和实现
下一篇：mmap和write性能对比