热点推荐

查看: 1345|回复: 0
收起左侧

[资料] 八大排序算法总结

[复制链接]
  • TA的每日心情
    振奋
    昨天 22:32
  • 签到天数: 536 天

    连续签到: 1 天

    [LV.9]以坛为家II

    347

    主题

    1289

    帖子

    6126

    积分

    Rank: 9

    积分
    6126

    突出贡献优秀版主荣誉管理论坛元老优质会员最佳新人

    发表于 2016-10-12 10:58:07 | 显示全部楼层 |阅读模式

    51Halcon诚邀您的加入,专注于机器视觉开发与应用技术,我们一直都在努力!

    您需要 登录 才可以下载或查看,没有帐号?会员注册

    x

    1. 插入排序


    2. 1.直接插入排序

    3. 原理:将数组分为无序区和有序区两个区,然后不断将无序区的第一个元素按大小顺序插入到有序区中去,最终将所有无序区元素都移动到有序区完成排序。

    4. 要点:设立哨兵,作为临时存储和判断数组边界之用。

    5. 实现:

    6. Void InsertSort(Node L[],int length)

    7. {

    8. Int i,j;//分别为有序区和无序区指针

    9. for(i=1;i<length;i++)//逐步扩大有序区

    10. {

    11. j=i+1;

    12. if(L[j]<L[i])

    13. {

    14. L[0]=L[j];//存储待排序元素

    15. While(L[0]<L[i])//查找在有序区中的插入位置,同时移动元素

    16. {

    17. L[i+1]=L[i];//移动

    18. i--;//查找

    19. }

    20. L[i+1]=L[0];//将元素插入

    21. }

    22. i=j-1;//还原有序区指针

    23. }

    24. }

    25. 2.希尔排序

    26. 原理:又称增量缩小排序。先将序列按增量划分为元素个数相同的若干组,使用直接插入排序法进行排序,然后不断缩小增量直至为1,最后使用直接插入排序完成排序。

    27. 要点:增量的选择以及排序最终以1为增量进行排序结束。

    28. 实现:

    29. Void shellSort(Node L[],int d)

    30. {

    31. While(d>=1)//直到增量缩小为1

    32. {

    33. Shell(L,d);

    34. d=d/2;//缩小增量

    35. }

    36. }

    37. Void Shell(Node L[],int d)

    38. {

    39. Int i,j;

    40. For(i=d+1;i<length;i++)

    41. {

    42. if(L[i]<L[i-d])

    43. {

    44. L[0]=L[i];

    45. j=i-d;

    46. While(j>0&&L[j]>L[0])

    47. {

    48. L[j+d]=L[j];//移动

    49. j=j-d;//查找

    50. }

    51. L[j+d]=L[0];

    52. }

    53. }

    54. }

    55. 交换排序

    56. 1.冒泡排序

    57. 原理:将序列划分为无序和有序区,不断通过交换较大元素至无序区尾完成排序。

    58. 要点:设计交换判断条件,提前结束以排好序的序列循环。

    59. 实现:

    60. Void BubbleSort(Node L[])

    61. {

    62. Int i ,j;

    63. Bool ischanged;//设计跳出条件

    64. For(j=n;j<0;j--)

    65. {

    66. ischanged =false;

    67. For(i=0;i<j;i++)

    68. {

    69. If(L[i]>L[i+1])//如果发现较重元素就向后移动

    70. {

    71. Int temp=L[i];

    72. L[i]=L[i+1];

    73. L[i+1]=temp;

    74. Ischanged =true;

    75. }

    76. }

    77. If(!ischanged)//若没有移动则说明序列已经有序,直接跳出

    78. Break;

    79. }

    80. }

    81. 2.快速排序

    82. 原理:不断寻找一个序列的中点,然后对中点左右的序列递归的进行排序,直至全部序列排序完成,使用了分治的思想。

    83. 要点:递归、分治

    84. 实现:




    85. 选择排序

    86. 1.直接选择排序

    87. 原理:将序列划分为无序和有序区,寻找无序区中的最小值和无序区的首元素交换,有序区扩大一个,循环最终完成全部排序。

    88. 要点:

    89. 实现:

    90. Void SelectSort(Node L[])

    91. {

    92. Int i,j,k;//分别为有序区,无序区,无序区最小元素指针

    93. For(i=0;i<length;i++)

    94. {

    95. k=i;

    96. For(j=i+1;j<length;j++)

    97. {

    98. If(L[j]<L[k])

    99. k=j;

    100. }

    101. If(k!=i)//若发现最小元素,则移动到有序区

    102. {

    103. Int temp=L[k];

    104. L[k]=L[i];

    105. L[i]=L[temp];

    106. }



    107. }

    108. }

    109. 2.堆排序

    110. 原理:利用大根堆或小根堆思想,首先建立堆,然后将堆首与堆尾交换,堆尾之后为有序区。

    111. 要点:建堆、交换、调整堆

    112. 实现:

    113. Void HeapSort(Node L[])

    114. {

    115. BuildingHeap(L);//建堆(大根堆)

    116. For(int i=n;i>0;i--)//交换

    117. {

    118. Int temp=L[i];

    119. L[i]=L[0];

    120. L[0]=temp;

    121. Heapify(L,0,i);//调整堆

    122. }

    123. }




    124. Void BuildingHeap(Node L[])

    125. { For(i=length/2 -1;i>0;i--)

    126. Heapify(L,i,length);

    127. }

    128. 归并排序

    129. 原理:将原序列划分为有序的两个序列,然后利用归并算法进行合并,合并之后即为有序序列。

    130. 要点:归并、分治

    131. 实现:

    132. Void MergeSort(Node L[],int m,int n)

    133. {

    134. Int k;

    135. If(m<n)

    136. {

    137. K=(m+n)/2;

    138. MergeSort(L,m,k);

    139. MergeSort(L,k+1,n);

    140. Merge(L,m,k,n);

    141. }

    142. }




    143. 基数排序

    144. 原理:将数字按位数划分出n个关键字,每次针对一个关键字进行排序,然后针对排序后的序列进行下一个关键字的排序,循环至所有关键字都使用过则排序完成。

    145. 要点:对关键字的选取,元素分配收集。

    146. 实现:

    147. Void RadixSort(Node L[],length,maxradix)

    148. {

    149. Int m,n,k,lsp;

    150. k=1;m=1;

    151. Int temp[10][length-1];

    152. Empty(temp); //清空临时空间

    153. While(k<maxradix) //遍历所有关键字

    154. {

    155. For(int i=0;i<length;i++) //分配过程

    156. {

    157. If(L[i]<m)

    158. Temp[0][n]=L[i];

    159. Else

    160. Lsp=(L[i]/m)%10; //确定关键字

    161. Temp[lsp][n]=L[i];

    162. n++;

    163. }

    164. CollectElement(L,Temp); //收集

    165. n=0;

    166. m=m*10;

    167. k++;

    168. }

    169. }
    复制代码


    无效附件更新 权限提升操作 删帖申请 举报以及其他需要帮助请加入QQ群:214663141 广告位招商 有意者联系
    您需要登录后才可以回帖 会员登录 | 会员注册

    本版积分规则

    经营性网站备案信息 经营性网站
    备案信息

    中国互联网举报中心 中国互联网
    举报中心

    中国文明网传播文明 中国文明网
    传播文明

    诚信网站

    深圳市市场监督管理局企业主体身份公示 工商网监
    电子标识