几种常见的排序算法之--插入排序，希尔排序，选择排序总结
一：插入排序
基本思想：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。
定义一个变量i从第一号下标开始遍历整个数组，定义一个变量j,它的值为i - 1,从i - 1的位置开始直到0，随着i值的变化，j随着i变化，始终保持已经排序的数字为有序数组。如果j号下标的值小于i号小标的值，则直接结束此趟循环，因为j之前的数组为有序数组，所以无需再进行比较。
如下图的遍历过程：
代码实现：
//进行直接插入排序
public static void insert(int[] arr){//直接插入排序(是一个稳定排序）
//时间复杂度为O(n^2)，空间复杂度O(1)
int temp = 0; //越有序越快
for (int i = 1; i < arr.length; i++) {
int j = 0;
temp = arr[i];
for (j =i - 1; j >= 0; j--) {
if(arr[j] > temp){
arr[j + 1] = arr[j];
}else{
break;
}
}
arr[j + 1] = temp;
}
}特性总结：
1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定
二：希尔排序
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为选定值的记录分在同一组内，并对每一组内的记录进行排序。然后取不同的选定值（经检验选择为素数）重复上述分组和排序的工作。当到选定值最终为1时，所有记录在统一组内排好序。
现将已知数组分为选定值组，然后进行直接排序，当最终选定值为1时。把他们放到同一个组内进行直接排序，此时经过之前的排序之后已经变得比较有序，所以该算法比直接排序的时间复杂度要低。
画图实现过程：
可以明显发现，经过之前的几次排序之后，最后一次全排序的需要调整的数字明显变少，印证了越有序越快。
代码实现：
//希尔排序 分组之后进行直接插入排序
public static void shell(int[] arr,int gap){
int temp = 0; //越有序越快，不稳定
for (int i = gap; i < arr.length; i++) {
int j = 0;
temp = arr[i];
for (j =i - gap; j >= 0; j -= gap) {
if(arr[j] > temp){
arr[j + gap] = arr[j];
}else{
break;
}
}
arr[j + gap] = temp;
}
}
public static void shellSort(int[] arr){
int[] drr = {5,2,1}; //增量序列为素数
for (int i = 0; i <drr.length ; i++) {
shell(arr,drr[i]); //时间复杂度为1.3~1.5之间
}
}特性总结：
1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就
会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算，需要进行推导，推导出来平均时间复杂度： O(N^1.3—N^2）
4. 稳定性：不稳定
三：选择排序
基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。
画图实现过程：
圈出来的即是经过排序之后有序的数组。
代码实现：
//选择排序
public static void selectSort(int[] arr){//选择排序 不稳定 有跳跃式交换
for (int i = 0; i <arr.length ; i++) {
int j = 0; //时间复杂度为O(N^2)
int temp = 0;
for (j = i + 1;j <arr.length; j++){
if(arr[j] < arr[i]){
temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
}
}特性总结：
1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定