前言

1.插入排序，一般也被称为直接插入排序。对于少量元素的排序是一个好的排序方法。插入排序是一种最简单的排序方法。

2.它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。

一、概述

插入排序：每次将一个待排序的记录，按其关键字的大小插入到前面已排序好的记录序列中的适当位置，直到全部记录插入完成为止。

确定插入位置的查找方法不同导致不同的算法描述：

直接插入排序：基于顺序查找
希尔排序：基于逐趟缩小增量

二、直接插入排序

直接插入排序是一种最简单的排序方法，其基本操作是将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增1的有序表。

1）概述：

直接插入排序：Straight Insertion Sort
基本条件：待排序记录依次存放在数据r[0..n-1]中
思想：

1.先将第0个记录，组成一个有序子表

2.然后依次将后面的记录插入到这个子表中，且一直保持它的有序性。

2）步骤

在r[0..i-1]中查找r[i]的插入位置，r[0..j].key ≤r[i].key < r[j+1..i-1].key

将r[j+1 .. i-1] 中的所有记录均后移一个位置

将r[i]插入到r[j+1]的位置上

3）示意图

4）分析：不带监视哨的算法

查找r[i]的插入位置，将r[i]暂存在临时变量temp中，将temp与r[j] （j=i-1,i-2, ..., 0）依次进行比较
若temp.key < r[j].key，则将r[j]后移一个位置，直到temp.key ≥ r[j].key 为止
将temp插入到第j+1个位置上
令 i = 1, 2, 3, ..., n-1 ，重置上面3步。

5）算法实现：不带监视哨

算法

//【算法1】 不带监视哨的直接插入排序算法
public void insertSort() {RecordNode temp;int i, j;for (i = 1; i < this.curlen; i++) {		// n-1趟扫描temp = r[i];  						// 将待插入的第i条记录暂存在temp中for (j = i - 1; j >= 0 && temp.key.compareTo(r[j].key) < 0; j--) { r[j + 1] = r[j];				// 将前面比r[i]大的记录向后移动}r[j + 1] = temp;          			// r[i]插入到第j+1个位置//System.out.print("第" + i + "趟: ");//display();}
}

测试

public class TestSeqList1_insert {public static void main(String[] args) throws Exception {int[] arr = {52,39,67,95,79,8,25,52};SeqList seqList = new SeqList(arr.length);for (int i = 0; i < arr.length; i++) {seqList.insert(i, new RecordNode(arr[i]));}// 不带监视哨的直接插入排序seqList.insertSort();}
}
//
//第1趟:  39 52 67 95 79  8 25 52
//第2趟:  39 52 67 95 79  8 25 52
//第3趟:  39 52 67 95 79  8 25 52
//第4趟:  39 52 67 79 95  8 25 52
//第5趟:   8 39 52 67 79 95 25 52
//第6趟:   8 25 39 52 67 79 95 52
//第7趟:   8 25 39 52 52 67 79 95

6）分析：带监视哨的算法

以上不带监视哨的算法中的【算法1】第6行的循环条件中的j≥0用来控制下标越界。为了提高算法效率，可对该算法改进如下：

首先将待排序的n条记录从下标为1的存储单元开始依次存放在数组r中，

在将顺序表的第0个存储单元设置为一个监视哨，即在查找之前把r[i]赋给r[0]，

这样每循环一次，只需要进行记录的比较，不需要比较下标是否越界

7）算法：带监视哨

算法

//【算法2】带监视哨的直接插入排序算法
public void insertSortWithGuard() {int i, j;
//        System.out.println("带监视哨的直接插入排序");for (i = 1; i <this.curlen; i++) {      //n-1趟扫描r[0] = r[i]; //将待插入的第i条记录暂存在r[0]中，同时r[0]为监视哨for (j = i - 1; r[0].key.compareTo(r[j].key) < 0; j--) { //将前面较大元素向后移动r[j + 1] = r[j];}r[j + 1] = r[0];          // r[i]插入到第j+1个位置System.out.print("第" + i + "趟: ");display(9);}
}

测试

/*** @author 桐叔* @email liangtong@itcast.cn*/
public class TestSeqList2_insertGuard {public static void main(String[] args) throws Exception {int[] arr = {0,52,39,67,95,79,8,25,52};SeqList seqList = new SeqList(arr.length);for (int i = 0; i < arr.length; i++) {seqList.insert(i, new RecordNode(arr[i]));}// 带监视哨的直接插入排序seqList.insertSortWithGuard();}
}
//
//第1趟:  39 52 67 95 79 8 25 52
//第2趟:  39 52 67 95 79 8 25 52
//第3趟:  39 52 67 95 79 8 25 52
//第4趟:  39 52 67 79 95 8 25 52
//第5趟:  8 39 52 67 79 95 25 52
//第6趟:  8 25 39 52 67 79 95 52
//第7趟:  8 25 39 52 52 67 79 95