LowB三人组--插入排序原理和java实现

「爱情、让人受尽委屈。」 2022-11-03 15:27 52阅读 0赞

### 文章目录 ###

*   *  插入排序原理图
     *  java实现代码
     *  复杂度

## 插入排序原理图 ##

[https://www.runoob.com/w3cnote/insertion-sort.html][https_www.runoob.com_w3cnote_insertion-sort.html]

![在这里插入图片描述][20210228213631638.gif_pic_center]

## java实现代码 ##

/** * 插入排序 */
    public class InsertionSortTest { 
        public static void main(String[] args) { 
            int[] arr = { 2,4,7,5,3,6,8,9,1};
            insertionSort(arr);
        }
    
        /** * 插入排序的原理: * 将待排序数组看成两部分: 有序数组和无序数组，初始时，第一次可以将第一张看成有序数组，其余作为无序数组 * 无序数组插入到有序数组中，遍历无序数组（无序数组个数就是需要插入的次数） * 将有序数组的右侧第一张和 无序的第一张， * 如果 从有序的右侧起: 获取无序的元素小于于有序的元素的第一个元素的索引，有序的这些元素向右移动一位 * 同时当前的索引值+1的位置就是 插入的元素 */
        public static void insertionSort(int[] arr){ 
            //外层为 要插入的元素
            for (int i=1;i<arr.length;i++){ 
                //有序位置的最后一个元素
                int tmp = arr[i];
                //获取要插入的元素的位置
                int j = i - 1;
                //从右侧起，获取第一个比要插入的元素小的元素的索引，索引右侧的值 右移一位
                while (j>=0 && arr[j]  > tmp){ 
                    arr[j+1] = arr[j];
                    //arr[j] = tmp;
                    j--;
                }
                arr[j+1] = tmp;
                System.out.println(Arrays.toString(arr));
            }
        }
    }

运行结果:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzIxMzQ5NjM1_size_16_color_FFFFFF_t_70]

## 复杂度 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzIxMzQ5NjM1_size_16_color_FFFFFF_t_70 1]

--------------------

完

[https_www.runoob.com_w3cnote_insertion-sort.html]: https://www.runoob.com/w3cnote/insertion-sort.html
[20210228213631638.gif_pic_center]: /images/20221023/3f419b55f7fa440490361f9e15e943aa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzIxMzQ5NjM1_size_16_color_FFFFFF_t_70]: /images/20221023/146cf07b45e74d40b7b530af9478801e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzIxMzQ5NjM1_size_16_color_FFFFFF_t_70 1]: /images/20221023/ecfac56d369e48c0838d2b17f59e1009.png