前言
1.插入排序，一般也被称为直接插入排序。对于少量元素的排序是一个好的排序方法。插入排序是一种最简单的排序方法。
2.它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进
行待插入位置查找，并进行移动 。
一、概述
插入排序：每次将一个待排序的记录，按其关键字的大小插入到前面已排序好的记录序列中的适当位置，直到全部记录插入完成为止。
确定插入位置的查找方法不同导致不同的算法描述：
直接插入排序：基于顺序查找
希尔排序：基于逐趟缩小增量
二、希尔排序
1、希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。
2、希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。
1）概述
希尔排序：Shell Sort
希尔排序，又称为缩小增量排序。
基本思路：
1.先选取一个小于n的整数di（称为增量），并将记录序列分成若干子表
2.从下标为0的记录开始，间隔为di的记录组成一个子表，在各个子表内进行直接插入排序。
3.一趟完成后，逐步减小增量di，并重复上面的步骤，直到di=1，使得间隔为1的记录有序，也就是整个序列都达到有序。
2）示意图
3）例题分析
序列：52、39、67、95、70、8、25、52、56、5
序列：99、5、69、33、56、13、22、55、77、48、12、88、2、69、99
4）算法实现
代码
//【算法3】希尔排序算法 public void shellSort(int[] d) { //d[]为增量数组 RecordNode temp; int i, j; System.out.println("希尔排序"); //控制增量，增量减半，若干趟扫描 for (int k = 0; k < d.length; k++) { //一趟中若干子表，每个记录在自己所属子表内进行直接插入排序 int dk = d[k]; for (i = dk; i < this.curlen; i++) { temp = r[i]; for (j = i - dk; j >= 0 && temp.key.compareTo(r[j].key) < 0; j -= dk) { r[j + dk] = r[j]; } r[j + dk] = temp; } System.out.print("增量dk=" + dk + " "); display(); } }
测试
public class TestSeqList3_shell { public static void main(String[] args) throws Exception { int[] arr = {52,39,67,95,70,8,25,52,56,5}; int[] d = {5,3,1}; SeqList seqList = new SeqList(arr.length); for (int i = 0; i < arr.length; i++) { seqList.insert(i, new RecordNode(arr[i])); } // 希尔排序算法 seqList.shellSort(d); } } //希尔排序 //增量dk=5 8 25 52 56 5 52 39 67 95 70 //增量dk=3 8 5 52 39 25 52 56 67 95 70 //增量dk=1 5 8 25 39 52 52 56 67 70 95
5）性能分析
- 希尔排序的时间复杂度：不确定，但在插入排序中，希尔排序的效能最高，最好情况可达O(nlog2n)
- 只需要一个记录的辅助空间，O(1)
- 是==不稳定==的排序方式，也就是说 52和 52 顺序不确定。
