算法排序4——插入排序

简介: 每个元素要比较的是它之前的已排序的元素,并判断大小,所以再定义一个元素 j,从已排序组内从后往前比较;例如当 i = 5 的时候,其实是第6个位置,而 j = 5 的时候,由于从第一个开始计数,所以就表示第五个位置,恰好满足已排序组内的最后一个,终止值就是元素第一个

🟡前言


21天挑战赛第四天,本文将讲述有关插入排序的知识


活动地址:CSDN21天学习挑战赛


🟡概述


1️⃣排序原理


1.将元素分为已排序的和未排序的两组

2.找到未排序组中的第一个元素,插入已排序的组中

3.倒序遍历已排序元素,并依次比较

4.当找到比该元素小或者等于该元素的元素时,插入

5.将其余元素向后移动一位


2️⃣原理图


4a9e0a49ceaa40f2a3ff0d0a1ccd386a.gif

9d61b62d8bba43cab411089ecbdaf3be.png


🟡调用API解决


1️⃣构造方法和成员方法


构造方法


Insertion()


成员方法


  • public static void sort(Comparable[]a):对数组a中元素进行排序


  • public static boolean greater(Comparable x, Cpmparable y):判断x是否大于y;

一般使用时会这么写:x.compareTo(y) ,再判断值是否 >0 , >0则表示 x>y


  • public static void exch(Comparable[]a, int i, int j):交换数组a中下标为 i 和 j 的元素


2️⃣解题思路


1.想要对数组内元素进行排序,就要调用 public static void sort(Comparable[]a)


2.排序时从第二个元素开始,依次将后面的每个元素进行排序,所以要调用一个for循环语句来执行,终止条件就是最后一个元素,即 i < a.length


3.每个元素要比较的是它之前的已排序的元素,并判断大小,所以再定义一个元素 j,从已排序组内从后往前比较;

例如当 i = 5 的时候,其实是第6个位置,而 j = 5 的时候,由于从第一个开始计数,所以就表示第五个位置,恰好满足已排序组内的最后一个,终止值就是元素第一个


4.当前一个元素更小时,交换两者;由于比较的是已排序好的元素,所以当碰到前者更小的时候就不用比较,直接退出循环


5.转换成字符串类型后打印输出


3️⃣代码实现


public class InsertionSort {
    public static void sort(Comparable[] a) {
        for(int i = 1; i < a.length; i++){
            for(int j = i; j > 0; j--){
                if(greater(a[j-1], a[j])){
                    exch(a,j,j-1);
                }
            }
        }
    }
    private static boolean greater(Comparable x, Comparable y){
        return x.compareTo(y) > 0;
    }
    private static void exch(Comparable[] a, int i, int j){
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}
import java.util.Arrays;
public class InsertionSortTest {
    public static void main(String[] args) {
        Integer[] arr = {4,3,2,10,12,1,5,6};
        BubbleSort.sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

f1c748bd3a58451e932cad8255ebc122.png


🟡时间复杂度


比较元素:(n-1) + (n-2) + … + 2 + 1 = 1/2 * (n^2 - n)

交换元素:(n-1) + (n-2) + … + 2 + 1 = 1/2 * (n^2 - n)

总计:n^2 - n

时间复杂度为:O(n^2)


🟡结语


插入排序也较简单基础,接下来会介绍高级排序


相关文章
|
3月前
|
算法
【算法】二分查找——在排序数组中查找元素的第一个和最后一个位置
【算法】二分查找——在排序数组中查找元素的第一个和最后一个位置
|
22天前
|
搜索推荐 Shell
解析排序算法:十大排序方法的工作原理与性能比较
解析排序算法:十大排序方法的工作原理与性能比较
37 9
|
15天前
|
算法 搜索推荐 Java
数据结构与算法学习十三:基数排序,以空间换时间的稳定式排序,速度很快。
基数排序是一种稳定的排序算法,通过将数字按位数切割并分配到不同的桶中,以空间换时间的方式实现快速排序,但占用内存较大,不适合含有负数的数组。
17 0
数据结构与算法学习十三:基数排序,以空间换时间的稳定式排序,速度很快。
|
15天前
|
算法 搜索推荐
数据结构与算法学习十一:冒泡排序、选择排序、插入排序
本文介绍了冒泡排序、选择排序和插入排序三种基础排序算法的原理、实现代码和测试结果。
13 0
数据结构与算法学习十一:冒泡排序、选择排序、插入排序
|
14天前
|
算法
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
27 0
|
19天前
|
搜索推荐 算法
【排序算法(一)】——插入排序,选择排序 —> 深层解析
【排序算法(一)】——插入排序,选择排序 —> 深层解析
|
21天前
|
存储 算法 搜索推荐
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
54 0
|
3月前
|
搜索推荐 算法 Java
现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int),已知类QuickSort的quickSort(int[])方法实现了快速排序算法
该博客文章通过UML类图和Java源码示例,展示了如何使用适配器模式将QuickSort类和BinarySearch类的排序和查找功能适配到DataOperation接口中,实现算法的解耦和复用。
28 1
现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int),已知类QuickSort的quickSort(int[])方法实现了快速排序算法
|
3月前
|
算法 搜索推荐 Java
算法实战:手写归并排序,让复杂排序变简单!
归并排序是一种基于“分治法”的经典算法,通过递归分割和合并数组,实现O(n log n)的高效排序。本文将通过Java手写代码,详细讲解归并排序的原理及实现,帮助你快速掌握这一实用算法。
41 0
|
3月前
|
算法 搜索推荐
算法设计 (分治法应用实验报告)基于分治法的合并排序、快速排序、最近对问题
这篇文章是关于分治法应用的实验报告,详细介绍了如何利用分治法实现合并排序和快速排序算法,并探讨了使用分治法解决二维平面上的最近对问题的方法,包括伪代码、源代码实现及时间效率分析,并附有运行结果和小结。