数据结构 | 排序算法总结——(一)直接插入排序(附Java实现代码)

简介: 数据结构 | 排序算法总结——(一)直接插入排序(附Java实现代码)

1.1排序基本概念

排序:重新排列表中的元素,使表中的元素满足按关键字递增或递减的过程。

算法的稳定性:如果待排序表中有两个元素Ri、Rj,其对应的关键字keyi=keyj,且在排序前Ri在Rj前面,如果使用某一排序算法排序后,Ri仍在Rj的前面,则称这个排序算法是稳定的。

分类:在排序过程中,根据数据元素是否完全在内存中,可将排序算法分为两类。

       内部排序:在排序期间元素全部存放在内存中的排序。

外部排序:在排序期间元素无法全部同时存放在内存中,必须在排序过程中根据要求不断地在内外存之间移动的排序。

1.2插入排序

基本思想:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子序列中,直到全部记录完成。

1.2.1直接插入排序

原理:把n个待排序的元素看成一个有序表和一个无需表,开始的时候有序表只有1个元素,无序表中有n-1个元素每次从无序表中取出第一个元素,将它插入到有序表中,使之成为新的有序表,重复n-1次完成整个排序过程。

具体流程如下:

  1. 首先比较数组的前两个数据,并排序;
  2. 比较第三个元素与前两个排好序的数据,并将第三个元素放入适当的位置;
  3. 比较第四个元素与前三个排好序的数据,并将第四个元素放入适当的位置;
  4. 直至把最后一个元素放入适当的位置
  5. 实例:


0.初始状态 3,1,5,7,2,4,9,6(共8个数)

有序表:3;无序表:1,5,7,2,4,9,6

1.第一次循环,从无序表中取出第一个数 1,把它插入到有序表中,使新的数列依旧有序

有序表:1,3;无序表:5,7,2,4,9,6

2.第二次循环,从无序表中取出第一个数 5,把它插入到有序表中,使新的数列依旧有序

有序表:1,3,5;无序表:7,2,4,9,6

3.第三次循环,从无序表中取出第一个数 7,把它插入到有序表中,使新的数列依旧有序

有序表:1,3,5,7;无序表:2,4,9,6

4.第四次循环,从无序表中取出第一个数 2,把它插入到有序表中,使新的数列依旧有序

有序表:1,2,3,5,7;无序表:4,9,6

5.第五次循环,从无序表中取出第一个数 4,把它插入到有序表中,使新的数列依旧有序

有序表:1,2,3,4,5,7;无序表:9,6

6.第六次循环,从无序表中取出第一个数 9,把它插入到有序表中,使新的数列依旧有序

有序表:1,2,3,4,5,7,9;无序表:6

7.第七次循环,从无序表中取出第一个数 6,把它插入到有序表中,使新的数列依旧有序

有序表:1,2,3,4,5,6,7,9;无序表:(空)

性能分析:

空间效率:仅使用常数个辅助单元,空间复杂度O(1)

时间效率:时间复杂度O(n2)

    最差情况:反序,需要移动n*(n-1)/2个元素,时间复杂度O(n2)

               最好情况:正序,不需要移动元素,时间复杂度O(n)

稳定性:稳定的

适用性:适用于顺序存储和链式存储的线性表

import java.util.Scanner;
import java.util.Arrays;
public class InsertSort {
    public static void insertSort(int[] arr){
        int i=0,j=0,temp=0;//定义变量i,j,temp并初始化
        for (i=1;i<arr.length;i++){//从第二个开始比较
            temp = arr[i];
            for (j=i-1;j>=0;j--){
                if (arr[j]>temp){//如果前面的数大于当前数,将它后移
                    arr[j+1] = arr[j];
                }else {
                    break;
                }
            }
            arr[j+1] = temp;//一轮比较结束,将此轮确定元素放到正确位置
        }
        System.out.println("直接插入排序:"+Arrays.toString(arr));
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);//Scanner工具类键盘输入数据
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            if (n > 0) {
                int arr[] = new int[n];
                for (int i = 0; i < n; i++) {
                    arr[i] = scanner.nextInt();
                }
                insertSort(arr);//调用直接插入排序insertSort方法
            }
        }
    }
}
相关文章
|
6天前
|
机器学习/深度学习 算法 Java
[算法与数据结构] 谈谈线性查找法~
该文章详细介绍了线性查找法的基本概念与实现方法,通过Java代码示例解释了如何在一个数组中查找特定元素,并分析了该算法的时间复杂度。
|
26天前
|
存储 算法 C语言
数据结构基础详解(C语言):单链表_定义_初始化_插入_删除_查找_建立操作_纯c语言代码注释讲解
本文详细介绍了单链表的理论知识,涵盖单链表的定义、优点与缺点,并通过示例代码讲解了单链表的初始化、插入、删除、查找等核心操作。文中还具体分析了按位序插入、指定节点前后插入、按位序删除及按值查找等算法实现,并提供了尾插法和头插法建立单链表的方法,帮助读者深入理解单链表的基本原理与应用技巧。
|
26天前
|
存储 C语言 C++
数据结构基础详解(C语言) 顺序表:顺序表静态分配和动态分配增删改查基本操作的基本介绍及c语言代码实现
本文介绍了顺序表的定义及其在C/C++中的实现方法。顺序表通过连续存储空间实现线性表,使逻辑上相邻的元素在物理位置上也相邻。文章详细描述了静态分配与动态分配两种方式下的顺序表定义、初始化、插入、删除、查找等基本操作,并提供了具体代码示例。静态分配方式下顺序表的长度固定,而动态分配则可根据需求调整大小。此外,还总结了顺序表的优点,如随机访问效率高、存储密度大,以及缺点,如扩展不便和插入删除操作成本高等特点。
|
26天前
|
存储 C语言
数据结构基础详解(C语言): 栈与队列的详解附完整代码
栈是一种仅允许在一端进行插入和删除操作的线性表,常用于解决括号匹配、函数调用等问题。栈分为顺序栈和链栈,顺序栈使用数组存储,链栈基于单链表实现。栈的主要操作包括初始化、销毁、入栈、出栈等。栈的应用广泛,如表达式求值、递归等场景。栈的顺序存储结构由数组和栈顶指针构成,链栈则基于单链表的头插法实现。
151 3
|
26天前
|
存储 算法 C语言
C语言手撕数据结构代码_顺序表_静态存储_动态存储
本文介绍了基于静态和动态存储的顺序表操作实现,涵盖创建、删除、插入、合并、求交集与差集、逆置及循环移动等常见操作。通过详细的C语言代码示例,展示了如何高效地处理顺序表数据结构的各种问题。
|
2月前
|
算法
【初阶数据结构篇】二叉树算法题
二叉树是否对称,即左右子树是否对称.
|
2月前
|
算法 索引
【初阶数据结构篇】单链表算法题进阶
深拷贝应该正好由 n 个全新节点组成,其中每个新节点的值都设为其对应的原节点的值。
|
5天前
|
算法 安全 测试技术
golang 栈数据结构的实现和应用
本文详细介绍了“栈”这一数据结构的特点,并用Golang实现栈。栈是一种FILO(First In Last Out,即先进后出或后进先出)的数据结构。文章展示了如何用slice和链表来实现栈,并通过golang benchmark测试了二者的性能差异。此外,还提供了几个使用栈结构解决的实际算法问题示例,如有效的括号匹配等。
golang 栈数据结构的实现和应用
01_设计一个有getMin功能的栈
01_设计一个有getMin功能的栈
|
6天前
|
前端开发
07_用队列实现栈
07_用队列实现栈
下一篇
无影云桌面