文章链接：日撸 Java 三百行（总述）_minfanphd的博客-CSDN博客
day43 插入排序?
43.1插入排序
插入排序基本思想：把一个待排序的数据插入到已经排序好的序列中。
day44 希尔排序
44.1 基本思路
他的基本思想是：将待排序的序列分为若干子序列，分别对每个子序列进行插入排序，在整个序列基本有序时，又进行一次整体的排序。最后一次排序一定是步长d=1.取步长d=1进行排序就和插入排序一样了，但是待排序得数是基本有序的。（如下图模拟的希尔排序）
44.2 插入排序和希尔排序对比
通过代码对比，插入排序：数据插入已经排好的序列，需要找到合适的插入位置，并移动数据，最后再插入数据。而希尔排序代码实现和插入排序实现很相似，插入排序只需要进行一次排序就好，而希尔排序要进行多次插入排序，而每一次排序有多个分组需要分别进行插入排序。
在希尔排序中，有四次循环，最外的循环是循环要进行几趟排序，第二个循环是在这一趟排序中，有多少组子序列需要排序，在里面的双层循环就和插入排序一样了，找到合适的位置移动数据，再插入数据。在排序过程中，由于变量太多，所以数组位置的赋值很容易乱，需要理清思路，我在这个过程中就出错了。
插入排序代码：
/**
* Insertion sort. data[0] does not store a valid data.
* data[0].key should be smaller than any valid key.
*/
public void insertionSort() {
DataNode tempNode;
int j = 0;
for (int i = 2; i < length; i++) {
tempNode = data[i];
//find and remove
for (j = i-1; data[j].key > tempNode.key; j--) {
data[j+1] = data[j];
}
//insert
data[j+1] = tempNode;
System.out.println("Round" + (i - 1));
System.out.println(this);
}
}希尔排序：
public void shellSort() {
DataNode tempNode;
int[] tempJumpArray = { 5, 3, 1};
int tempJump;
int p;
//以步长tempJumpArray[i] 划分若干个子序列
for (int i = 0; i < tempJumpArray.length; i++) {
tempJump = tempJumpArray[i];
//对每一个子序列进行插入排序
for (int j = 0; j < tempJump; j++) {
//排序和插入排序一样 只是步长不为1了
for (int k = j + tempJump; k < length; k += tempJump) {
tempNode = data[k];
for (p = k - tempJump; p >= 0; p -= tempJump) {
if (data[p].key > tempNode.key) {
data[p + tempJump] = data[p];
}else {
break;
}
}
//insert
data[p+tempJump] = tempNode;
}
}
System.out.println("Round " + i);
System.out.println(this);
}
}运行结果：
-------shellSortTest-------
I am a data array with 10 items.
(5, if) (3, then) (6, else) (10, switch) (7, case) (1, for) (9, while) (12, throw) (8, until) (4, do)
Round 0
I am a data array with 10 items.
(1, for) (3, then) (6, else) (8, until) (4, do) (5, if) (9, while) (12, throw) (10, switch) (7, case)
Round 1
I am a data array with 10 items.
(1, for) (3, then) (5, if) (7, case) (4, do) (6, else) (8, until) (12, throw) (10, switch) (9, while)
Round 2
I am a data array with 10 items.
(1, for) (3, then) (4, do) (5, if) (6, else) (7, case) (8, until) (9, while) (10, switch) (12, throw)
Result
I am a data array with 10 items.
(1, for) (3, then) (4, do) (5, if) (6, else) (7, case) (8, until) (9, while) (10, switch) (12, throw)
?总结：
今天学习了插入排序和希尔排序，明明希尔排序的循环都变多了，为啥它的平均时间复杂度还要比插入排序时间复杂度好呢，我觉得是希尔排序主要是它每次就是再一小范围内移动插入数据，再最后一次整体的进行插入排序时数列基本有序，但如果数据量大了，感觉希尔排序好像也没有很大的优势。另外，我认为学习希尔排序要结合插入排序学习，可能理解更容易。