排序原理:

①将数据分为已排序和未排序两部分。
②将未排序数据第一个插入 到已排序数据中的合适位置
③倒序遍历已排序数据，直到找到一个小于等于插入数据的数据，则将插入数据插入到该数据后面，将原本之后的数据后移一位。

时间复杂度：

最好情况：O(n)
最坏情况：O(n^2)
平均情况：O(n^2)

空间复杂度：

O(1)

稳定性：

稳定

实现：

API设计:

①主排序算法用于排序
public static void sort(int[] a)
② 比较API，用于比较两个元素大小
private static boolean greater(int[] a,int v,int w)
③交换API，用于交换两个索引位置的值
private static void exchange(int[] a,int i,int j)

API实现:

//主排序算法用于排序
           public static void sort(int[] a) {
               for(int i = 0;i < a.length - 1;i ++) {
                   for(int j = i;j > 0;j--) {
                       //如果前一元素大于等于待插入元素，则将两元素交换，直到前一元素小于待插入元素
                       if(greater(a,j-1,j)) {
                           exchange(a,j-1,j);
                       }else {
                           break;
                       }
                   }
               }
           }
         //比较API，用于比较两个元素大小
           private static boolean greater(int[] a,int v,int w) {
               if(a[v] > a[w]) {
                   return true;
               }
               return false;
           }
           //交换API，用于交换两个索引位置的值
           private static void exchange(int[] a,int i,int j) {
               int temp = a[i];
               a[i] = a[j];
               a[j] = temp;
           }