图解数据结构与算法(三)——插入排序
排序思想：
插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动，最终到达有序化。
排序过程：
实现代码：
/*** @ClassName: InsertionSort* @Auther: Jerry* @Date: 2020/6/6 9:07* @Desctiption: 插入排序* @Version: 1.0*/public class InsertionSort {public static void sort(int[] arr){for (int i = 1; i < arr.length; i++) {for (int j = i; j > 0 && arr[j] < arr[j-1]; j--) {int temp = 0;temp = arr[j-1];arr[j-1] = arr[j];arr[j] = temp;}}// 打印数组print(arr);}/*** 打印数组* @param arr 数组*/public static void print(int[] arr){for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}}public static void main(String[] args) {int[] arr = {3, 5, 4, 2, 9, 8, 6, 7, 1};sort(arr);}}
算法分析：
时间复杂度：在插入排序中，当待排序数组是有序时，是最优的情况，只需当前数跟前一个数比较一下就可以了，这时一共需要比较N- 1次，时间复杂度为O(n)。
最坏的情况是待排序数组是逆序的，此时需要比较次数最多，总次数记为：1+2+3+…+N-1，所以，插入排序最坏情况下的时间复杂度为O(n^2)。
空间复杂度：插入排序的空间复杂度为常数阶O(1) 。
稳定性：如果待排序的序列中存在两个或两个以上具有相同关键词的数据，排序后这些数据的相对次序保持不变，即它们的位置保持不变，则该算法是稳定的；如果排序后，数据的相对次序发生了变化，则该算法是不稳定的。关键词相同的数据元素将保持原有位置不变，所以该算法是稳定的。