前言
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
8）性能分析
- 平均值：约n2/4，直接插入排序的时间复杂度为O(n2)
- 需要一个辅助单元r[0]，空间复杂度为O(1)
- 直接插入排序是一种稳定的排序算法。
