直接插入排序算法(JAVA版)

时间复杂度:O(n*n)

直接插入排序:遍历第二个到最后一个,找到每一个值的最佳位置,插进去:)
1.a[i]和前一个值a[i-1]比较,如果小于前一个值
2.设此值为temp,把a[i-1]向后移一位a[i]=a[i-1]
3.检查前面的a[<=i-2]是否有比temp大的,如果比temp大,后移一位
4.直到一个比temp小的或者j=-1,此时把temp赋值到j+1即可

举例子:
原序列:8 4 5 3
第一次 4 8 5 3
第二次 5<8,所以temp = 5, 序列变成 4 8 8 3,然后和i-2=0前面的4比较大小,5>4,所以5应该在1的位置上,把temp赋值到1位置上,4 5 8 3
第三次 3<8,所以temp = 3, 序列变成 4 5 8 8,然后和i-2=2前面的5比较大小,3>5,序列变成 4 5 5 8,再比较3>4,序列变成 4 4 5 8,此时j=-1,那temp肯定在0位上,最终序列3 4 5 8

public class Paixu {
 
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] a = {8,4,5,3};
		int[] insertSorta = new Paixu().insertSort(a);
		pw(insertSorta);
	}
 
	/*
http://fatkun.com
直接插入排序:遍历第二个到最后一个,找到每一个值的最佳位置,插入进去
1.a[i]和前一个值a[i-1]比较,如果小于前一个值
2.设此值为temp,把a[i-1]向后移一位a[i]=a[i-1]
3.检查前面的a[<=i-2]是否有比temp大的,如果比temp大,后移一位
4.直到一个比temp小的或者j=-1,此时把temp赋值到j+1即可
 
初始序列:8 4 5 3
4 8 5 3
4 5 8 3
3 4 5 8
	 */
	int[] insertSort(int[] arr) {
		int temp;
		for (int i = 1; i < arr.length; i++) {
			pw(arr);
			if (arr[i] < arr[i - 1]) {//如果当前值小于前一个
				temp = arr[i]; //设定岗哨
				arr[i] = arr[i - 1]; //把前一个值移到后一位
 
				//继续和前面的进行比较,如果比temp大,则后移一位
				//这里j从前两个开始,因为前一个知道必定比temp大了,无需再比较
				int j = i - 2;
				while (j>=0 && temp < arr[j]){
					arr[j + 1] = arr[j];
					j--;
				}
				//上一个循环结束后,j在最后一个比temp小的位置或者-1,所以j+1,把当前值放在这里
				arr[j + 1] = temp;
			}
		}
		return arr;
	}
 
	//打印数组
	private static void pw(int[] arr){
		for (int i : arr)
		System.out.print(i+" ");
		System.out.println("");
	}
 
}

简化一些,去掉一些注释,代码基本一样

	int[] insertSort(int[] arr) {
		int temp;
		for (int i = 1; i < arr.length; i++) {
			pw(arr);
			if (arr[i] < arr[i - 1]) {
				temp = arr[i];
				//这里和前面不太一样,从i的前一个就开始比较,也就是判断前面所有元素(多判断了一次arr[i]和arr[i-1])
				int j = i - 1;
				while (j>=0 && temp < arr[j]){
					arr[j + 1] = arr[j];
					j--;
				}
				arr[j + 1] = temp;
			}
		}
		return arr;
	}



fatkun

14条评论

发表评论

电子邮件地址不会被公开。