插入排序

介绍

这是一个对少量元素进行排序的有效算法。它将被插入元素与已经排好序的元素从右往左以此对比，遇到比它大的元素则将该元素向后移动一位，知道找到合适的位置插入

java代码

void insert_sort(int[] array){ if(array == null || array.length == 0 || array.length == 1) return; int val,int index; for(int i = 1; i < array.length; i++){ val = array[i]; index = i; while(index >= 1 && val < array[index - 1]){ array[index] = array[index - 1] index--; } array[index] = val; } }

算法性能

时间复杂度

当数组已经排好序时，复杂度O(n) 最坏情况复杂度O(n^2)

空间复杂度

由于插入排序是in-place排序，空间复杂度为O(1)

稳定性

如果碰见一个和被插入元素相等的，那么被插入元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的