从零开始数据结构与算法(三)之插入排序

3.插入排序

实现思想：插入排序也称为直接插入排序，默认从第二个开始比较，如果当前的数比前面的数(大或小)，则交换位置；依次类推，比较前面并交换前面所有的数，直到不需要交换了为止()。因为前面的数据都是有序的。

插入排序与选择排序的区别：①同样是分为了有序列表与无序列表，选择排序是将有序列表的最小值参照物与后面无序列表的所有数进行比较，查找真正的最小值；而插入排序是寻找升序(大于前一个数，小于后一个数)/降序的临界条件为止，因为有序列表是有序的，因此节省了遇到临界条件后的排序过程。②选择排序是不稳定的(改变了相同值的元素位置)，插入排序是稳定的。

简单来说：选择排序就是在无序列表进行比较，找最小值；插入排序就是在有序列表中比较，找临界值。

如何判断：以当前元素为标准，[0, i]为有序列表，[i+1, arr.length-1]为无序列表。选择排序是j++，插入排序是j--。

package deepinsea.十大经典排序算法;

import java.util.Arrays;

/**
 * @author deepinsea
 */
public class 插入排序 {

    public static void main(String[] args) {
        int[] arr = new int[]{1, 6, 2, 4, 3, 5, 7, 8, 9};
        System.out.println(Arrays.toString(arr));
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 插入排序
     */
    public static int[] insertSort(int[] arr) {
        // 外循环，遍历所有的元素
        for (int i = 1; i < arr.length; i++) {
            // 内循环，寻找元素 arr[i] 合适的插入位置(临界值)
            for (int j = i; j > 0; j--) {
                // 小于前一个数，则交换顺序;否则，结束循环
                if (arr[j] < arr[j - 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                } else
                    break;
            }
        }
        return arr;
    }
}