直接插入排序StraightInsertSort
最后更新于：2022-04-01 09:49:14
1、算法思想
将一个记录插入到已排序好的有序表中，从而得到一个新的记录数增1的有序表。
即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。
要点：设立哨兵，作为临时存储和判断数组边界之用。
2、代码实现
~~~
package sort;
public class StraightInsertSort {
public static void main(String[] args) {
int[] source = {99, 53, 27, 36, 15, 69, 42, 66};
printArr(source);
StraightInsertSort(source);
printArr(source);
}
/**
* 将一个记录插入到已排序好的有序表中，从而得到一个新的记录数增1的有序表。 即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。 要点：设立哨兵，作为临时存储和判断数组边界之用。
*/
private static void StraightInsertSort(int[] source) {
if (source.length <= 1 || source == null) {
return;
}
int j;
for (int i = 1; i < source.length; i++) { // 从第二个数开始，依次直接插入
j = i;// 亦可只用一个变量i，但会增加比较次数
while (j > 0 && source[j] < source[j - 1]) {// 位置不合适则交换
source[j] = source[j - 1] + (source[j - 1] = source[j]) * 0;
j--;
}
printArr(source);
}
}
private static void printArr(int[] source) {
for (int i : source) {
System.out.print(i + " ");
}
System.out.println();
}
}
~~~
3、算法分析
### 算法稳定性
如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。
如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况如下。
**最好情况**：序列已经是升序排列了，在这种情况下，需要进行的比较操作需(n-1)次即可。
**最坏情况**：序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次（计算式为1+2+……+ n-1）。
直接插入排序属于稳定的排序，**最坏时间复杂度**为**O(n^2)**，**最好时间复杂度**为**O(n)**，**空间复杂度**为**O(1)**。
插入排序的赋值操作是比较操作的次数加上(n-1)次。
因此，插入排序**不适合对于数据量比较大**的排序应用。
源码地址：[https://github.com/zxiaofan/Algorithm/blob/master/src/sort/StraightInsertSort.java](https://github.com/zxiaofan/Algorithm/blob/master/src/sort/StraightInsertSort.java)