插入排序
插入排序是最简单的一种排序方式。这里就不去啰嗦绕口的概念了，通过图去解释什么是插入排序
假设一个数组内有如下5个元素，需要对其按照从小到大的顺序进行排列。
插入排序就是从未排序序列中，取出元素，在已排序序列中一次比较。插入到相应的位置。
在上面的五个数字中
-
我们假设有一个长度为一的有序系列为12。
-
而8、17、31、22为无序序列。
-
从无序序列中取出一个元素8，与有序序列中的12进行比较。比12小，则将其移动到12前面，反之放在后面
结果为：
public static void main(String[] args) {
Integer[] arr = {12, 8, 17, 31, 22};
// 第一个元素为有序，因此从i = 1开始
for (int i = 1; i < arr.length; i++) {
// 待插入元素 第一次循环arr[i] 就是8
Integer temp = arr[i];
int j;
for (j = i - 1; j >= 0; j--) {
// 数组中第二个元素与第一个元素比较，12>8
if (temp < arr[j])
/**
* 复制j位元素到j+1
* 循环一次是，结果为12、12、17、31、22
*/
arr[j + 1] = arr[j];
else
break;
}
/**
* j + 1 位为要插入的最小元素
* 循环一次结果为8、12、17、31、22
*/
arr[j + 1] = temp;
}
System.out.println(Arrays.toString(arr));
}
二分排序
在说二分排序之前不得不提到二分查找这个基本的算法。那什么是二分查找呢？
举个例子，大家应该都玩过猜数字的游戏，如果从1~100这里面猜一个数字。我只需要对你猜的数字回答 “大了”、“小了”。直至猜出结果。
如果漫无目的的去猜，运气不好可能会猜100次。那怎么样才能更少次数的猜出结果呢。
假设我们的目标数字是 66
对于N个元素的列表，我们要猜出其中一个数字最多只需要log 2 N次。如果列表中1024个数字，我们也只需要猜测10次就可以出来。2的十次方等于1024.
回到我们的二分插入，原理基本一样，从无序列表中取出一个元素，跟前面的有序列表的中间数进行比较，如果小了，再进行折半比较，直至找到合适的位置。
如图，6、9、12、18、20为有序列表，对15进行二分插入
-
取出有序列表的中间元素12。12< 15。
-
12、18、20取出中间元素，18。18 > 15
-
在12、18中进行比较，12<15<18
public static void main(String[] args) {
int i, j, right, left, mid, temp;
Integer[] arr = {12, 8, 17, 31, 22, 44, 1, 99, 76};
// 依旧把第一个元素当成有序的，因此从i=1开始
for (i = 1; i < arr.length; i++) {
//如果后一个元素比前一个元素大，则continue，开始下一次循环
if (arr[i] > arr[i - 1]) {
continue;
}
temp = arr[i];
//最左边为二分插入的起始位置
left = 0;
//左右定义有序列表的长度
right = i-1;
while (left <= right) {
//mid为中间元素的下标
mid = (left + right) / 2;
// 中间元素和要插入的元素进行比较
if (arr[mid] < temp)
//如果中间元素小，则起始位置为mid + 1
left = mid + 1;
else
//同left
right = mid - 1;
}
// 移动元素到相应的位置
for (j = i - 1; j >= left; j--) {
arr[j + 1] = arr[j];
}
arr[left] = temp;
}
System.out.println(Arrays.toString(arr));
}
希尔排序
希尔排序又成为缩小增量排序。假设有一个长度为N的数组，他的增量设为X(X<N)，将数组拆分为多个子序列，在每个子序列中进行直接插入排序。然后减少增量的值，重复以上操作，直至X=1(即一个子序列中只有一个元素)。这样理解可能比较混乱，看图说话吧。
如图，一个长度为8的无序数组
增量通常取长度的一般，所以增量为 8/2 = 4。意味着此时被拆分为4个子序列。
[18 , 10]， [22，1]，[3，19]，[51，55]
我用四种不同的颜色进行标识
然后子序列中的元素进行插入排序，即同一颜色的两个数进行排序，结果为
然后缩小增量，此时增量为4/2 = 2。被分为两个子序列
[10，3，18，19] ，[1，5 1，22，55]
再次对子序列进行排序，得到的结果如下
重复上述操作，再次缩小增量直至为1，经过增量递减的过程，其实就是元素排序的过程，当增量为1时，大部分元素其实已经排好顺序了，我们只需要对其进行微调即可。
代码实现如下
public static void main(String[] args) { Integer[] arr = {18, 22, 3, 51, 10, 1, 19, 55}; // 初始增量通常为总长度的一半 int mid = arr.length / 2; int i; while (mid > 0) { for (i = mid; i < arr.length; i++) { // 起始下标 int begin = i - mid; int tmp = arr[i]; // 起始下标元素大 则调整位置， while (begin >= 0 && arr[begin] > arr[i]) { arr[begin + mid] = arr[begin]; begin -= mid; } //并且调换位置 arr[begin + mid] = tmp; } // 每次结束，增量缩小一半。也可以自定义 mid = mid / 2; System.out.println(Arrays.toString(arr)); } }
总结
插入排序适用于少量数据的排序，其时间复杂度为O(n^2)。
二分排序则是利用了数组能够快速定位的特点，时间复杂度也是O(n^2)，适用于较大数据排序
希尔排序的实质是分组再进行直接插入，开始时增量较大时，插入排序的数量少，所以前期会很快。当增量变小时，数据也基本有序了。所以希尔排序的时间复杂度要比O(n^2)要好很多。
最后 欢迎大家关注我的公众号 程序员共成长。每天都会分享技术干货，包括不限于Java、数据量、Linux、职场感悟，大厂面试等。另外还有各种学习资源