面试题必考系列:插入排序法

插入排序相比于之前的冒泡二分法排序难度更大一点,排序过程涉及到三个循环加两个判断,想完成该算法需要了解插入排序的三个循环的原理,我在草稿纸大概描述了其中的大致原理,思路可能不太好理解,先慢慢体会一下其中的排序的原理:

代码实现:

public class insertSortDemo {
	public static void main(String[] args) {
		int [] ints= {5,4,8,7,1,2,3,6};
		//循环地点从数组第二个元素开始,与前一位元素比较大小
		for(int i =1;i<ints.length;i++){
			//i元素<i-1元素进入j循环  i元素就是需要被调整的元素
			if(ints[i] < ints[i-1]){
				//从0索引位置到i之前遍历 寻找大于i的元素 找到即是i元素要插入的位置
				for(int j = 0;j<i;j++){
					//j元素大于i元素 j索引位置就是插入点
					if(ints[j]>ints[i]){
						//先将i位置的值提取出来
						int tempt =ints[i];
						//j索引插入点到i元素前一位所有元素向后移动一位(从后往前遍历)
						for(int k = i-1;k>=j;k--){
							ints[k+1]=ints[k];
						}
						//元素后移后腾出j位置让tempt插入
						ints[j] =tempt;
						//提高效率 插入完成后无需继续遍历 退出循环
						break;
					}
				}
			}
		}
		for(int i=0;i<ints.length;i++){
			System.out.print(ints[i]+" ");
		}
	}
}