插入排序 | 黄皖's Blog

前言：

我们在玩打牌的时候，你是怎么整理那些牌的呢？一种简单的方法就是一张一张的来，将每一张牌插入到其他已经有序的牌中的适当位置。当我们给无序数组做排序的时候，为了要插入元素，我们需要腾出空间，将其余所有元素在插入之前都向右移动一位，这种算法我们称之为插入排序。

过程描述：

1、从数组第2个元素开始抽取元素。

2、把它与左边第一个元素比较，如果左边第一个元素比它大，则继续与左边第二个元素比较下去，直到遇到不比它大的元素，然后插到这个元素的右边。

3、继续选取第3，4，…n个元素,重复步骤 2 ，选择适当的位置插入。

动图：

实现代码：

package fg;

import java.util.Arrays;

public class InsertSort{

    public static void insertSort (int[] arr) {
        int j = 0;
        int temp = 0;                             //临时变量,用于交换
        for (int i = 1; i < arr.length; i++) {    //从第二数开始比较
            temp = arr[i];                        //将当前数插入到已经有序的数组中
            for (j = i - 1; j >= 0; j--) {
                if (arr[j] > temp) {              //如果前面的数大于当前数,将他后移
                    arr[j + 1] = arr[j];
                } else {                          //因为小于就不用管了嘛
                    break;
                }
            }
            arr[j + 1] = temp;                     //将当前轮数的数放到应该在的位置
        }


        System.out.println(Arrays.toString(arr));   //将其转换成数组
    }

    //测试代码
    public static void main (String[] args) {
        int[] arr = {9, 322, 22, 72, 33, 99};
        insertSort(arr);
    }
}