找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

【算法篇】插入排序与希尔排序Java版

admin 2019-4-12 05:57 75人围观 C++相关

插入排序


时间复杂度:O(n²)

插入排序(Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用 in-place 排序(即只需用到 O(1) 的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。——维基百科

  1. publicvoid sort(int[] data){

  2. int tmp;

  3. int j;

  4. for(int p =1; p < data.length; p++){

  5. tmp = data[p];

  6. for(j = p; j >0&& data[j -1]> tmp; j--){

  7. data[j]= data[j -1];

  8. }

  9. data[j]= tmp;

  10. }

  11. }

希尔排序


原始的算法实现在最坏的情况下需要进行 O(n2) 的比较和交换。优化后性能提升至 O(n log2 n)。这比最好的比较算法的 O(n log n) 要差一些。

该算法是冲破二次时间屏障的第一批算法之一。希尔排序有时也叫做缩小增量排序(diminishing increment sort)。希尔排序使用一个序列 h1,h2,h3,...ht,叫做增量序列(increment sequence),只要 h1 = 1,任何增量序列都是可行的。

  1. publicvoid sort(int[] array){

  2. int number = array.length /2;

  3. int i;

  4. int j;

  5. int temp;

  6. while(number >=1){

  7. for(i = number; i < array.length; i++){

  8. temp = array[i];

  9. j = i - number;

  10. while(j >=0&& array[j]> temp){

  11. array[j + number]= array[j];

  12. j = j - number;

  13. }

  14. array[j + number]= temp;

  15. }

  16. number = number /2;

  17. }

  18. }

使用不同的增量序列时间复杂度也都各不相同。


----------------------------------------------------------------------------------------------------------------------
我们尊重原创,也注重分享,文章来源于微信公众号:张可,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
----------------------------------------------------------------------------------------------------------------------

鲜花

握手

雷人

路过

鸡蛋

yafeilinux和他的朋友们微信公众号二维码

微信公众号

专注于Qt嵌入式Linux开发等。扫一扫立即关注。

Qt开源社区官方QQ群二维码

QQ交流群

欢迎加入QQ群大家庭,一起讨论学习!

我有话说......


关于进行手机实名认证的紧急通知!
按照有关部门要求,论坛类网站必须完成手机实名认证才可以进行发帖等操作。希望大家积极配合,为创建一个和谐文明的社区而贡献自己的力量。我们会对会员的隐私进行严格保密,对大家造成的不便深表歉意! 我知道了