插入排序之 直接插入排序 法

直接插入排序法：

基本思想:

将一个记录插入到已排序好的有序数组中，从而得到一个新数组，记录数增1的有序数组。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。

要点：设立标志，作为临时存储和判断数组边界之用。

说明： 1.准备一个数组 {31,25,12,64,20} 2.原理:从第二个数开始，往前面插入(前面的子数组是有序数组) 3.用循环，即可简单完成任务

(31),25,12,64,20 原始数据

(25,31),12,64,20 第一次插入 (12,25,31),64,20 第二次插入 (12,25,31,64),20 第三次插入 (12,20,25,31,64) 第四次插入

---

详细讲解排序的过程：

31 25 12 64 20 原始数据

第一轮循环: 标志位为num[1]; 设置temp=25 首先判断nums[0]是不是比temp大，如果成立，前面的数往后挪一位，变为： 31 31 12 64 20 第一次比较 然后把 nums[0] = temp 结果如下： 25 31 12 64 20

第二轮循环: 标志位为num[2]; 设置temp=12 1.先判断nums[1]是不是比temp大，如果成立，前面的数往后挪一位，变为： 25 31 31 64 20 第一次比较 2.判断nums[0]是不是比temp大，如果成立，前面的数往后挪一位，变为： 25 25 31 64 20 第二次比较 3.找到temp应该在的地方 nums[0] = temp 结果如下： 12 25 31 64 20

第三轮循环 标志位为num[3]; 设置temp=64 首先判断nums[2]是不是比temp大，如果不成立，则直接跳出，不许在比较了，结果为： 12 25 31 64 20

第四轮循环 标志位为num[4]; 设置temp=20

先判断nums[3]是不是比temp大，如果成立，前面的数往后挪一位，变为： 12 25 31 64 64 第一次比较判断nums[2]是不是比temp大，如果成立，前面的数往后挪一位，变为： 12 25 31 31 64 第二次比较判断nums[1]是不是比temp大，如果成立，前面的数往后挪一位，变为： 12 25 25 31 64 第三次比较找到temp应该在的地方 nums[1] = temp 结果如下： 12 20 25 31 64

代码如下(java为例)：（写法不唯一）

public class test { public static void main(String[] args) { int[] nums = {12,20,25,31,64}; for (int i=1;i<nums.length;i++) { int temp=nums[i]; //设置标志位（哨兵） int j = 0; //定义下标 for (j = i-1;j>=0;j--) { //从标志位之前的数往前遍历 if (nums[j]>nums[j+1]) { //依次判断标志位的数值大小，应该插到什么位置 nums[j+1] = nums[j]; //如果标志位的数要插到前面，需要把相应的数往后挪一位 }else { break; //如果标志位的数比前面的数大，就不用继续向前比了，直接跳出 } } if (nums[j+1]!=temp) { //判断要插入的位置数是不是和temp相等 nums[j+1] = temp; //就把标志位的数（temp）插入到相应的位置 } } for(int i:nums) { //遍历 System.out.println(i); } } }

直接插入排序思路简单，但代码逻辑较难； 算法的优点是简单，缺点是慢。 排序的结果稳定