校园时光不多，准备找工作，多看点东西增加知识，为自己助力！加油！

插入排序：简单的排序方法

基本的操作：将一个新的记录插入到已经排好序的有序数组中

影响时间复杂度的因素：记录间的比较与移动

原始的插入排序算法：时间复杂度O(n²)

1 //插入排序算法 2 public void simpleSort(int[] array){ 3         for(int i=1; i
     
      =0&&temp
     

折半插入排序：使用折半查找，找出已经排序好的数组中，新的记录应该插入的位置。

改进效果：记录之前的比较次数减少了，但移动次数不变，因此时间复杂度不变。

/*     * 折半插入排序     * 目的：减少比较次数     * 时间复杂度：O(n^2) [移动次数没有变]     */    public void binaryInsertSort(int[] array){        for(int i=1; i
     
      high; j--){                array[j+1]=array[j];            }            array[high+1]=temp;        }    }
     

2路插入排序算法：在折半插入排序的基础上再改进，使用与原始数组大小的数组作为辅助空间，旨在减少记录的移动次数。

注意：如果当选择的第一个元素为数组中最大或者最小的元素的时候，这种排序方法会退化。

1     /* 2      * 二路插入排序 3      * 目的：为了减少移动次数 4      * 额外消耗：需要n个存储空间 5      */ 6     public int[] tInsertSort(int[] array){ 7         int[] cArray= new int[array.length]; 8         int start=0,end=array.length-1; 9         int temp = array[0];10         11         for(int i=1; i
     
      =0&&array[i]
      
       cArray[k];k++){30                         cArray[k-1]=cArray[k];31                     }32                     cArray[k-1]=array[i];33                     end--;34                 }    35             }36         }37         cArray[++start]=temp;38         39         return cArray;40     }
      
     

表插入排序方法：减少记录的移动，但是时间复杂度依旧不变

1     /* 2      * 表插入排序 3      * 目的：为了减少移动的次数 4      */ 5     public void tableInsertSort(DataItem[] array){ 6         for(int i=2;i

希尔排序：又称缩小增量排序，在时间效率上该算法有所提高。

使用增量数组，来按照间隔来对数组中的元素进行排序。

关于增量数组的选择：还没有统一的定论，当inc[k]=2^t-k+1+1，其中t为排序趟数，1<=k<=t<=log₂(n+1)的时候，希尔排序的时间复杂度为O(n^3/2).

1     /* 2      * 希尔排序 3      * 使用一个增量数组，按照数组中的值跳着对数组中的值进行排序 4      */ 5     public void shellSort(int array[],int[] incArray){ 6         for(int i=0; i
     
      =0&&temp