插入排序

1.简介：

插入排序是一种简单直观且稳定的排序算法。它的最坏时间复杂度为O(n²)，最好时间复杂度为O(n)，平均时间复杂度为O(n²)，它是稳定排序。

基本思想：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

2.算法原理：

• 从第一个元素开始，该元素可以认为已经被排序；
• 取出下一个元素，在已经排序的元素序列中从后向前扫描；
• 如果该元素（已排序）大于新元素，将该元素移到下一位置；
• 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置（如果待插入的元素与有序序列中的某个元素相等，待插入元素插入到相等元素的前后皆可。）；
• 将新元素插入到该位置后；
• 重复步骤2~5。

结合动态图理解一下：

（图片来源：十大经典排序算法（动图演示））

3.代码实现：

    public static void  chaRu(int[] arr) {
        // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
        for (int i = 1; i < arr.length; i++) {
            // 记录要插入的数据
            int tmp = arr[i],j;
            // 从已经排序的序列最右边的开始比较，找到比其小的数
            for(j = i;j > 0 && arr[j-1] > tmp;j--)
                arr[j] = arr[j-1];
            // 存在比其小的数，插入
            arr[j] = tmp;
        }
    }

测试一波：

package sort;
/**
 * @author yzh
 * @date 2019-07-17 2:02
 */
public class ChaRu {
    public static void  chaRu(int[] arr) {
        // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
        for (int i = 1; i < arr.length; i++) {
            // 记录要插入的数据
            int tmp = arr[i],j;
            // 从已经排序的序列最右边的开始比较，找到比其小的数
            for(j = i;j > 0 && arr[j-1] > tmp;j--)
                arr[j] = arr[j-1];
            // 存在比其小的数，插入
            arr[j] = tmp;
        }
    }
    public static void main(String[] args) {
        int[] arr = {24,-4,754,76,24};
        chaRu(arr);
        for(int i = 0;i < arr.length;i++){
            System.out.println(arr[i]);
        }
    }
}

测试结果：

4.优缺点：

• 优点：稳定，快；
• 缺点：比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量庞大的时候，但用链表可以解决这个问题。