插入和希尔排序

1. 插入排序-直接插入排序

   基本思想：把整个要排序的数列分为两部分，一个是有序，其余是无序，把无序数组内容逐渐加入有序数组内容进行排序，直至无序数组内容为空

   实现思路：把一个无序数字加入有序数组排序方式可以先找到要插入的下标，然后该下标之后的元素后移

   效率：

   时间复杂度：O（n^2）.

   java实现：

   public class InsertSort {
   
     public static void main(String[] args) {
   //    int[] array = {3, 9, -1, 10, 20};
   //    sort(array);
   //    System.out.println(Arrays.toString(array));
   
       int[] array = new int[80000];
       for (int i = 0; i < 80000; i++) {
         array[i] = (int) (Math.random() * 80000);
       }
       LocalDateTime localDateTime1 = LocalDateTime.now();
       System.out.println("执行前" + localDateTime1.format(DateTimeFormatter.ofPattern("yyyy-MM-DD "
           + "HH-mm-ss")));
       sort(array);
   
       LocalDateTime localDateTime2 = LocalDateTime.now();
       System.out.println("执行后" + localDateTime2.format(DateTimeFormatter.ofPattern("yyyy-MM-DD "
           + "HH-mm-ss")));
   
     }
   
     static void sort(int[] array) {
       // 下标从1开始，因为0看做是一个有序的
       for (int i = 1; i < array.length; i++) {
         // 新的将要插入的数据
         int insertVal = array[i];
         int insertIndex = i - 1;
         while (insertIndex >= 0 && insertVal < array[insertIndex]) {
           array[insertIndex + 1] = array[insertIndex];
           insertIndex--;
         }
         array[insertIndex + 1] = insertVal;
       }
     }
   
   }
   

JS实现：

function insertSort (arr) {
  for (var i = 1; i < arr.length; i++) {
    var temp = arr[i];
      //实际上这个可以拆开成for里面加一个if
      for (var j = i - 1; j >= 0 && temp < arr[j]; j--) {
        arr[j + 1] = arr[j];
      }
      arr[j + 1] = temp;
  }
  return arr;
}

2. 插入排序-希尔排序

   基本思想：（其实就是直接插入排序的变种，就变了一点点）

   1. 选择一个增量组成一个数组，进行排序，之后增量减半，直至增量为1；（一开始就排序两个数，然后越来越多，最后到1）

   2. 每个子数组用直接插入排序进行排序

  java实现：
  
  ```java
  public class ShellSort {
  
    public static void main(String[] args) {
  //    int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
  //    sort(arr);
  //    System.out.println(Arrays.toString(arr));
  
      int[] array = new int[80000];
      for (int i = 0; i < 80000; i++) {
        array[i] = (int) (Math.random() * 80000);
      }
      LocalDateTime localDateTime1 = LocalDateTime.now();
      System.out.println("执行前" + localDateTime1.format(DateTimeFormatter.ofPattern("yyyy-MM-DD "
          + "HH-mm-ss-SSS")));
      sort(array);
  
      LocalDateTime localDateTime2 = LocalDateTime.now();
      System.out.println("执行后" + localDateTime2.format(DateTimeFormatter.ofPattern("yyyy-MM-DD "
          + "HH-mm-ss-SSS")));
  
  
    }
  
    static void sort(int[] arr) {
      int length  = arr.length;
      int gap = length/2;
      while (gap > 0) {
        for (int i = gap; i < length; i++) {
          int index = i - gap;
          int insertVal = arr[i];
          while (index >= 0 && insertVal < arr[index]) {
            arr[index+gap] = arr[index];
            index = index - gap;
          }
          arr[index + gap] = insertVal;
        }
  //      System.out.println(Arrays.toString(arr));
        gap = gap/2;
      }
    }
  }
  ```
  
  js实现
  
  ```javascript
  function shellSort(arr) {
    var gap = Math.floor(arr.length / 2);
    while (gap >= 1) {
        for (var i = gap; i < arr.length; i++) {
            var temp = arr[i];
            for (var j = i - gap; j >= 0 && temp < arr[j]; j = j - gap) {
                arr[j + gap] = arr[j];
            }
            arr[j + gap] = temp;
        }
        gap = Math.floor(gap / 2);
    }
    return arr
  }
  ```