转载：算法：插入排序InsertionSort
原文链接：https://zhuanlan.zhihu.com/p/104107073
我脱下短袖
公众号『算法无遗策』
已关注
插入排序
插入排序是比较简单也比较直接的一种排序算法。它是从一堆数据中取出一个数据并将它插入到已排序的数据中合适的位置。
比如按身高排队，有一个人指挥排队从第二个人开始，按身高把当前的人安插到之前排序好队的合适的位置。
或者打扑克牌，假设我们拿到了10，J，K，A这四张牌，然后拿到了Q这张牌，那如何让手中的五张牌变为升序呢？如果我们只学了冒泡排序和快速排序，初始状态是10，J，K，A，Q。
如果是用冒泡排序或者快速排序去做的话，那就可能不合适。结果是对，但是浪费了很多比较次数。
正常人最简单的方式就是，把Q安插到J和K之间就可以了。
插入排序正是如此，它的思想就是维护一个有序区，把元素一个一个插入到有序区中的合适的位置，直到所有元素有序为止。
视频动画
算法动画视频 地址 https://www.bilibili.com/video/av78480448/
[高清 720P] 插入排序和其优化（减少交换次数）_P1_插入排序 [最优化的质量和大小].flv
Code
package cn.study.sort;
import java.util.Arrays;
public class InsertionSort1 {
public static void insertionSort(int[] array){
for(int i = 1; i < array.length; i++){
for(int j = i; j > 0 && array[j] < array[j - 1]; j--){
swap(array, j, j - 1);
System.out.println("发生交换：" + Arrays.toString(array));
}
System.out.println(i + "趟" + Arrays.toString(array));
}
}
public static void swap(int[] array, int i, int j){
if(i == j){return;}
array[i] = array[i] ^ array[j];
array[j] = array[i] ^ array[j];
array[i] = array[i] ^ array[j];
}
public static void main(String[] args) {
int[] array = {5,1,3,7,4,6,2};
System.out.println("初始状态：" + Arrays.toString(array));
insertionSort(array);
System.out.println(Arrays.toString(array));
}
}
Result
初始状态 [5, 1, 3, 7, 4, 6, 2]发生交换 [1, 5, 3, 7, 4, 6, 2]1趟 [1, 5, 3, 7, 4, 6, 2]发生交换 [1, 3, 5, 7, 4, 6, 2]2趟 [1, 3, 5, 7, 4, 6, 2]3趟 [1, 3, 5, 7, 4, 6, 2]发生交换 [1, 3, 5, 4, 7, 6, 2]发生交换 [1, 3, 4, 5, 7, 6, 2]4趟 [1, 3, 4, 5, 7, 6, 2]发生交换 [1, 3, 4, 5, 6, 7, 2]5趟 [1, 3, 4, 5, 6, 7, 2]发生交换 [1, 3, 4, 5, 6, 2, 7]发生交换 [1, 3, 4, 5, 2, 6, 7]发生交换 [1, 3, 4, 2, 5, 6, 7]发生交换 [1, 3, 2, 4, 5, 6, 7]发生交换 [1, 2, 3, 4, 5, 6, 7]6趟 [1, 2, 3, 4, 5, 6, 7]
回顾一下上面代码运行的结果，发现有很多次的交换，会有一点一点的时间上的消耗。如果我们做减少交换次数的代码，那如何去写呢？
回顾一下快速排序那篇文章，也使用了减少交换次数的方法。它是一个一个待比较完之后，定位最大的元素或者最小的元素，然后进行交换。
插入排序把待插入的元素做一个标记，和有序区一个一个元素去做比较。假设是从待插入元素的邻近元素开始比较（从后往前），符合条件的前一个元素去复制粘贴到待插入元素的地址。直到不符合条件才插入到合适的位置。
视频动画
算法动画视频 地址 https://www.bilibili.com/video/av78480448?p=2
[高清 720P] 插入排序和其优化（减少交换次数）_P2_插入排序减少交换次数 [最优化的质量和大小].flv
Code
package cn.study.sort;
import java.util.Arrays;
public class InsertionSort1 {
public static void insertionSort(int[] array){
for(int i = 1; i < array.length; i++){
for(int j = i; j > 0 && array[j] < array[j - 1]; j--){
swap(array, j, j - 1);
System.out.println("发生交换：" + Arrays.toString(array));
}
System.out.println(i + "趟" + Arrays.toString(array));
}
}
//插入排序把待插入的元素做一个标记，和有序区一个一个元素去做比较。假设是从待插入元素的邻近元素开始比较（从后往前），符合条件的前一个元素去复制粘贴到待插入元素的地址。直到不符合条件才插入到合适的位置。
public static void insertionSortTwo(int[] array){
for (int i = 1; i < array.length; i++) {
int j = i;
int insertValue = array[i];
for(; j > 0 && insertValue < array[j - 1]; j--){
array[j] = array[j - 1];
System.out.println("发生复制：" + Arrays.toString(array));
}
array[j] = insertValue;
System.out.println(i + "趟" + Arrays.toString(array));
}
}
public static void swap(int[] array, int i, int j){
if(i == j){return;}
array[i] = array[i] ^ array[j];
array[j] = array[i] ^ array[j];
array[i] = array[i] ^ array[j];
}
public static void main(String[] args) {
int[] array = {5,1,3,7,4,6,2};
System.out.println("初始状态：" + Arrays.toString(array));
// insertionSort(array);
insertionSortTwo(array);
System.out.println(Arrays.toString(array));
}
}
Result
初始状态 [5, 1, 3, 7, 4, 6, 2]发生复制 [5, 5, 3, 7, 4, 6, 2]1趟 [1, 5, 3, 7, 4, 6, 2]发生复制 [1, 5, 5, 7, 4, 6, 2]2趟 [1, 3, 5, 7, 4, 6, 2]3趟 [1, 3, 5, 7, 4, 6, 2]发生复制 [1, 3, 5, 7, 7, 6, 2]发生复制 [1, 3, 5, 5, 7, 6, 2]4趟 [1, 3, 4, 5, 7, 6, 2]发生复制 [1, 3, 4, 5, 7, 7, 2]5趟 [1, 3, 4, 5, 6, 7, 2]发生复制 [1, 3, 4, 5, 6, 7, 7]发生复制 [1, 3, 4, 5, 6, 6, 7]发生复制 [1, 3, 4, 5, 5, 6, 7]发生复制 [1, 3, 4, 4, 5, 6, 7]发生复制 [1, 3, 3, 4, 5, 6, 7]6趟 [1, 2, 3, 4, 5, 6, 7]
喜欢本文的朋友，微信搜索「算法无遗策」公众号，收看更多精彩的算法动画文章
