排序算法——插入排序

排序逻辑

每次遍历，保证前面的队列是有序的

• 初始队列

  

• 第一轮

  

• 第二轮

  

• 第三轮

  

• 第四轮

  

代码示例

public static void insertSort(int[] arr){
  //从第二个数开始遍历所有的数字，每一次遍历保证前面的序列是有序的
  for(int i=1;i<arr.length;i++){
      //每次遍历保证前面的序列有序
      for(j=i-1;j>=0;j--){
          if(arr[j]>arr[j+1]){
              int temp = arr[j];
              arr[j] = arr[j+d];
              arr[j+d] = temp;
          }
      }
  }
}

选择排序每次都需要遍历前面所有的队列，但因为前面序列本身就是有序的，所以当前数大于前面一个数时，则不需要向前遍历，故可以小小优化一下

public static void insertSort(int[] arr){
    //从第二个数开始遍历所有的数字，每一次遍历保证前面的序列是有序的
    for(int i=1;i<arr.length;i++){
        //如果当前数字比前一个小则遍历前面的队列，否则加上该数队列仍然是有序的
        if(arr[i]<arr[i-1]){
            //将当前值存到 temp 中
            int temp = arr[i];
            int j;
            //从前一个数字向前遍历，每一个比 temp 大的数赋给它的后一位
            for(j=i-1;j>=0&&temp<arr[j];j--){
                //每一个比 temp 大的数，将当前数赋给后一个数
                arr[j+1] = arr[j];
            }
            //直到不比 temp 大的数，将 temp 赋给该位
            arr[j+1] = temp;
        }
    }
}

事件复杂度

O(n²)