搜公众号
推荐 原创 视频 Java开发 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库
Lambda在线 > 张可 > 【算法篇】插入排序与希尔排序Java版

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

张可 2019-04-16
举报

插入排序

时间复杂度:O(n²)

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

 
   
   
 
  1. public void 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. public void 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. }

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


版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《【算法篇】插入排序与希尔排序Java版》的版权归原作者「张可」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注张可微信公众号

张可微信公众号:zhangke_blog

张可

手机扫描上方二维码即可关注张可微信公众号

张可最新文章

精品公众号随机推荐

举报