当前位置：首页 > news >正文

数据结构-插入排序笔记

news 2024/11/4 16:20:48

看里面的图解来理解

【数据结构】八大排序(超详解+附动图+源码)_数据结构排序-CSDN博客

一基本思想：

插入排序(Insertion Sorting)的基本思想是:把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

二代码实现

public class Main {// 主方法，程序的入口点public static void main(String[] args) {// 初始化一个整型数组，包含一些元素int arr[] = {221, 334, 300, 1};// 调用sort方法对数组进行排序sort(arr);// 遍历排序后的数组，并打印每个元素for(int i : arr){System.out.print(i + " ");}}/*
//        插入排序可以理解成，将一个数组分成两个部分，一边是有序的一边是无序的。
//        最开始我们将数组第一个元素arr【0】看成有序数组，然后后面的都是无序数组
//        将后面无序数组的元素按一定算法找到要插入的位置并且插入
//         */// 定义一个静态方法sort，用于对整型数组进行排序static void sort(int arr[]){// 外层循环，从数组的第二个元素开始遍历到最后一个元素for(int i = 1 ; i < arr.length; i++){// 将当前元素的值赋给insertValint insertVal = arr[i];// 初始化插入位置的索引为当前元素的前一个位置int insertIndex = i - 1;// 内层循环，用于将insertVal插入到已排序序列中的正确位置while(insertIndex >= 0 && insertVal < arr[insertIndex]){// 将当前位置的元素向后移动一位arr[insertIndex + 1] = arr[insertIndex];// 插入位置索引向前移动一位insertIndex--;}// 将insertVal插入到正确的位置arr[insertIndex + 1] = insertVal;}}
}