插入排序demon
public class InsertSortDemon {
//从前往后找
public static void sort(List<Integer> numbers){
/**
* 将数组看为 有序的部分和无序的区间
* 将无序的区间插入到有序的区间
* 起始时候 有序区间是第一个数据
*/
for (int i = 1; i < numbers.size(); i++) {
for (int j = 0; j < i; j++) {
int tmp = numbers.get(i);
if(tmp < numbers.get(j)){
numbers.remove(i);
numbers.add(j,tmp);
break;
}
}
}
}
//从后往前找
public static void sort2(List<Integer> numbers){
/**
* 将数组看为 有序的部分和无序的区间
* 将无序的区间插入到有序的区间
* 起始时候 有序区间是第一个数据
*/
for (int i = 1; i < numbers.size(); i++) {
int j = i - 1;
int tmp = numbers.get(i);
for (; j >= 0; j--) {
if(tmp > numbers.get(j)){
break;
}
}
if(j + 1!= i){
Integer value = numbers.remove(i);
numbers.add(j+1,value);
}
}
}
public static void main(String[] args) {
List<Integer> nums = Lists.newArrayList(1,2,4,6,8,3,5,9,7);
InsertSortDemon.sort(nums);
System.out.println(nums);
}
}
运行结果
[1, 2, 3, 4, 5, 6, 7, 8, 9]
可以看出 插入排序是
原地排序
不需要二外的存储空间，空间复杂度是o(1)
是稳定的排序算法
最好时间复杂度 o(n)
最坏时间复杂度 O(n^2)
平均时间复杂度 O(n^2)
