`
dyx1024
  • 浏览: 113435 次
  • 性别: Icon_minigender_1
  • 来自: 西安
文章分类
社区版块
存档分类
最新评论

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

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

相关推荐

    内部排序算法性能比较———c++

    五种内部排序算法性能比较, 1.直接插入排序算法。 2.简单选择排序。 3.希尔排序。 4.归并排序。5.快速排序。分别对交换次数,比较次数,移动次数,时长,时间复杂度进行性能比较。给出十万到百万级数据量的统计结果...

    C++数据结构知识点与经典算法整理

    3、C/C++实现 31 4、对排序算法的总结 41 11、数组和链表的优缺点 42 12、C++操作符优先级: 43 13、B树、B-树、B+树、B*树、红黑树和trie树 44 14、最小生成树算法之Prim算法(C++实现) 49 15、最小生成树之kruskal...

    C/C++笔试题(附答案,华为面试题系列)

    (1)不调用C++/C 的字符串库函数,请编写函数 strcat 答: VC源码: char * __cdecl strcat (char * dst, const char * src) { char * cp = dst; while( *cp ) cp++; /* find end of dst */ while( *cp++ = *src++ ...

    内部排序算法合集(插入、希尔、起泡、快速、选择、堆、归并和基数排序)

    内部排序合集(插入、希尔、起泡、快速、选择、堆、归并和基数排序) 这是我在我们期末的时候写的一些内部排序的例子。因为我们的数据结构考试的范围就限定在内部排序上,所以我没有什么办法,只好对自己埋头苦干就...

    C/C++实现八大排序算法汇总

    概述排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 我们这里说说八大排序就是内部排序。 当n较大,则...

    数据结构课程设计(内部排序算法比较)

    数据结构算法比较,经过C认证运行顺利,并附有实验报告,本人呕心沥血才弄出来的。

    内部排序算法计较.cpp

    C语言课程设计-实训-计算机内部算法性能比较。通过随机数据比较各算法的关键字比较次数和关键字移动次数,以去得直观感受

    c/c++ 学习总结 初学者必备

    B:写出下列算法的时间复杂度和实现排序: (1)冒泡排序; (2)选择排序; (3)插入排序; (4)快速排序; (5)堆排序; (6)归并排序; 23、编写gbk_strlen函数,计算含有汉字的字符串的长度,汉字作为一个字符处理;已知...

    快速排序算法

    快速排序算法(C语言版) #include #include "type.h" #define Q_SIZE 10 /************************************* 模块内部数组或变量定义 **************************************/ static UINT8 q_array[Q_...

    谭浩强C语言程序设计,C++程序设计,严蔚敏数据结构,高一凡数据结构算法分析与实现.rar

    4.3 数据输入输出的概念及在 C 语言中的实现 54 4.4 字符数据的输入输出 54 4.4.1 putchar 函数(字符输出函数) 54 4.4.2 getchar函数(键盘输入函数) 55 4.5 格式输入与输出 55 4.5.1 printf 函数(格式输出函数...

    c++中八大排序算法

    排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 我们这里说说八大排序就是内部排序。 当n较大,则应...

    谭浩强C语言程序设计,C++程序设计,严蔚敏数据结构,高一凡数据结构算法分析与实现.rar )

    4.3 数据输入输出的概念及在 C 语言中的实现 54 4.4 字符数据的输入输出 54 4.4.1 putchar 函数(字符输出函数) 54 4.4.2 getchar函数(键盘输入函数) 55 4.5 格式输入与输出 55 4.5.1 printf 函数(格式输出函数...

    【STL源代码】C++标准库STL源代码下载

    【STL源代码】中包含了许多常用的数据结构(如vector、list、map等)和算法(如排序、查找、遍历等)。通过阅读代码可以仔细研究这些数据结构和算法的实现,了解它们的内部工作原理和使用方式。

    77G 22套C语言 C++ 数据结构 程序设计视频课程合集 C丨C++相关学习视频全套视频教程

    数据结构与算法_C语言 01.swap.mp4 02.BubbleSort.mp4 03.SelecttionSort.mp4 04.顺序查找.mp4 05.C_DS_折半查找.mp4 06.递归.mp4 07递归算法_折半查找.mp4 08.Permutations.mp4 09.插入排序.mp4 10.快速...

    数据结构程序设计

    实验一 一元稀疏多项式的计算 实验二 长整数四则运算 实验四 算术表达式求值 实验七 哈夫曼编/译码器实验指导书 实验八 最短路径实验指导书 实验十 内部排序算法比较实验指导书

    数据结构(C、C++)演示系统

    这是一个数据结构演示系统,具体语言可以选择C(C++)和Pascal语言。可以动态演示各种算法,有两个基本作用: 1、理解算法 2、验证算法结果 无论是对老师上课,还是学生自学,都有很大帮助。程序运行的每一步都以...

    C++数据结构与算法 第四版

    在编写程序之前,必须清楚地了解如何通过程序实现所要完成的任务。因此,在编写代码之前,应列出程序的提纲,...然而,诸如C+ +之类的面向对象语言(OOL)与抽象数据类型有着直接的联系,这种语言将OOL作为-个类来实现。

    数据结构算法演示.zip

    该程序以动画的形式向学习者展示各种算法的执行过程,帮助学习者...包括顺序表、链表、栈、串、稀疏矩阵、广义表、二叉树、图、存储管理、静态查找、动态查找、内部排序、外部排序等。使用语言为C/C++以及Pascal语言。

    图书管理系统C++代码

    利用《数据结构》课程的相关知识完成一个具有一定难度的综合设计题目,利用C/C++语言进行程序设计,并规范地完成课程设计报告。通过课程设计,巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识...

Global site tag (gtag.js) - Google Analytics