数据结构 | 排序算法总结——(一)直接插入排序(附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方法
            }
        }
    }
}
相关文章
|
27天前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
41 1
|
28天前
|
存储 算法 搜索推荐
Python 中数据结构和算法的关系
数据结构是算法的载体,算法是对数据结构的操作和运用。它们共同构成了计算机程序的核心,对于提高程序的质量和性能具有至关重要的作用
|
14天前
|
存储 缓存 安全
Java 集合江湖:底层数据结构的大揭秘!
小米是一位热爱技术分享的程序员,本文详细解析了Java面试中常见的List、Set、Map的区别。不仅介绍了它们的基本特性和实现类,还深入探讨了各自的使用场景和面试技巧,帮助读者更好地理解和应对相关问题。
36 5
|
28天前
|
数据采集 存储 算法
Python 中的数据结构和算法优化策略
Python中的数据结构和算法如何进行优化?
|
1月前
|
算法
数据结构之路由表查找算法(深度优先搜索和宽度优先搜索)
在网络通信中,路由表用于指导数据包的传输路径。本文介绍了两种常用的路由表查找算法——深度优先算法(DFS)和宽度优先算法(BFS)。DFS使用栈实现,适合路径问题;BFS使用队列,保证找到最短路径。两者均能有效查找路由信息,但适用场景不同,需根据具体需求选择。文中还提供了这两种算法的核心代码及测试结果,验证了算法的有效性。
103 23
|
1月前
|
算法
数据结构之蜜蜂算法
蜜蜂算法是一种受蜜蜂觅食行为启发的优化算法,通过模拟蜜蜂的群体智能来解决优化问题。本文介绍了蜜蜂算法的基本原理、数据结构设计、核心代码实现及算法优缺点。算法通过迭代更新蜜蜂位置,逐步优化适应度,最终找到问题的最优解。代码实现了单链表结构,用于管理蜜蜂节点,并通过适应度计算、节点移动等操作实现算法的核心功能。蜜蜂算法具有全局寻优能力强、参数设置简单等优点,但也存在对初始化参数敏感、计算复杂度高等缺点。
60 20
|
26天前
|
存储 算法 程序员
C 语言递归算法:以简洁代码驾驭复杂逻辑
C语言递归算法简介:通过简洁的代码实现复杂的逻辑处理,递归函数自我调用解决分层问题,高效而优雅。适用于树形结构遍历、数学计算等领域。
|
27天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
61 1
|
1月前
|
存储 缓存 算法
通过优化算法和代码结构来提升易语言程序的执行效率
通过优化算法和代码结构来提升易语言程序的执行效率
|
1月前
|
算法
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码,实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。