排序算法-插入排序

原理

1.默认按照从小到大的排序规则。
2.当对一个新数组排序时，每次确定某个元素位置的时候，将当前元素之前的元素与当前元素做对比换位。
3.每次换位之后，当前元素之前的元素都是排好顺序的，直至最后一个元素插入好位置。

图示

代码演示

public static void Sort(int[] array)
{
  for(int i = 1; i < array.Length; i++)
  {
      var temp = array[i];
      int j = i - 1;
      while(j >= 0 && array[j] > temp)
      {
          array[j + 1] = array[j];
          j--;
      }
      array[j + 1] = temp;
  }
}

分析

1.最好的时间复杂度是已经排好序的数组，O(N)。
2.最坏的时间复杂度是逆序排列的数组，O(N²)。

源码地址： https://github.com/woniuSnail/BaseAlgorithm.git