理解插入排序，希尔排序，选择排序的算法原理
在前面的文章中，其实已经把效率比较高的排序算法给分析过了，比如比较通用的快排，归并排序和堆排，还有用于特定场景的计数排序等。本篇我们把剩下的几种效率一般的排序算法给介绍一下，分别是插入排序，希尔排序和选择排序。
插入排序（Insert Sort）
插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
这里我们假如有个无序数组如下，这里为了突出其排序规律，我们故意采用了一组降序的数字：
10,9,8,7,6排序的过程如下：
[9, 10, 8, 7, 6]
[8, 9, 10, 7, 6]
[7, 8, 9, 10, 6]
[6, 7, 8, 9, 10]从上面可以看到，每个元素会被依次加入上前面的有序序列，反复如此，直到全部排完序。
代码如下：
public static void sort(int[] numbers){
for (int i = 1; i < numbers.length; i++) {
//取遍历的每一个元素
int currentNumber = numbers[i];
int j = i - 1;
//每一个元素，都会与前面所有的有序元素集合进行比较
//从而交换自己的位置
while (j >= 0 && numbers[j] > currentNumber) {
numbers[j + 1] = numbers[j];
j--;
}
//找到当前元素的位置，然后交换。
numbers[j + 1] = currentNumber;
System.out.println(Arrays.toString(numbers));
}
}不难发现，对于n个元素的排序，插入排序是需要n*（n-1）次比较和交换的，所以其平均的时间复杂度为О(n²),空间复杂度属于原地排序，只需要一个额外的变量，所以是O(1)，此外这种算法属于稳定性算法，不会改变相等元素的相对位置。
希尔排序 （Shell Sort）
希尔排序也称递减增量排序算法或，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
在插入排序中，每个排序一个元素，需要经过若干次交换才能归位，所以在希尔排序中，采用了步长来优化，这中方法每次可以交换两个元素，在最后步长等于1的时候，会退化成插入排序，但这个时候元素的位置基本有序，只需要执行少量的移动和交换即可完成排序，所以算是对插入排序的一种优化。
给定一个无序数组：
10,9,8,7,6这里我们按数组的长度除以2来获取步长，则等于5/2=2;
那么则先进行
8 比 10 交换
7 比 9 交换
6 比 8 交换
最终必定会执行一次步长为1，也就是退化成插入排序，步骤如下：
[8, 9, 10, 7, 6]
[8, 7, 10, 9, 6]
[6, 7, 8, 9, 10]
[6, 7, 8, 9, 10]上面的是根据步长进行的比较交换，我们可以发现规律，这两个比较的数字的索引间距是2。
第一轮交换后，数组一部分已经有序，然后步长继续缩减=2/2=1，这个时候，希尔排序彻底退化为插入排序，这个时候虽然也需要量量比较，但是移动次数却大大减少，所以效率相比原生的插入排序要高，但是这个效率与步长的间隔是有关系的，所以希尔排序的平均时间复杂度为：O(nlog^2 n) 平均空间复杂度是O(1)，由于需要跨越交换，所以不属于稳定排序。
下面我们看下Java代码如何实现：
public static void sort(int array[]){
//初始化步长
int number = array.length / 2;
//只要步长大于1，就继续排序
while (number >= 1) {
//遍历从步长开始的位置元素
for (int i = number; i < array.length; i++) {
//取出来当前遍历的元素
int temp = array[i];
//得到当前位置减去步长后的下标
int j = i - number;
//比较当前值与步长值的大小
while (j >= 0 && array[j] > temp) {
array[j + number] = array[j];
j = j - number;
}
//赋值交换
array[j + number] = temp;
System.out.println(Arrays.toString(array));
}
//步长继续缩小，最终一定是1，整个算法退化成插入排序
number = number / 2;
}
}选择排序（Select Sort）
选择排序是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。
选择排序的思想我认为非常容易理解，简单的说就是，每次找到数组中的最小值，然后放入对应的位置，因为条件是最小值，所以元素本身就在正确的位置，就不会移动，减少了移动的次数。
给定无序数组：
10,19,8,7,1其排序步骤如下：
[1, 19, 8, 7, 10]
[1, 7, 8, 19, 10]
[1, 7, 8, 19, 10]
[1, 7, 8, 10, 19]这里面可以看到第一次找到最小值1，然后与数组开始的10交换，第二次在剩下的数组中找到了7是最小值，然后与第2位置的19交换，第三次发现8在剩下元素中就是正确的位置，最后19与10交换，至此就完成了整个排序。
这里面的平均时间复杂度为О(n²)，因为每一次查询最小值，都需要在剩下的数组中遍历一次，对于n个元素，需要n-1轮的比较查找。
其平均空间复杂度为O(1)，这里面仅仅需要一个辅助元素即可。
选择排序采用数组实现的方式为非稳定排序方式。
代码如下：
public static void sort(int arr[]){
int min;//存储每次遍历得到的最小元素的数组下标值.
int swap;//存储代待交换元素的值.
for (int i = 0; i < arr.length; i++) {
//依次数组的下标赋值.
min = i;
//遍历剩余部分的元素，找到最小值的下标.
for (int j = i; j < arr.length; j++) {
// 比较元素值.
if (arr[j] < arr[min]) {
min = j;//下标赋值.
}
}
//每次把最小值提前.
swap = arr[min];
arr[min] = arr[i];
arr[i] = swap;
System.out.println(Arrays.toString(arr));
}
}总结：
本文主要了介绍了插入排序，希尔排序，选择排序的算法原理和思想，尽管这些排序算法并不是最优的选择，并不适合大数据量集下的排序，但是了解这些算法的基本思想还是很有必要的。
腾讯云开发者
