1.什么是插入排序
将一个记录插入到已经排好序的有序表中, 从而得到一个新的,记录数增1的有序表
2.实现思路:
1.从数组的第二个数据开始往前比较,即一开始用第二个数和他前面的一个比较,如果 符合条件(比前面的大或者小,自定义),则让他们交换位置。
2.然后再用第三个数和第二个比较,符合则交换,但是此处还得继续往前比较,比如有 5个数8,15,20,45, 17,17比45小,需要交换,但是17也比20小,也要交换,当不需 要和15交换以后,说明也不需要和15前面的数据比较了,肯定不需要交换,因为前 面的数据都是有序的。
3.重复步骤二,一直到数据全都排完。
3.动图演示:
插入排序.gif4.代码演示:
public static void sort(int[] arr){
for (int i = 1; i < arr.length; i++) {
int j = i;
while (j > 0){
if (arr[j] < arr[j-1]){
int temp ;
temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
//System.out.println(Arrays.toString(arr));
j--;
}else {
break;
}
}
}
//System.out.println(Arrays.toString(arr));
}
5.时间复杂度
在插入排序中,当待排序数组是有序时,是最优的情况,只需当前数跟前一个数比较一下就可以了,这时一共需要比较N- 1次,时间复杂度为O(N)
最坏的情况是待排序数组是逆序的,此时需要比较次数最多,总次数记为:1+2+3+…+N-1,所以,插入排序最坏情况下的时间复杂度为O(N2)
网友评论