本专栏和大家分享关于排序的算法,其中有插入排（直接插入排序和希尔排序）、选择排序（直接选择排序和堆排）、交换排序（冒泡排序和快速排序）、归并排序以及其他非基于比较的排序
本文与大家分享插入排序
目录
1.直接插入排序
直接插入排序的步骤如下:
假设我们的数组是:[5,3,10,7,4],我们用i来遍历数组,每次遍历用j作为i的前一个数,我们需要保证遍历到i的时候.0-j之间的数据都是有序的.同时我们定义一个tmp = arr[i],作为每次循环的基准,将i之前所有大于tmp的数都放到后面
我先看整体的效果
我们一步一步来演示:
i是从第2个元素开始遍历的,每次都把i之前所有大于3的数都放到后面,那么我们的j就要往前遍历去判断,第一个arr[j] = 5 > 3,我们就让arr[j+1] = arr[j],同时j--;
当j < 0时候,说明i前面的所有数都遍历完了,那么就让arr[j+1] = tmp
这样就保证i之前所有的数都有序,i++继续遍历
第一个遍历的arr[j] < tmp,由于之前的数据已经是有序的了,那么在5之前不可能找到一个数比10大,那么直接跳出本次循环,让arr[j+1] = tmp,即让tmp回到应到的位置.i++继续遍历
由于arr[j] > tmp,那么这10就要往后走,即arr[j + 1] = arr[j],同时j--继续遍历;
同样,5 < tmp,那么直接跳出本次循环,同时让arr[j+1] = tmp;
i++继续遍历
由于 10 > 4,那么10要往后走,就arr[j+1] = arr[j],同时j--;
同样,7 > 4,7也往后走,j--;
5也是一样情况,直到j遍历到3,就让arr[j+1] = tmp
接着i++后,数组就遍历完了
可以发现此时的数组就是有序的了
具体用代码演示:
public void insertSort(int[] array){
if(array.length == 0){
return;
}
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{
break;
}
}
array[j + 1] = tmp;
}
}时空复杂度分析
直接插入排序的时间复杂度为O(n^2)。在最坏情况下，即数组完全逆序时，需要进行n*(n-1)/2次比较和交换操作。在最好情况下，即数组已经有序时，时间复杂度可以降至O(n).
空间复杂度是O(1)
稳定性
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的
直接插入排序的稳定性取决于在判断大小的时候有没有 加 "=" ,如果有的话就是不稳定的,没有的话就是稳定的
同时我们也可以得出这样的结论:一个本身是稳定的排序是可以变成不稳定的，但是一个不稳定的排序是不可能变成有序的排序的
特点:数据越有序，插入排序就越快
2.希尔排序
希尔排序法又称缩小增量法。实际上是对直接插入排序的优化.假设我们现在有10000个数据,直接使用直接插入排序,时间复杂度将达到10000*10000,也就是一个亿;但是如果我们将这10000个数据去分组,分成100组,每一组分别去进行直接插入排序,每一组时间复杂度就是10000,合起来就是1000000(当然与分组的方法是有关的)
希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成多个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取重复上述分组和排序的工作。 当到达=1时，所有记录在统一组内排好序。
我们的重点在于分组
假设现在有一组数据:[9,1,2,5,7,4,8,6,3,5]
如果让我们去分组,我们可能会这么分:
那么每组进行排序后,就会得到:
但是好像对我们没什么帮助
发明希尔排序的科学家是这样进行分组的:跳跃式的分组
把相同颜色的分成同一组,那么有什么好处呢?? 我们试着每一组排序:
与前面的相比,我们会发现,通过这样跳跃式的分组,尽可能将大的元素放到后面,小的元素放到前面,即数组越来越有序了,上面我们说到,数组越有序,直接插入排序就越快
那么我们再将组数缩小为2:
每组再分别进行直接插入排序
最后一定要将整个数组看成一组进行直接插入排序
就能得到
从上面我们知道,分组是为了提升效率,缩小增量都是预排序的过程,每次排序都让数组趋近于有序,直到最后组数为1的时候,整体进行插入排序
当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
那么具体代码该怎么编写呢??
我们在直接插入排序的时候说过,i是从第二个元素开始的,因此当我们的i 一开始是等于gap的,对于j,就要每次 -= gap,以达到针对某一组进行插入排序的效果
但是i也是+=gap吗??实际上不必,我们会发现,当我们的i++后,j-=gap,此时排序的是绿色这一组,当i++后,j同同样-=gap,此时又针对红色这一组进行排序,因此我们只需要将i++,就能来回对不同的组进行直接插入排序
public class ShellSort {
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 j = i - gap;
int tmp = array[i];
while(j >= 0){
if(array[j] > tmp){
array[j+gap] = array[j];
j -= gap;
}else{
break;
}
}
array[j+gap] = tmp;
}
}
}时空复杂度分析
希尔排序的时间复杂度不好计算，因为gap的取值方法很多，可能是gap = gap / 2或者 gap = gap / 3 + 1导致很难去计算，因此在不同书中给出的希尔排序的时间复杂度都不固定
我们认定在O(N^1.25) ~ O(N^1.5)左右
空间复杂度是O(1)
稳定性:
不稳定的排序