插入排序demon
插入排序demon
public class InsertSortDemon {
//从前往后找
public static void sort(List 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 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 = https://www.it610.com/article/numbers.remove(i);
numbers.add(j+1,value);
}
}
}public static void main(String[] args) {
List nums = Lists.newArrayList(1,2,4,6,8,3,5,9,7);
InsertSortDemon.sort(nums);
System.out.println(nums);
}
}
运行结果
【插入排序demon】[1, 2, 3, 4, 5, 6, 7, 8, 9]可以看出 插入排序是
原地排序
不需要二外的存储空间，空间复杂度是o(1)
是稳定的排序算法
最好时间复杂度 o(n)
最坏时间复杂度 O(n^2)
平均时间复杂度 O(n^2)
推荐阅读
- 一个选择排序算法
- 排序（归并排序）
- 【图解】9张图彻底搞懂堆排序
- vue|vue 上移 下移 删除 排序
- 必须掌握的八种基本排序算法
- 【排序】插入排序算法
- 排序之冒泡和选择
- 2019-03-02|2019-03-02 排序
- Java数据结构与算法（十）排序算法01
- 不为人知的排序和筛选用法