/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */
#content_views .toc,
/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */
#content_views.markdown_views > p:empty:has(+ .toc),
#content_views.markdown_views > .toc + p:empty,
/* 富文本旧版目录标记 */
#content_views.htmledit_views #main-toc,
#content_views.htmledit_views #hr-toc,
#content_views.htmledit_views p[id*=\”-toc\”] {
display: none !important;
}
/* 目录去掉后，紧跟的首个标题不再多出一块上边距 */
#content_views.markdown_views > .toc + h1,
#content_views.markdown_views > .toc + h2,
#content_views.markdown_views > .toc + h3,
#content_views.markdown_views > .toc + h4,
#content_views.markdown_views > .toc + p:empty + h1,
#content_views.markdown_views > .toc + p:empty + h2,
#content_views.markdown_views > .toc + p:empty + h3,
#content_views.markdown_views > .toc + p:empty + h4 {
margin-top: 0 !important;
}
本文主要是对直接插入排序进行说明，希尔排序图难理解一点，代码还是很容易的。
所以希尔排序的图花的稍微精致一点。
插入排序
1.直接插入排序
- 时间复杂度：O（N^2）
- 空间复杂度：O（1）
- 稳定性：稳定
直接插入排序的思路：把一组数据分为【已排序】和【未排序】两个区间，将未排序的第一个元素存放起来，使用这个元素与已排序的区间元素进行比较赋值。
也可以这样说：想必大家都玩过扑克牌，当我们抽一张牌的向我们手中已经排好序的牌中进行插入的过程就是插入排序。
接下来我们用下面这一组数据来对这个过程进行解释：（从小到大排序）
刚开始的时候我们将第一个元素看作是【已排序】的最后一个元素，而现在后面所有的元素都是【未排序】区间的。我们拿【未排序】的第一个元素和【已排序】的最后一个元素进行比较。
我们拿出【未排序】的第一个元素放在tmp中。
下面这个图更能形象的表示，我的 i 位置的值放在了tmp中，实际情况是上面这个图。这个图就是方便理解
此时是3 小于 tmp 所以有:
if(array[j] < tmp){
array[j+1] = tmp;
}
接下来 i 继续向后走， j = i -1；
此时 j 的值大于tmp的值有
if(array[j] > tmp){
array[j + 1] = array[j];
}
接下来在执行上面第一个代码后的结果就是：
重复上面的步骤，完整的代码：
//1.Direct insertion sort
public static void insertSort(int[] array){
for(int i = 1; i < array.length;i++){
int tmp = array[i];
int j = i – 1;
for(; j >= 0; j–){
if(array[j] > tmp){
array[j+1] = array[j];
}else{
array[j+1] = tmp;
break;
}
}
array[j + 1] = tmp;//如果前面的元素都比tmp大，就需要执行这个代码
}
}
2.希尔排序（缩小增量排序）
- 时间复杂度：至今没有一个公认的值
- 空间复杂度：O（1）
- 稳定性：不稳定
希尔排序的基本思路：先选定一个整数，把待排序的数据分成多个组，对每一个组内进行排序。接着继续分组，比上一次的组少，在排序。直到最后分成1组，排序。
在排序的时候依旧使用的是插入排序
通过观察我们看到，使i = gap，而 j = i – gap；
所以我们就能写出完整的代码：
public static void shellSort(int array[]){
int gap = array.length;
while(gap > 1){
gap /= 2;
shell(array,gap);
}
}
private static void shell(int[] array, int gap) {
for(int i = gap; i < array.length; i++){
int tmp = array[i];
int j = i -gap;
for(;j >= 0;j-=gap){
if(array[j] > tmp){
array[j+gap]=array[j];
}else {
array[j + gap] = tmp;
break;
}
}
array[j+gap] = tmp;
}
}
希尔排序的代码和直接插入排序的主代码几乎一样，细心的可以看出只是把直接插入排序的代码的1换成了gap了。
