IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 数据结构与算法(Java篇)笔记--插入排序 -> 正文阅读

[数据结构与算法]数据结构与算法(Java篇)笔记--插入排序


前言

在我们的程序中,排序是非常常见的一种需求,提供一些数据元素,把这些数据元素按照一定的规则进行排序。比如查询一些订单,按照订单的日期进行排序;再比如查询一些商品,按照商品的价格进行排序等等。所以,接下来我们要学习一些常见的排序算法。


一、插入排序

插入排序(Insertion sort)是一种简单直观且稳定的排序算法。
需求:
排序前:{4,3,2,10,12,1,5,6}
排序后:{1,2,3,4,5,6,10,12}

二、排序原理

Step1.把所有的元素分为两组,已经排序的和未排序的;
Step2.找到未排序的组中的第一个元素,向已经排序的组中进行插入;
Step3.倒叙遍历已经排序的元素,依次和待插入的元素进行比较,直到找到一个元素小于等于待插入元素,那么就把待 插入元素放到这个位置,其他的元素向后移动一位;
在这里插入图片描述

API设计

类名Insertion
构造方法Insertion():创建Insertion对象
成员方法1.public static void sort(Comparable[] a):对数组内的元素进行排序
2.private static boolean greater(Comparable v,Comparable w):判断v是否大于w
3.private static void exch(Comparable[] a,int i,int j):交换a数组中,索引i和索引j处的值

1.代码实现

//排序代码
public class Insertion {
    /*
    	对数组a中的元素进行排序
    */
    public static void sort(Comparable[] a){
        for (int i=1;i<a.length;i++){
            //当前元素为a[i],依次和i前面的元素比较,找到一个小于等于a[i]的元素
            for (int j=i;j>0;j--){
                if (greater(a[j-1],a[j])){
                    //交换元素
                    exch(a,j-1,j);
                }else {
                    //找到了该元素,结束
                    break;
                }
            }
        }
    }
    /*
    	比较v元素是否大于w元素
    */
    private static boolean greater(Comparable v,Comparable w){
    	return v.compareTo(w)>0;	
    }
    /*
    	数组元素i和j交换位置
    */
    private static void exch(Comparable[] a,int i,int j){
        Comparable t = a[i];
        a[i]=a[j];
        a[j]=t;
    }
}

测试类

//测试代码
public class Test {
    public static void main(String[] args) {
        Integer[] a = {4,3,2,10,12,1,5,6};
        Insertion.sort(a);
        System.out.println("Selection sort " + Arrays.toString(a));
    }
}

2.运行结果

编写完成之后,点击运行就能知道选择排序的结果,如下图所示:
在这里插入图片描述


总结

插入排序使用了双层for循环,其中内层循环的循环体是真正完成排序的代码,所以,我们分析插入排序的时间复杂度,主要分析一下内层循环体的执行次数即可。按照大O推导法则,保留函数中的最高阶项那么最终插入排序的时间复杂度为O(N^2).

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-09-21 00:52:38  更:2022-09-21 00:53:32 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年12日历 -2024/12/28 18:40:01-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码
数据统计