当前位置：网站首页>【21天学习挑战赛】直接插入排序

【21天学习挑战赛】直接插入排序

2022-08-04 04:07:00 【Alex抱着爆米花】

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

怕什么真理无穷，进一步有一份的欢喜。

【21天学习挑战赛】直接插入排序

我为什么参与挑战赛

1，机缘

读到研一了，暑假器件打开私信发现这个挑战赛就鼓起勇气参加了。

2，期待的收获

A, 本人在华南理工大学攻读专硕，目前研究方向是图像恢复，从事深度学习相关工作，目标是从事Java后端开发。
B, 期待您的反馈，如果有什么不对的地方，欢迎指正！
C, 期待认识志同道合的领域同行或技术交流。
如果感觉博主的文章还不错的话，还请关注、点赞、收藏三连支持一下博主哦

什么是排序？

在计算机科学中定义为：计算机内根据一定规律将一组“无序”的数据元素调整为“有序”的数据元素。也就是说，我们是出于某种目的，对一堆数据让它变得富有规律，一般分为升序和降序。

升序：按从小到大的顺序排列(如1、3、5、6、7、9)。
降序：就是按从大到小的顺序排列(如9、8、6、4、3、1)。

直接插入排序的定义

将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增1的有序表。

直接插入排序的优劣

优势

简单，将数据插入有序表。

劣势

直接插入排序是由两层嵌套循环组成的。时间复杂度高，时间效率是O（n^2）。

直接插入排序的步骤

每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。第一趟比较前两个数，然后把第二个数按大小插入到有序表中；
第二趟把第三个数据与前两个数从后向前扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。

️ 算法实现

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;

public class InsertSort {
    
    public static void main(String[] args) {
    
        int[] arr = {
    9, 20, 15, 37, 28, 23};
        DirectInsertSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void DirectInsertSort(int[] arr) {
    
        //前第0位-第i-1位是有序的，如果第i位不是有序的进行寻位插入，
        // 如果是有序的就忽略，进行判断下一位。
        for (int i = 1; i < arr.length; i++) {
    
            if (arr[i] < arr[i - 1]) {
    
                int key = arr[i];
                int j = i - 1;
                //遍历前i-1位，寻找合适的位置
                while (j >= 0 && key < arr[j]){
    
                    arr[j+1] = arr[j];
                    j--;
                }
                arr[j+1]=key;//插入第i位的值
            }

        }
    }
}