Java直接插入排序算法实现

下面是“Java直接插入排序算法实现”的完整攻略。

算法简介

直接插入排序,也叫插值排序,是对于插入排序算法的一种变形。与通常的插入排序不同之处在于,它可以在O(n)的时间内完成前n个元素的排序。类似于整理扑克牌,抓出一张新牌插入手中的牌序中。遍历未排序的元素,将其插入到已排序的序列中的正确位置。

算法步骤

  1. 从第一个元素开始,该元素可以认为已经被排序
  2. 取出下一个元素,插入到已经排序的元素序列中
  3. 对于新插入的元素,从后往前遍历已排序的序列
  4. 如果当前遍历到的元素大于新元素,则将大于新元素的元素往后移动一位
  5. 重复步骤3,4 直到找到正确的位置并插入元素
  6. 重复步骤2~5

Java代码实现

public class InsertionSort {
    public static void main(String[] args) {
        int arr[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
        insertionSort(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    public static void insertionSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j > 0 && temp < arr[j - 1]; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = temp;
        }
    }
}

算法分析

  • 平均时间复杂度为O(n²)
  • 空间复杂度为O(1)
  • 稳定排序

示例说明

示例一

输入:[3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]

输出:[1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

示例二

输入:[6, 5, 4, 3, 2, 1]

输出:[1, 2, 3, 4, 5, 6]

在以上示例中,我们可以看到插入排序成功将无序的数组进行排序,而且在示例一中,排序后结果依然保持了元素原本的相对位置不变,因此这种排序方法被称为稳定排序。

阅读剩余 37%

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:Java直接插入排序算法实现 - Python技术站

(0)
上一篇 2023年5月19日
下一篇 2023年5月19日

相关文章

  • Java内省实例解析

    Java内省实例解析 什么是Java内省? Java内省是指通过类提供的公共方法来访问类属性和方法的一种机制,用于实现Java Bean自省功能。 如何使用Java内省? Java内省通过Java自带的Introspector类实现。Introspector类提供了丰富的API,用于获取和操作Java Bean中的属性、方法等。 获取Java Bean信息 …

    Java 2023年6月15日
    00
  • Spring Security OAuth2 token权限隔离实例解析

    Spring Security OAuth2 token权限隔离实例解析 在本文中,将介绍如何使用Spring Security来实现OAuth2 token的权限隔离。我们将阐述基于Spring Boot的实现方式及其持久化方案,并提供两条示例。 情境描述 假设一个应用程序需要提供给多个客户端进行访问,而每个客户端都有自己的用户组并需要访问特定的资源。在这…

    Java 2023年5月20日
    00
  • MyBatis集成Spring流程详解

    MyBatis集成Spring流程详解 本文将详细介绍如何将MyBatis与Spring整合,以提高Web应用程序的性能和可维护性。 前置条件 在开始本文之前,确保您已经安装了以下环境: Java JDK 1.8或更高版本 Apache Maven 3.6或更高版本 Eclipse IDE或IntelliJ IDEA IDE(任意一个都可以) 此外,您还需要…

    Java 2023年5月19日
    00
  • Java反射机制的学习总结

    Java反射机制的学习总结 什么是Java反射机制? Java反射机制是指在程序运行时动态获取类的信息以及动态调用对象的方法的机制。 我们在开发中常常需要在运行时动态地加载和使用类,例如在插件系统中使用的动态加载和使用各种插件类的方式,这就需要用到Java反射机制。 通过利用Java反射机制,程序可以在不知道具体类名的情况下,获取类的相关信息,创建对象实例,…

    Java 2023年6月1日
    00
  • JSP分页显示的实例代码

    JSP分页显示的实例代码需要以下步骤: 1. 准备数据 首先,我们需要准备一些数据,以便在JSP页面中分页显示。可以从数据库中查询相关数据,或者手动设置一些数据。 int pageSize = 5; //每页显示5条数据 int currentPage = 1; //当前页码 List<String> dataList = new ArrayLi…

    Java 2023年6月15日
    00
  • Java实现计网循环冗余检验算法的方法示例

    让我详细介绍一下“Java实现计网循环冗余检验算法的方法示例”的攻略。这里我将分为以下几个方面进行讲解: 简介及算法原理 Java代码实现步骤 示例说明1 示例说明2 总结 1. 简介及算法原理 CRC(Cyclic redundancy check)即循环冗余校验码,是一种基于校验码的数据传输完整性检查方法。它能够检测出所有单个比特以及更多数量的比特出错。…

    Java 2023年5月19日
    00
  • Java基础之教你怎么用代码一键生成POJO

    下面是Java基础之教你怎么用代码一键生成POJO的完整攻略。 简介 POJO指的是“普通Java对象”(Plain Old Java Object),它是一种基础的Java类,通常用于存储数据。在实际开发中,我们需要大量地编写POJO,这个过程比较繁琐。因此,我们可以使用一些工具,来快速地生成POJO的代码。本文将介绍一种使用IDEA插件一键生成POJO的…

    Java 2023年5月19日
    00
  • Java实现读取项目中文件(.json或.properties)的方法详解

    下面我将为您详细讲解Java实现读取项目中文件(.json或.properties)的方法。 读取.properties文件的方法 1. 新建Properties对象并加载文件 Properties properties = new Properties(); InputStream inputStream = getClass().getClassLoad…

    Java 2023年5月20日
    00
合作推广
合作推广
分享本页
返回顶部