插入（希尔）排序时间、空间复杂度

希尔）排序时间、空间复杂度"/>

插入（希尔）排序时间、空间复杂度

插入排序：

算法优点：稳定，快。
算法缺点：比较次数不一定，比较次数越多，插入点后的数据移动越多（特别是当数据总量庞大的时候）。但用链表可以解决这个问题。

适用：当元素数量小，分布有序，要求稳定直接插入排序将大大减少比较次数和移动记录的次数

希尔排序

优缺：

 时间复杂度取决于所用序列：

不稳定；取决于增量序列选择的好坏

插入排序改进措施

1. 优化为希尔排序：希尔排序法是对直接插入排序法的优化，通过设置一个增量，对原始序列进行分组，对每组用直接插入排序法排序再整合，再缩小增量，周而复始直至增量为1，完成排序，因此又叫“缩小增量排序法”。
           其实到希尔算法进行到最后，n的值变为1（即增量或者称跳跃数变为1）的时候，它就是直接插入排序，只不过这时候，整个序列基本上是有序的，需要交换的数据已经非常少了，提高效率。

package main.Test;import java.util.Arrays;public class XiErSort {//    非递归private static void sort(int arr[]) {for(int d = arr.length/2; d >= 1; d/=2) {for(int i = d; i < arr.length; i++) {int j = i;while (j - d >= 0 && arr[j - d] > arr[j]) {swap(arr, j, j - d);j -= d;}}}}//    递归private static void sort(int arr[], int d) {for(int i = d; i < arr.length; i++) {int j = i;while (j - d >= 0 && arr[j - d] > arr[j]) {swap(arr, j, j - d);j -= d;}}if (d/2 >= 1)sort(arr, d/2);}private static void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}public static void main(String[] args) {int[] a = new int[]{1, 2, 4, 5, 3, 1, 2, 3};sort(a, a.length);System.out.println(Arrays.toString(a));}
}