Chinaunix首页 | 论坛 | 博客
  • 博客访问: 413447
  • 博文数量: 168
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 0
  • 用 户 组: 普通用户
  • 注册时间: 2013-09-09 13:46
文章分类

全部博文(168)

文章存档

2015年(51)

2014年(30)

2013年(87)

我的朋友

分类: C/C++

2013-10-18 14:55:15

 

  1. #include <iostream>
  2. #include <strstream>
  3. #include <vector>
  4. using namespace std;

  5. void Swap(int &a, int &b)
  6. {
  7.       int temp = a;
  8.       a = b;
  9.       b = temp;
  10. }
  11. /* 冒泡排序 */
  12. void BubbleSort(int* a, int n)
  13. {
  14.       for(int i = n - 1; i >= 0; i--)
  15.       for(int j = 0; j < i; j++)
  16.       {
  17.                  if(a[j] > a[j + 1])
  18.                  Swap(a[j], a[j + 1]);
  19.          }
  20. }

  21. /* 快速排序 */
  22. void QuickSort(int *a, int low, int high)
  23. {
  24.       int middle = a[(low + high)/ 2];
  25.       int i = low;
  26.       int j = high;
  27.       while(i <= j)
  28.       {
  29.               while(a[i] < middle) i++;
  30.               while(a[j] > middle) j--;
  31.             
  32.              if(i <= j)
  33.              {
  34.                   Swap(a[i], a[j]);
  35.                   i++;
  36.                   j--;
  37.          }
  38.      }
  39.      
  40.      if(i < high)
  41.        QuickSort(a, i, high);
  42.      if(j > low)
  43.        QuickSort(a, low, j);
  44. }

  45. /* 桶排序, 无相同元素 */
  46. void BucketSortNoSameElement(int *a, int n)
  47. {
  48.       int max = a[0];
  49.       for(int i = 1; i < n; ++i)
  50.       {
  51.          if(max < a[i])
  52.           max = a[i];
  53.      }
  54.     
  55.      int *emptyBucket = new int[max];
  56.      for(int i = 0; i < max; ++i)
  57.      {
  58.               emptyBucket[i] = 0;
  59.      }
  60.      
  61.      for(int i = 0; i < n; ++i)
  62.      {
  63.      emptyBucket[a[i] - 1] = a[i];
  64.      }
  65.     
  66.      int index = 0;
  67.     
  68.      for(int i = 0; i < max; ++i)
  69.      {
  70.               if(emptyBucket[i] > 0)
  71.               a[index++] = emptyBucket[i];
  72.      }
  73.     
  74.      delete []emptyBucket;
  75. }

  76. /* 桶排序, 有相同元素 */
  77. void BucketSortHasSameElement(int *a, int n)
  78. {
  79.       int max = a[0];
  80.       for(int i = 1; i < n; ++i)
  81.       {
  82.          if(max < a[i])
  83.           max = a[i];
  84.      }
  85.     
  86.      vector<int>* emptyBucket = new vector<int>[max];
  87.      for(int i = 0; i < n; ++i)
  88.      {
  89.               emptyBucket[a[i] - 1].push_back(a[i]);
  90.      }
  91.     
  92.      int index = 0;
  93.      for(int i = 0; i < max; ++i)
  94.      {
  95.               vector<int>::iterator iter = emptyBucket[i].begin();
  96.               for(; iter != emptyBucket[i].end(); ++iter)
  97.               {
  98.                   a[index++] = *iter;
  99.                 }
  100.      }
  101.     
  102.      delete []emptyBucket;
  103. }

  104. /* 插入排序 */
  105. void InsertionSort(int* a, int n)
  106. {
  107.       for(int i = 1; i < n; ++i)
  108.       {
  109.               int t = a[i];
  110.               int j = i;
  111.               while(( j > 0) && (a[j - 1] > t))
  112.               {
  113.                       a[j] = a[j -1];
  114.                       --j;
  115.               }
  116.               a[j] = t;
  117.      }
  118. }


  119. /* 希尔排序, 插入排序变种 */
  120. void ShellSort(int *a, int n)
  121. {
  122.     int inc = 0;
  123.     for(inc = 1; inc <= n / 9; inc = 3 * inc + 1);
  124.     for(; inc > 0; inc /= 3)
  125.     {
  126.         for(int i = inc + 1; i <= n; i += inc)
  127.         {
  128.             int t = a[i -1];
  129.             int j = i;
  130.             while(( j > inc) && (a[j - inc - 1] > t))
  131.             {
  132.                 a[j - 1] = a[j - inc - 1];
  133.                 j -= inc;
  134.             }
  135.             a[j - 1] = t;
  136.         }
  137.     }
  138. }

  139. /* 基数排序 */
  140. typedef vector<unsigned int> input_type;
  141. void RadixSort(input_type & x)
  142. {
  143.       if(x.empty()) return;
  144.      
  145.       typedef vector< vector<input_type::value_type> > buckets_type;
  146.       buckets_type buckets;
  147.      
  148.       buckets.resize(10);
  149.      
  150.       int pow10 = 1; //pow10 holds powers of 10 (1, 10, 100, ...)
  151.      
  152.      input_type::value_type max = *std::max(x.begin(), x.end());
  153.      
  154.       for(; max != 0; max /= 10, pow10 *= 10)
  155.       {
  156.           for(input_type::const_iterator elem = x.begin(); elem != x.end(); ++elem)
  157.           {
  158.                size_t const bucket_num = (*elem / pow10) % 10;
  159.                buckets[bucket_num].push_back(*elem);
  160.           }
  161.          
  162.           // transfer results of buckets back into main array
  163.           input_type::iterator store_pos = x.begin();
  164.          
  165.           for(buckets_type::iterator bucket = buckets.begin(); bucket != buckets.end(); ++bucket)
  166.           {
  167.      for(buckets_type::value_type::const_iterator bucket_elem = bucket->begin();
  168.                             bucket_elem != bucket->end(); ++bucket_elem)
  169.              {
  170.                              *store_pos++ = *bucket_elem;
  171.              }
  172.              bucket->clear();
  173.           }
  174.      }
  175. }

  176. /* 鸽巢排序 */
  177. void PigeonholeSort(int *a, int n)
  178. {
  179.       int max = a[0];
  180.       for(int i = 1; i < n; ++i)
  181.       {
  182.               if(max < a[i])
  183.               max = a[i];
  184.      }
  185.     
  186.      int *pigeonHole = new int[max + 1];
  187.      for(int i = 0; i < n; ++i)
  188.      {
  189.          pigeonHole[a[i]] = 0;
  190.      }

  191.      for(int i = 0; i < n; ++i)
  192.      {
  193.               pigeonHole[a[i]]++;
  194.      }
  195.     
  196.      int index = 0;
  197.     
  198.      for(int i = 0; i <= max; ++i)
  199.      {
  200.               for(int j = 0; j < pigeonHole[i]; ++j)
  201.               {
  202.                       a[index++] = i;
  203.               }
  204.      }
  205.     
  206.      delete []pigeonHole;
  207. }

  208. /* 合并排序 */
  209. void Merge(vector<int> left, vector<int> right, vector<int> &result)
  210. {
  211.     result.clear();
  212.     int i = 0, j = 0;
  213.     while(i < left.size() && j < right.size())
  214.     {
  215.         if(left[i] < right[j])
  216.         {
  217.             result.push_back(left[i++]);
  218.         }
  219.         else
  220.         {
  221.             result.push_back(right[j++]);
  222.         }
  223.     }

  224.     // 还有左元素,没有右元素
  225.     while( i < left.size())
  226.     {
  227.         result.push_back(left[i++]);
  228.     }

  229.     //还有右元素,没有左元素
  230.     while( j < right.size())
  231.     {
  232.         result.push_back(right[j++]);
  233.     }
  234. }

  235. void MergeSort(vector<int> &a)
  236. {
  237.     if(a.size() <= 1) return;
  238.     vector<int> left;
  239.     vector<int> right;
  240.     int middle = a.size() / 2;
  241.     
  242.     for(int i = 0; i < middle; ++i)
  243.     {
  244.         left.push_back(a[i]);
  245.     }

  246.     for(int i = middle; i < a.size(); ++i)
  247.     {
  248.         right.push_back(a[i]);
  249.     }

  250.     MergeSort(left);
  251.     MergeSort(right);

  252.     Merge(left, right, a);
  253. }


  254. /* 选择排序 */
  255. void SelectionSort(int *a, int n)
  256. {
  257.     for(int i = 0; i < n; i++)
  258.         for(int j = i + 1; j < n; j++)
  259.         {
  260.             if(a[j] < a[i])
  261.             {
  262.                 Swap(a[j], a[i]);
  263.             }
  264.         }
  265. }

  266. /* 计数排序 */
  267. void CountingSort(int *a, int n)
  268. {
  269.     int max = a[0];
  270.     int min = a[0];

  271.     for(int i = 1; i < n; ++i)
  272.     {
  273.         if(a[i] > max)
  274.             max = a[i];
  275.         if(a[i] < min)
  276.             min = a[i];
  277.     }

  278.     int range = max - min + 1;
  279.     int *count = new int[range];

  280.     for(int i = 0; i < range; ++i)
  281.     {
  282.         count[i] = 0;
  283.     }

  284.     for(int i = 0; i < n; ++i)
  285.     {
  286.         count[ a[i] - min]++;
  287.     }

  288.     int index = 0;
  289.     for(int i = min; i <= max; i++)
  290.         for(int j = 0; j < count[i - min]; ++j)
  291.             a[index++] = i;

  292.     delete []count;
  293. }
阅读(1176) | 评论(0) | 转发(0) |
0

上一篇:MFC类库组成

下一篇:C/C++面试题

给主人留下些什么吧!~~