不管何种排序方式，查找比较规则都是从右到左
一般情况下， 该算法比冒泡排序快一倍，比选择排序要快一些
对于有序或者基本有序的数据，插入排序非常快，可以达到O(N)
如果数据是逆序的，那么插入排序比冒泡排序还慢
实现
#
//插入排序--由大到小
public static void insertSort(int[] arr){
int j;
int key;
for (int i = 1; i < arr.length; i++) {
key=arr[i];//key就是我们每次新摸到的牌，现在需要找到插入的位置并空出位置
j=i-1;
while (j>=0 && arr[j]<key) {//将已排好序的所有比key小的元素右移一个位置，空出一个位置，方便key插入
arr[j+1]=arr[j];
j--;
}
arr[j+1]=key;//空出位置后，然后插入
}
}
时间复杂度：O(N的平方)，稳定算法
就上面三种算法比较的话，插入排序是最好的，适合小数据量。
以上三种称为简单排序算法
最优复杂度：当输入数组就是排好序的时候，复杂度为O(n)，而快速排序在这种情况下会产生O(n^2)的复杂度
最差复杂度：当输入数组为倒序时，复杂度为O(n^2)
插入排序比较适合用于“少量元素的数组”
4.希尔排序希尔排序
原理：是基于插入排序的改进算法，插入排序每次移动都是一个一个移动，当逆序时候，移动次数要很多，希尔排序改进了移
动步长，可以实现大跨度移动，减少移动时间。希尔排序也叫做缩小增量排序法
将整个无序数据分割成若干小的子序列分别进行插入排序
在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，
而各组的记录数目逐渐增多，但由于已经按di-1作为距离排序，使文件较接近于有序状态，所以新的一趟排序过程也较快。
在插入算法中，如果有一个最小的数在数组的最后面，用插入算法就会从最后一个位置移动到第一个，这样就会浪费很大，使
用这个改进的希尔排序可以实现数据元素的大跨度的移动。也就是这个算法的优越之处。
先取一个小于n的整数d1作为一个增量，把表的全部记录分成d1个组，所有距离为d1的倍数的记录放在同一个组中，在各组内
进行直接插入排序，然后，取第二个增量d2(<d1),重复上述的分组和排序，直至所取的dt=1,即所有记录放在同一组中进行直接
插入排序为止。
举例：要排序的数组是[3 5 4 12 45 3 -32 7 5 8 34 -4],长度为12，首先确定最大增量，增量的值选取对运行效率影响很大，这里
面有很多间隔划分算法。我们这里选择的增量为长度/2，这里=6，故开始分组 每隔6个元素一组，分组如下：第一组【3 -32】
第二组【5 7】第三组【4 5】第四组【12 8】第五组【45 34】 第六组【3 -4】，然后对每一组进行插入排序，从大到小，经过
第一次排序后，变为【3 7 5 12 45 3 -32 5 4 8 34 -4】，然后再次修改增量，这次增量要缩小，我们再次是上次增量/2=3；然后
开始第二次分组：第一组【3 12 -32 8】第二组【7 45 5 34】第三组【5 3 4 -4】，然后对每组使用插入排序，排序后合成，则
数组变为【12 45 5 8 34 4 3 7 3 -32 5 -4】，从这里可以看出，已经基本有序了。最后增量/2=1;表示不需要再分组了，对上述数
据进行一次插入排序即可。
实现
//希尔排序--由大到小
public static void shellSort(int[] arr) {
int size = arr.length;
//这层for是分组
for(int gap = size/2; gap>=1; gap /= 2) {
//这层for是对每组进行插入排序
for(int i=gap; i<size; i++) {
评论0