【算法学习】 六 插入排序
社长，一个爱学习，爱分享的程序猿，始终相信,付出总会有回报的。知识改变命运，学习成就未来。爱拼才会赢!可以关注我，跟我一起学习，一起进步。
1.什么是插入排序
插入排序（Insertion sort）是一种简单直观且稳定的排序算法。
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序。
2.排序原理
把数据切割成2部分，一部分是已经排序的（索引为0的元素，我们认为是已经排序的），还有一部分是没有排序的(索引从1开始的元素，我们认为是没有排序的)
取出未排序的元素，放入已排序的数组中
通过已排序数据的元素从后到前一个个比较,
分两种情况:,
(1)能找到比需要插入元素小的值，说明需要从待排序的那个位置开始，后面的每一个值都要向后移动一个位置。
(2)不能找到，说明不用动直到所有的数据都插入完成
社长给各位社友说说大致的思路。
插入排序，就是把 数据切割成两份，左边是有序的，右边是无序的。把无序数组的第一个元素，跟有序数组的从后到前依次比较。那为什么是从后到前比较？各位社友有没有想过？
而这时，我们隔壁的小王，就迫不及待的说，社长，社长，我知道。左边已经是排序好的，从后到前一个个比较，可以减少比较次数，这样性能也是最佳的。
不得不说，隔壁小王，说的真棒，社长给你点赞。
我们默认第一个元素就是有序的。为了方便了解，我把对应的过程，通过程序打印出来
排序的数组：[60, 71, 49, 11, 24, 3, 66]
待插入的值:71
待排序之前的数组：[60, 71, 49, 11, 24, 3, 66]
比较的值：71和60,71大，保持不变
第1轮:排序后的数组为：[60, 71, 49, 11, 24, 3, 66]
待插入的值:49
待排序之前的数组：[60, 71, 49, 11, 24, 3, 66]
比较的值：49和71,49大，交换位置
比较的值：49和60,49大，交换位置
第2轮:排序后的数组为：[49, 60, 71, 11, 24, 3, 66]
待插入的值:11
待排序之前的数组：[49, 60, 71, 11, 24, 3, 66]
比较的值：11和71,11大，交换位置
比较的值：11和60,11大，交换位置
比较的值：11和49,11大，交换位置
第3轮:排序后的数组为：[11, 49, 60, 71, 24, 3, 66]
待插入的值:24
待排序之前的数组：[11, 49, 60, 71, 24, 3, 66]
比较的值：24和71,24大，交换位置
比较的值：24和60,24大，交换位置
比较的值：24和49,24大，交换位置
比较的值：24和11,24大，保持不变
第4轮:排序后的数组为：[11, 24, 49, 60, 71, 3, 66]
待插入的值:3
待排序之前的数组：[11, 24, 49, 60, 71, 3, 66]
比较的值：3和71,3大，交换位置
比较的值：3和60,3大，交换位置
比较的值：3和49,3大，交换位置
比较的值：3和24,3大，交换位置
比较的值：3和11,3大，交换位置
第5轮:排序后的数组为：[3, 11, 24, 49, 60, 71, 66]
待插入的值:66
待排序之前的数组：[3, 11, 24, 49, 60, 71, 66]
比较的值：66和71,66大，交换位置
比较的值：66和60,66大，保持不变
第6轮:排序后的数组为：[3, 11, 24, 49, 60, 66, 71]
排序后的数组为：[3, 11, 24, 49, 60, 66, 71]
3.实战篇
话不多说，上代码。
插入排序工具类
package com.cxyxs.dilution.util;
import java.util.Arrays;
/**
* Description：转发请注明来源 程序猿学社 - https://ithub.blog.csdn.net/
* Author: 程序猿学社
* Date: 2020/2/8 18:38
* Modified By:
*/
public class InsertSortUtils {
public static int[] insertSort(int[] insertSorts){
//60,71,49,11,24,3,66
System.out.println("排序的数组："+Arrays.toString(insertSorts));
System.out.println();
for (int i = 1; i < insertSorts.length ; i++) {
System.out.println("待插入的值:"+insertSorts[i]);
System.out.println("待排序之前的数组："+ Arrays.toString(insertSorts));
for (int j = i; j > 0; j--) {
if(insertSorts[j]<insertSorts[j-1]){
System.out.println("比较的值："+ insertSorts[j]+"和"+insertSorts[j-1]+","+insertSorts[j]+"大，交换位置");
changeValue(j,j-1,insertSorts);
}else{
System.out.println("比较的值："+ insertSorts[j]+"和"+insertSorts[j-1]+","+insertSorts[j]+"大，保持不变");
break;
}
}
System.out.println("第"+i+"轮:"+"排序后的数组为："+Arrays.toString(insertSorts));
System.out.println();
}
return insertSorts;
};
/**
* 交换两个值
* @param before
* @param after
* @param insertSorts
*/
public static void changeValue(int before,int after,int[] insertSorts){
int temp=insertSorts[before];
insertSorts[before]=insertSorts[after];
insertSorts[after]=temp;
}
}
测试类
package com.cxyxs.dilution.test;
import com.cxyxs.dilution.util.InsertSortUtils;
import java.util.Arrays;
/**
* Description： 【算法与结构】- 插入排序
* 转发请注明来源 程序猿学社 - https://ithub.blog.csdn.net/
* Author: 程序猿学社
* Date: 2020/2/8 19:36
* Modified By:
*/
public class Test6 {
public static void main(String[] args) {
//插入排序测试方法
insertSort();
}
/**
* 插入排序测试方法
*/
public static void insertSort() {
int[] insertSorts = {60, 71, 49, 11, 24, 3, 66};
int[] ints = InsertSortUtils.insertSort(insertSorts);
System.out.println("排序后的数组为：" + Arrays.toString(ints));
}
}
注意：不要像社长一样命名Test6,这样命令，只是为了方面知道这个是算法和结构专栏学习第6章的测试类方法，仅此而已。
4.性能分析
怎么区分一个算法的好坏，我们可以通过看时间复杂度。
忘了的社友，可以看看第一章
计算时间复杂度最重要的，就是以最坏的情况来计算，why?
在数据量级无法确定的前提下，我们只能以最坏的情况来计算。就跟我们做任何事之前，都需要先做好最坏的情况一样，只有把坏的情况都考虑到了，我们成功的几率又大了不少。不然，想法都是太理想，但是现实是残酷的。
以最坏的情况进行推导。
71,66 ,60 ,49 ,24 ,11, 3
第一轮n-1
第二轮n-2
……….
n-1轮：1
所以他的次数为(n-1)+(n-2)+….+1
实际上就是一个等差数列求和
根据社长之前说过的， 只要高阶项，不要低阶项，也不要高阶项的系数
那么插入排序的时间复杂度为 O(n²)，空间复杂度 O(1),固定时间的操作，我们就认为他是常数操作。
原创不易，喜欢的朋友给我点个赞支持一下。
github算法篇源码 https://github.com/ITfqyd/datastuct