算法:简单排序3-插入排序

简单排序3-插入排序

思路

• 1.每一次循环从第二位置开始，并把第二个位置空出来，把数放到临时的地方
• 2.依次和空白位置的左侧比较大小
• 3.如果比左侧小就继续向左比较大小，同时左侧的数量依次向空白处移动位置

InsertSort.java 具体实现

public class InsertSort {

	public static int array[] = { 5, 6, 3, 1, 3 };

	public static void main(String[] args) {
		for (int out = 1; out < array.length; out++) {	//1
			int in = out;	//2
			int temp = array[out];	//3
			
			while (in > 0 && array[in - 1] > temp) {	//4

				array[in] = array[in - 1];	//5

				--in;
			}
			array[in] = temp;	//6
		}

		for(int i=0;i<array.length;i++){
			System.out.print(" "+array[i]);
		}
	}

}

输出： 1 3 3 5 6

说明

• 1.从第二个位置开始循环
• 2.里层下标记录为out
• 3.把第二个位置挪出到临时区域，并变为空白位置
• 4.向左侧一直比较大小，直到没有可比较的，当有比抽离出来的位置大于的数时进行交换位置
• 5.依次向右移动到空白位置
• 6.把临时区的数据插入到符合位置

注意：逆序时的插入排序比冒泡还要慢，因为每一次都会产生比较和交换位置。

注:该内容为Java数据结构和算法读后学习感悟

其他相关文章

递归-归并排序

高级排序2-快速排序

划分排序

高级排序1-希尔排序

简单排序2-选择排序

简单排序1-冒泡排序

赏

谢谢你的激励

微信