当前位置：网站首页>【21 Days Learning Challenge】Direct Insertion Sort

【21 Days Learning Challenge】Direct Insertion Sort

2022-08-04 04:16:00 【Alex holding popcorn】

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

怕什么真理无穷,进一步有一份的欢喜.

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

我为什么参与挑战赛

1,机缘

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

2,期待的收获

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

什么是排序？

在计算机科学中定义为：In the computer, a group is divided according to certain rules“无序”的数据元素调整为“有序”的数据元素.也就是说,我们是出于某种目的,Make it regular for a bunch of data,Generally divided into ascending and descending order.

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

Definition of Insertion Sort

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

Pros and cons of direct insertion sort

优势

简单,Insert data into an ordered table.

劣势

Direct insertion sort is made by 两层嵌套循环组成的.时间复杂度高,时间效率是O（n^2）.

Steps for direct insertion sort

每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序. 第一趟比较前两个数,然后把第二个数按大小插入到有序表中;
第二趟把第三个数据与前两个数从后向前扫描,把第三个数按大小插入到有序表中;依次进行下去,进行了(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位是有序的,如果第iBits are not in order for bit-seeking insertion,
        // Ignore if ordered,judge the next.
        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位的值
            }

        }
    }
}