现在的位置: 首页 > 综合 > 正文

内部排序算法的C/C++实现

2017年09月06日 ⁄ 综合 ⁄ 共 6887字 ⁄ 字号 评论关闭
  1. 内部排序算法的C/C++实现
  2. 排序是数据处理中经常使用的一种重要运算,在计算机及其应用系统中,花费在排序上的时间在系统运行时间中占有很大比重;并且排序本身对推动算法分析的发展 也起很大作用。目前已有上百种排序方法,但尚未有一个最理想的尽如人意的方法,本文介绍常用的如下排序方法的C/C++实现,并对它们进行分析和比较。
  3. 更详细的算法思想的介绍可以参考这里  
  4. /*
  5.    冒泡排序  插入排序 二路插入排序 希尔排序   快速排序 选择排序 归并排序  堆排序算法的
  6.    C/C++实现。
  7.    
  8.    作者:feosun
  9.    日期:2008年10月12日
  10.    参考资料:数据结构(C语言版) 清华大学出版社
  11. */
  12. #include <iostream>
  13. using namespace std;
  14. //交换两个数的值
  15. void swap(int &a,int &b)
  16. {
  17.     int tmp;
  18.     tmp=a;
  19.     a=b;
  20.     b=tmp;
  21. }
  22. //屏幕输出数组
  23. void display(int array[],int len)
  24. {
  25.     cout<<"the result is:"<<endl;
  26.     for (int i = 0 ;i < len;i++ )
  27.     {
  28.         cout<<array[i]<<"  ";
  29.     }
  30.     cout<<endl;
  31. }
  32. /*
  33. 冒泡排序
  34. 算法思想:将被排序的记录数组R[1..n]垂直排列,每个记录R[i]看作是重量为R[i].key的气泡。
  35.           根据轻气泡不能在重气泡之下的原则,从下往上扫描数组 R:凡扫描到违反本原则的
  36.           轻气泡,就使其向上"飘浮"。如此反复进行,直到最后任何两个气泡都是轻者在上,
  37.           重者在下为止。
  38. 时间复杂度 o(n^2)
  39. 空间复杂度 o(1)
  40. 比较次数 n(n+1)/2
  41. */
  42. void bubble_sort(int array[],int len)
  43. {
  44.     
  45.     for (int i = len-1 ;i >= 0;i-- )
  46.     {
  47.         for(int j = 0;j < i;j++)
  48.             if(array[j] > array[j+1])
  49.                 swap(array[j],array[j+1]);
  50.     }
  51. }
  52. /*
  53. 直接插入排序
  54. 算法思想:把n个待排序的元素看成为一个有序表和一个无序表,开始时有序表中只包含一个元
  55.           素,无序表中包含有n-1个元素,排序过程中每次从无序表中取出第一个元素,将它
  56.           插入到有序表中的适当位置,使之成为新的有序表,重复n-1次可完成排序过程。
  57. 时间复杂度 o(n^2)
  58. 空间复杂度 o(1)
  59. 比较次数 n(n+1)/2
  60. */
  61. void insert_sort(int array[],int len)
  62. {
  63.     int tmp,i,j;
  64.     for(i = 1;i < len;i++)
  65.     {
  66.         if (array[i] < array[i-1])
  67.         {
  68.             tmp = array[i];
  69.             array[i] = array[i-1];
  70.             //插入到相应位置
  71.             for (j = i-2;j >= 0;j--)
  72.             {
  73.                 //往后移
  74.                     if (array[j] > tmp )
  75.                         array[j+1] = array[j];
  76.                     else
  77.                     {
  78.                         array[j+1] = tmp;
  79.                         break;
  80.                     }
  81.             }
  82.             if(j == -1)
  83.             array[j+1] = tmp;
  84.         }
  85.     }
  86. }
  87. /*
  88. 2-路插入排序
  89. 算法思想:增加一个辅助空间d,把r[1]赋值给d[1],并将d[1]看成是排好序后处于中间
  90.           位置的记录。然后从r[2]开始依次插入到d[1]之前或之后的有序序列中。
  91. 时间复杂度 o(n^2)
  92. 空间复杂度 o(1)
  93. 比较次数 n(n+1)/2
  94. */
  95. void bi_insert_sort(int array[],int len)
  96. {
  97.     int* arr_d = (int *)malloc(sizeof(int) * len);
  98.     arr_d[0] = array[0];
  99.     int head = 0,tail = 0;
  100.     for (int i = 1;i < len; i++ )
  101.     {
  102.         if (array[i] > arr_d[0])
  103.         {
  104.             int j;
  105.             for ( j= tail;j>0;j--)
  106.             {
  107.                 if (array[i] < arr_d[j])
  108.                     arr_d[j+1] = arr_d[j];
  109.                 else
  110.                     break;
  111.             }
  112.             arr_d[j+1] = array[i];
  113.             tail += 1;
  114.         }
  115.         else
  116.         {
  117.             if (head ==0)
  118.             {
  119.                 arr_d[len-1] = array[i];
  120.                 head =len-1;
  121.             }
  122.             else
  123.             {
  124.                 int j;
  125.                 for (j = head;j <= len-1;j++)
  126.                 {
  127.                     if (array[i] > arr_d[j])
  128.                         arr_d[j-1] = arr_d[j];
  129.                     else
  130.                         break;
  131.                 }
  132.                 arr_d[j-1] = array[i];
  133.                 head -= 1;
  134.             }
  135.         }
  136.     }
  137.     for (int i = 0;i < len; i++)
  138.     {
  139.         int pos = (i + head );
  140.         if(pos >= len) pos -= len;
  141.         array[i] = arr_d[pos];
  142.     }
  143.     free(arr_d);
  144. }
  145. /*
  146. 希尔排序
  147. 算法思想:先将整个待排序记录分割成若干子序列分别进行直接插入排
  148.           序,待整个序列中的记录基本有序时,再对全体记录进行一
  149.           次直接插入排序
  150. 时间复杂度 o(n^2)
  151. 空间复杂度 o(1)
  152. 比较次数 ?
  153. */
  154. void shell_insert(int array[],int d,int len)
  155. {
  156.     int tmp,j;
  157.     for (int i = d;i < len;i++)
  158.     {
  159.         if(array[i] < array[i-d])
  160.         {
  161.             tmp = array[i];
  162.             j = i - d;
  163.             do 
  164.             {
  165.                 array[j+d] = array[j];
  166.                 j = j - d;
  167.             } while (j >= 0 && tmp < array[j]);
  168.             array[j+d] = tmp; 
  169.         }
  170.     }
  171. }
  172. void shell_sort(int array[],int len)
  173. {
  174.     int inc = len;
  175.     do 
  176.     {
  177.         inc = inc/2;
  178.         shell_insert(array,inc,len);
  179.     } while (inc > 1);
  180. }
  181. /*
  182. 快速排序
  183. 算法思想:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递
  184.           归地解这些子问题,然后将这些子问题的解组合成为原问题的解。
  185. 时间复杂度 o(nlogn)
  186. 空间复杂度 o(logn)
  187. 比较次数  ?
  188. */
  189. int partition(int array[],int low,int high)
  190. {
  191.     int  pivotkey = array[low];
  192.     while (low < high)
  193.     {
  194.         while(low < high && array[high] >= pivotkey)
  195.             --high;
  196.         swap(array[low],array[high]);
  197.         while(low < high && array[low] <= pivotkey)
  198.             ++low;
  199.         swap(array[low],array[high]);
  200.     }
  201.     array[low] = pivotkey;
  202.     return low;
  203. }
  204. void quick_sort(int array[],int low,int high)
  205. {
  206.     if (low < high)
  207.     {
  208.         int pivotloc = partition(array,low,high);
  209.         quick_sort(array,low,pivotloc-1);
  210.         quick_sort(array,pivotloc+1,high);
  211.     }
  212. }
  213. /*
  214. 直接选择排序
  215. 算法思想:每一趟在n-i+1个记录中选取关键字最小的记录作为有序序列中的第i个记录
  216. 时间复杂度 o(n^2)
  217. 空间复杂度 o(1) ?
  218. 比较次数  n(n+1)/2
  219. */
  220. int SelectMinKey(int array[],int iPos,int len)
  221. {
  222.     int ret = 0;
  223.     for (int i = iPos; i < len; i++)
  224.     {
  225.         if (array[ret] > array[i])
  226.         {
  227.             ret = i;
  228.         }
  229.     }
  230.     return ret;
  231. }
  232. void select_sort(int array[],int len)
  233. {
  234.     for (int i = 0; i < len; i++)
  235.     {
  236.         int j = SelectMinKey(array,i,len);
  237.         if (i != j)
  238.         {
  239.             swap(array[i],array[j]);
  240.         }
  241.     }
  242. }
  243. /*
  244. 归并排序
  245. 算法思想:设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上:R[low..m],R[m+1..high],先
  246.           将它们合并到一个局部的暂存向量R1(相当于输出堆)中,待合并完成后将R1复制回R[low..high]中。
  247. 时间复杂度 o(nlogn)
  248. 空间复杂度 o(n) 
  249. 比较次数  ?
  250. */
  251. void merge(int array[],int i,int m, int n)
  252. {
  253.     int j,k;
  254.     int iStart = i, iEnd = n;
  255.     int arrayDest[256];
  256.     for ( j = m + 1,k = i; i <= m && j <= n; ++k)
  257.     {
  258.         if (array[i] < array[j])
  259.             arrayDest[k] = array[i++];
  260.         else
  261.             arrayDest[k] = array[j++];
  262.     }
  263.     if (i <= m)
  264.         for (;k <= n; k++,i++)
  265.             arrayDest[k] = array[i];
  266.     if(j <= n)
  267.         for (;k <= n; k++,j++)
  268.             arrayDest[k] = array[j];
  269.     for(j = iStart; j <= iEnd; j++)
  270.         array[j] = arrayDest[j];
  271. }
  272. void merge_sort(int array[],int s,int t)
  273. {
  274.     int m;
  275.     if (s < t) 
  276.     {
  277.         m = (s + t )/2;
  278.         merge_sort(array,s,m);
  279.         merge_sort(array,m+1,t);
  280.         merge(array,s,m,t);
  281.     }
  282. }
  283. /*
  284. 堆排序
  285. 算法思想:堆排序(Heap Sort)是指利用堆(heaps)这种数据结构来构造的一种排序算法。
  286.           堆是一个近似完全二叉树结构,并同时满足堆属性:即子节点的键值或索引总是
  287.           小于(或者大于)它的父节点。
  288. 时间复杂度 o(nlogn)
  289. 空间复杂度 o(1) 
  290. 比较次数  较多
  291. */
  292. void heap_adjust(int array[],int i,int len)
  293. {
  294.     int rc = array[i];
  295.     for(int j = 2 * i; j <len; j *= 2)
  296.     {
  297.         if(j < len && array[j] < array[j+1]) j++;
  298.         if(rc >= array[j]) break;
  299.         array[i] = array[j]; i = j;
  300.     }
  301.     array[i] = rc;
  302. }
  303. void heap_sort(int array[],int len)
  304. {
  305.     int i;
  306.     for(i = (len-1)/2; i >= 0; i--)
  307.         heap_adjust(array,i,len);
  308.     for(  i = (len-1); i > 0; i--)
  309.     {
  310.         swap(array[0],array[i]);   //弹出最大值,重新对i-1个元素建堆
  311.         heap_adjust(array,0,i-1);
  312.     }
  313. }
  314. int main() {
  315.     int array[] = {45,56,76,234,1,34,23,2,3,55,88,100};
  316.     int len = sizeof(array)/sizeof(int);
  317.     //bubble_sort(array,len);           //冒泡排序
  318.     /*insert_sort(array,len);*/         //插入排序
  319.     /*bi_insert_sort(array,len);*/      //二路插入排序
  320.     
  321.     /*shell_sort(array,len);*/          //希尔排序 
  322.     /*quick_sort(array,0,len-1);*/      //快速排序
  323.     
  324.     /*select_sort(array,len);*/         //选择排序
  325.     /*merge_sort(array,0,len-1);*/      //归并排序
  326.     
  327.     heap_sort(array,len);               //堆排序
  328.     display(array,len);
  329.     return 0;
  330. }

抱歉!评论已关闭.