算法-基本排序算法-03 插入排序详解

1.要点

插入排序就向打牌，每一遍把后面的一张牌插入到前面合适的位置

2.动图演示

这里是[9,1,5,8,3,7,4,6,2,10]的例子

3.算法步骤

1.一遍的（红色）元素依次与前面的元素比较，如果比前面的元素小，就插入到前面的元素的后面 插入到前面的元素的后面的操作涉及到2步骤(1) 前面的元素（绿色）右移，（2）插入元素（红色）插入到指定位置. 2. 遍历插入操作，排序成功.

4.代码

java代码实现

public int[] insertionSort(int[] sourceArray) { int length = sourceArray.length; //复制一份新的数组防止改变之前的数据，可选 int[] copyArray = Arrays.copyOf(sourceArray, length); //第一个不用插入，我们从第二个开始 for (int i = 1; i < length; i++) { int temp = copyArray[i]; //temp小于前面的数字，前面的数字这个向后方移动一位，向temp方向. int j ; for ( j = i; j > 0 && temp < copyArray[j-1]; j--) { copyArray[j] = copyArray[j-1]; } //temp插入 copyArray[j] = temp; } return copyArray; }

5.优缺点

优点

如果这个数据本身就是“相对顺序的”就十分的快速 .

缺点 2. 时间复杂度 O(n2)