插入排序类似于我怕们平时玩的扑克牌,每次从牌堆摸一张牌放入手中,依次和手上的牌比大小,插入合适的位置;时间复杂度O(n^2)。
描述:
1、每次从数组中取一个目标元素,向左扫描;
2、扫到大于它的元素,将大的元素右移一位,扫到小于等于它的元素停止,将目标元素插在当前位置;
3、重复以上过程;
动画:
![](https://img.haomeiwen.com/i3983707/51bc2753af6700c1.gif)
代码:
private void insertSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int index = i;
int temp = array[index];
while (index >= 1 && temp < array[index - 1]) {
array[index] = array[index - 1];
index--;
}
if (index != i) {
array[index] = temp;
}
}
}
网友评论