一.插入排序
插入排序的原理
插入排序的核心思路是将数据分为有序区和无序区，初始有序区只有第一个元素，插入算法就是从未排序的元素中挑选一个元素，在已排序的区间找到合适的位置并将其插入并保证有序区一直有序。插入排序属于原地排序，是稳定的排序，平均时间复杂度为O(n^2)。
代码示例
public static void insertSort(int[] num){
if (num==null){
return;
}
for (int i = 0; i < num.length-1; i++) {
//变量在这里定义，是为了方便内层循环结束后，将temp值放到正确的位置，会用到j
int j = i;
//记录i+1的值，因为后续这个位置的值会变，所以必须记录下来
int temp = num[i+1];
for (;j>=0;j--){
//如果比当前元素的值要小就将当前元素的值后移一位
if (temp<num[j]){
//后移一位
num[j+1]=num[j];
}else{
//因为数组的左边是有序的，因此只要有一次不满足条件就可跳出循环
break;
}
}
//注意这里必须J++，因为上面的内层循环是递减的，
// 当不满足条件或者break跳出循环时，j的值总会因为上次循环递减而少1，
// 上次移动元素到后一位之后，最后被移动的元素会在数组中重复两次，因为原位置还是它
// 所以在这里需要将元素的值用之前记录的temp值覆盖，换而言之就是把数组中后续最小的值插入到当前位置
num[++j]=temp;
}
}
总结
插入排序的时间复杂度 就是判断比较次数有多少，而比较次数与 待排数组的初始顺序有关，当待排数组有序时，没有移动操作，此时复杂度为O(N)，当待排数组是逆序时，比较次数达到最大,对于下标 i 处的元素，需要比较 i-1 次。总的比较次数：1+2+...+N-1 ，故时间复杂度为O(N^2)
二.希尔排序
希尔排序原理
希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序的基本思想是：
把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。
随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。
希尔排序.jpg
代码示例
public static void shellSort(int[] num){
if (num==null){
return;
}
//定义gap为数组长度一般，其实还可以为gap=(length-1)/3
int gap = num.length/2;
while (gap>=1){
for (int i = gap; i < num.length; i++) {
//变量在这里定义，是为了方便内层循环结束后，将temp值放到正确的位置，会用到j
int j = i-gap;
//记录i的值，因为后续这个位置的值会变，所以必须记录下来
int temp = num[i];
for (;j>=0;j-=gap){
//如果比当前元素的值要小就将当前元素的值后移gap位
if (temp<num[j]){
//后移gap位
num[j+gap]=num[j];
}else{
//因为数组的左边gap序列是有序的，因此只要有一次不满足条件就可跳出循环
break;
}
}
//注意这里必须j+gap，因为上面的内层循环是递减的，
// 当不满足条件或者break跳出循环时，j的值总会因为上次循环递减而少gap，
// 上次移动元素到后gap位之后，最后被移动的元素会在数组中重复两次，因为原位置还是它
// 所以在这里需要将元素的值用之前记录的temp值覆盖，换而言之就是把数组中当前gap序列后续最小的值插入到当前位置
num[j+gap]=temp;
}
//缩小增量 还可以为gap=gap/3
gap = gap/2;
}
}
总结
时间复杂度情况如下：（n指待排序序列长度）
- 最好情况：序列是正序排列，在这种情况下，需要进行的比较操作需（n-1）次。后移赋值操作为0次。即O(n)
- 最坏情况：O(nlog2n)。
- 渐进时间复杂度（平均时间复杂度）：O(nlog2n)
希尔算法在最坏的情况下和平均情况下执行效率相差不是很多。希尔排序没有快速排序算法快，因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择。
由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。
（注：专家们提倡，几乎任何排序工作在开始时都可以用希尔排序，若在实际使用中证明它不够快，再改成快速排序这样更高级的排序算法。）
网友评论