五、Java版直接插入排序

一、核心思想

抽出一个元素，在其前面的元素中找到适当的位置进行插入。
插入排序法：所谓插入排序法乃是将一个数目插入该占据的位置。

假设我们输入的是 “53，27，36，15，69, 42” 我们从第二个数字开始，这个数字是27，我们的任务只要看看27有没有正确的位置，我们的做法是和这个数字左边的数字来比，因此我们比较27和53，27比53小，所以我们就交换27和53，原来的排列就变成了“27, 53, 36, 15, 69, 42 ”

接下来，我们看第3个数字有没有在正确的位置。这个数字是36，它的左边数字是53，36比53小，所以我们将36和53交换，排列变成了 “27,36, 53, 15, 69, 42 "我们必须继续看36有没有在正确的位置，36的左边是27，27比36小，36就维持不动了,这时候排序还是“27, 36, 53, 15, 69, 42 "。

再来看第四个数字，这个数字是15，我们将15和它左边的数字相比，都比15大，所以就将15一路往左移动，这时候排序变成了 “15, 27, 36, 53, 69, 42 ”。

再来看第五个数字，这个数字是69，我们将69和它左边的数字相比，都比69小，所以就69维持不动了，这时候排序变成了 “15, 27, 36, 53, 69, 42 ”

最后，我们检查第六个数字，这个数字是42，42必须往左移，一直移到42的左边是36为止，所以我们的排列就变成了 “15, 27, 36, 42 ,53, 69”排序因此完成了。

image.png

二、源码

package com.ctw;

/**
 * @author TongWei.Chen 2018-09-26 14:16:52
 * @Description:
 * @Project sjjg-sf
 */
public class InsertSort {

    public static void insertSort(long[] array) {
        int i, j;
        // 要插入的数据
        long insertNode;
        // 从数组的第二个元素开始循环将数组中的元素插入
        for (i = 1; i < array.length; i ++) {
            // 设置数组中的第二个元素为第一次循环要插入的数据
            insertNode = array[i];
            j = i - 1;
            // 若要插入的元素小于第j个元素，则将第j个元素向后移动
            while ((j >= 0) && insertNode < array[j]) {
                array[j + 1] = array[j];
                j --;
            }
            // 直到要插入的元素不小于第j个元素，将insertNode插入到数组中
            array[j + 1] = insertNode;
        }
    }

    public static void main(String[] args) {
        MyArray array = new MyArray();
        array.add(111L);
        array.add(13L);
        array.add(31L);
        array.add(211L);
        array.add(11L);
        array.add(12L);
        array.add(23L);
        array.add(31L);
        array.add(41L);
        array.add(551L);

        insertSort(array.getArr());

        array.display();
    }

}

三、广告

• 码云地址

  https://gitee.com/geekerdream/google-guava/

• QQ群【Java初学者学习交流群】：458430385

• 微信公众号【Java码农社区】

  img

• 今日头条号：编程界的小学生