文章目录
前言
介绍
动图演示
特点
基本思想
实现
算法描述
代码实现
前言
插入排序（Insertion sort）是一种简单直观且稳定的排序算法。
介绍
插入排序类似于打扑克牌，从第二张牌开始插入，小的插到大的前面，然后使其有序。再拿第三张牌来，找到合适的位置继续插入，使这三张有序。在第四张直至全部插入有序。
动图演示
特点
时间复杂度
最好情况：O(n)
平均情况：O(n2)
最坏情况：O(n2)
空间复杂度：O(1)
稳定性：稳定
基本思想
将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
实现
假设存在这样一个数组a[5]，数组中存在有5个10以下的数：
a[5] = [5,3,4,7,2];
将数组中第一个数看做是一个有序序列，即a[1] = [5]，再把数组剩下的数看做一个无序序列，即a[4] = [3,4,7,2]。
从头到尾依次扫描无序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面）
即：
a[1]=[5] -> a[2]=[5,3] -> a[2]=[3,5] a[2]=[3,5] -> a[3]=[3,5,4] -> a[3]=[3,4,5] a[3]=[3,4,5] -> a[4]=[3,4,5,7] a[4]=[3,4,5,7] -> a[5]=[3,4,5,7,2] -> a[5]=[2,3,4,5,7]
至此，插入排序完毕
算法描述
1.从第一个元素开始，该元素可以认为已经被排序
2.取出下一个元素，在已经排序的元素序列中从后向前扫描
3.如果该元素（已排序）大于新元素，将该元素移到下一位置
4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5.将新元素插入到下一位置中
6.重复步骤2~5
代码实现
public class InsertSort implements IArraySort { @Override public int[] sort(int[] sourceArray) throws Exception { // 对 arr 进行拷贝，不改变参数内容 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length); // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的 for (int i = 1; i < arr.length; i++) { // 记录要插入的数据 int tmp = arr[i]; // 从已经排序的序列最右边的开始比较，找到比其小的数 int j = i; while (j > 0 && tmp < arr[j - 1]) { arr[j] = arr[j - 1]; j--; } // 存在比其小的数，插入 if (j != i) { arr[j] = tmp; } } return arr; } } /** * 插入排序 * 第一个数不用管 * 比大小：一个数与所有他前面的数比大小，找到比他小的就停止 * 比他大的就往后移一个位置，比他小的，就插入在这个小的后面 */ public class Demo8 { public static void main(String[] args) { int[] a=new int[10]; //用随机数给数组元素赋值 for(int i=0;i<a.length;i++){ a[i]=(int)(Math.random()*100); } System.out.println(Arrays.toString(a)); int tmp; int j; for(int i=1;i<a.length;i++){ tmp=a[i]; for(j=i-1;j>=0;j--){ if(tmp<a[j]){ a[j+1]=a[j]; }else{ //a[j+1]=tmp; 如果写在这里会出现首位无法赋值的情况 //因为会有满足全部数据都大于tmp的值，就进不了这个else //因此要保证退出循环的时候再赋值 break;//找到比他小的要跳出循环 } } a[j+1]=tmp; } System.out.println(Arrays.toString(a)); } }
