基本思想
每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的子序列的合适位置，直到全部插入排序完为止。
image
算法实现
package cn.caojiantao.tutorials.sort;
/**
* @author caojiantao
*/
public class Insert implements ISort {
@Override
public void sort(int[] data) {
for (int i = 1; i < data.length; i++) {
int key = data[i], j = i - 1;
for (; j >= 0; j--) {
if (key < data[j]) data[j + 1] = data[j];
else break;
}
data[j + 1] = key;
}
}
}
复杂度
- 时间复杂度 O(n2)
- 空间复杂度 O(1)
网友评论