插入排序
文章目录
插入排序
一.什么是插入排序?
每步将一个待排序的纪录,按其数值的大小插入前面已经排序的文件中适当位置上,直到全部插入完为止,其适用于少量数据的排序
二.java实现
public void insertion_sort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int i,j,temp;
for (i=1; i<arr.length; i++) {
temp = arr[i];
for (j = i-1; j>=0 && arr[j]>temp; j--) {
arr[j+1] = arr[j];
}
arr[j+1] = temp;
}
}
三.算法复杂度
- 最好复杂度:序列为正序时复杂度为O(n)
- 最好复杂度:序列为反序时复杂度为O(n^2)
- 平均复杂度:O(n^2)
四.算法稳定性
- 插入排序是稳定的
插入排序是在有序的序列上,一次插入一个元素。当然,刚开始这个有序的小序列只有1个元素,就是第一个元素。比较是从有序序列的末尾开始,也就是想要插入的元素和已经有序的最大者开始比起,如果比它大则直接插入在其后面,否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论