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

数据结构-选择排序笔记

article 2024/11/1 5:32:00

看里面的图解来理解

【数据结构】八大排序(超详解+附动图+源码)_数据结构排序-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++){
            // 将当前元素的值赋给insertVal
            int 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;
        }
    }
}