专栏首页CherishTheYouth排序算法Java代码实现(三)—— 插入排序 和 希尔排序

排序算法Java代码实现(三)—— 插入排序 和 希尔排序

因为希尔排序的核心思想是插入排序,所以本篇将两篇排序一起记录

本篇内容:

  • 插入排序
  • 希尔排序

(一)插入排序

算法思想:

把n个待排序的元素看成一个有序表和一个无序表,开始时有序表中只有一个元素,无序表中有n-1个元素;

排序过程即每次从无序表中取出第一个元素,将它插入到有序表中,使之成为新的有序表,重复n-1次完成整个排序过程。

代码实现:

(注意:ArrayBase在第一篇中已给出代码)

/**
 * 
 */
package com.cherish.SortingAlgorithm;

/**
 * @author acer
 *
 */
public class Chapter_3_插入排序 extends ArrayBase {

    /**
     * 
     */
    public Chapter_3_插入排序() {
        // TODO 自动生成的构造函数存根
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO 自动生成的方法存根
        int[] array = new int[] {3,4,7,9,2,5,1,8,6};
        printArray(array);
        insertSorting(array);
        printArray(array);
    }
    
    /*
     * 把n个待排序的元素看成一个有序表和一个无序表,开始时有序表中只有一个元素,无序表中有n-1个元素;
     * 排序过程即每次从无序表中取出第一个元素,将它插入到有序表中,使之成为新的有序表,重复n-1次完成整个排序过程。
     * */
    public static void insertSorting(int[] array) {
        // TODO 自动生成的方法存根
        int arrayLength = array.length;
        for(int i = 1 ; i < arrayLength ; i++)
        {
            for(int j = i ; j > 0;j--)
            {
                if(array[j]<array[j-1])
                {
                    swap(array,j,j-1);
                }
                
            }
            printArray(array);
        }
    }
}

实现结果:

(二)希尔排序

算法思想:

希尔排序的实质就是分组插入排序,又称缩小增量法;

将整个无序序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,

然后依次缩减增量再进行排序,待整个序列中的元素基本有序时,再对全体元素进行一次直接插入排序。

因为直接插入排序在元素基本有序的情况下,效率是很高的,因此希尔排序在时间效率上有很大提高

/**
 * 
 */
package com.cherish.SortingAlgorithm;

/**
 * @author acer
 *
 */
public class Chapter_4_希尔排序 extends ArrayBase {

    /**
     * 
     */
    public Chapter_4_希尔排序() {
        // TODO 自动生成的构造函数存根
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        int[] array = new int[] {3,4,7,9,2,5,1,8,6};
        printArray(array);
        shellSorting(array);
        printArray(array);        
    }
    
    
    /*
     * 希尔排序的实质就是分组插入排序,又称缩小增量法
     * 将整个无序序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,
     * 然后依次缩减增量再进行排序,待整个序列中的元素基本有序时,再对全体元素进行一次直接插入排序。
     * 因为直接插入排序在元素基本有序的情况下,效率是很高的,因此希尔排序在时间效率上有很大提高
     * */
    public static void shellSorting(int[] array)
    {
        int arrayLength = array.length;//数组长度
        int gap = arrayLength/2;//子序列数
        while(gap>=1)
        {
            for(int i = gap;i < arrayLength;i++)
            {
            //    int j=i-gap;
                for(int j = i-gap;j>=0;j--)
                {
                    if(array[j]>array[i])
                    {
                        swap(array,j,i);
                    }    
                }                            
            }
            gap = gap/2;
            printArray(array);
        }
    }
}

实现结果:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 一个完整机器学习项目流程总结

    现在机器学习应用越来越流行,了解机器学习项目的流程,能帮助我们更好的使用机器学习工具来处理实际问题。

    统计学家
  • TNW-授权获取用户信息

    TNW: TypeScript(The) + Node.js(Next) + WeChat 微信公众号开发脚手架,支持任何 Node.js 的服务端框架(Exp...

    Javen
  • Java-static用法

    运行结果: 杭州阿里巴巴 ########### 深圳腾讯 ########### 杭州网易

    Fisherman渔夫
  • Java-方法重载时 调用未定义的对象属性

    public class TestWayReload { int id; String name; String pwd; public TestWay...

    Fisherman渔夫
  • 【AI in 美团】深度学习在文本领域的应用

    AI(人工智能)技术已经广泛应用于美团的众多业务,从美团App到大众点评App,从外卖到打车出行,从旅游到婚庆亲子,美团数百名最优秀的算法工程师正致力于将AI技...

    石晓文
  • 旅行商问题的近似算法之最近邻法(Nearest Neighbor) C语言实现

    另外,实际设计算法时,有一个常用的Idea就是我们用构筑法生成初始解放到改善法里去Improve。

    短短的路走走停停
  • Dynamics-Aware Unsupervised Discovery of Skills 笔记

    关键词:model-base、 model-free、 entropy 、mutual-info、 abstract 、skill-action、 goal-...

    用户1908973
  • Java-Object类的继承和重写

    注意要点: 一、我们得继承再重写,而Object是我们默认继承的,无需用extends语言 二、和.class文件相同名字的类,也是类,所以在内既可以定义m...

    Fisherman渔夫
  • 4399AT功能更新-12.6

    增加数据池和随机值,通过关键词 values,random,count进行搭配进行使用。场景:1.搜索多个游戏名称,来校验是否能搜索出输相应的游戏,进而校验数据...

    厦门-安仔
  • Java--==和equals的普遍重写

    运行结果: false ################# true ################# false ###############...

    Fisherman渔夫

扫码关注云+社区

领取腾讯云代金券