//直接插入查找
static void InsertSort(int[] arr,int length){
int i,j;
//依次将arr[2]~arr[n]插入前面已排序序列
for(i=2;i<=length;i++){
//若arr[i]关键字小于其前驱，则将arr[i]插入有序表
if(arr[i]
空间效率:仅使用了常数个辅助单元，因而空间复杂度为O(1)。
时间效率：在排序过程中，向有序子表中逐个插入元素的的操作进行了n-1趟，每趟操作都分为比较关键字和移动元素，而比较次数和移动次数取决于待排序的初始状态。
在最好的情况下：表中的元素已经有序，此时没插入一个元素，都只需比较一次而不用移动元素，因而时间复杂度为O(n)。
最坏的情况下：表中的元素为逆序，总的比较次数达到最大，总的移动次数也达到最大。
因此直接插入排序算法的时间复杂度为O(n^2)。
算法比较稳定。
折半插入排序
//折半查找
static void InsertSort2(int[] arr,int length){
int i,j,high,low,mid;
//依次将arr[2]~arr[n]插入到前面的已排序序列
for (i=2;i<=length;i++){
//暂时存入当前元素于arr[0]
arr[0]=arr[i];
//设置折半查找的范围
low=1;high=i-1;
//折半查找
while (low<=high){
//确定中间点
mid=(low+high)>>1;
//查找左半子表
if(arr[mid]>arr[0]){
high=mid-1;
}
//查找右半子表
else {
low=mid+1;
}
}
//统一后移元素，为插入元素腾位置
for(j=i-1;j>=low;j--){
arr[j+1]=arr[j];
}
//插入操作
arr[low]=arr[0];
}
}
空间复杂度：O(1)
时间效率：折半插入排序比直接插入排序仅减少了比较次数，约为O(nlog2n),该比较次数与待排序序列的初始状态无关，仅取决于表中元素的个数n;而元素的移动次数并未改变，它依赖于表的初始状态。因此时间复杂度为O(n^2)。
算法比较稳定。
希尔排序
//希尔排序
static void ShellSort(int[] arr,int length){
int dk,i,j;
//变化要比较两元素之间的距离
for (dk=length>>1;dk>=1;dk=dk>>1 ){
//依次往后分组，分组以两元素间隔距离为dk
for (i=dk+1;i<=length;i++){
//如果当前分组后者元素小于前者元素，则暂存后者元素于arr[0]
if (arr[i]0&&arr[0]
空间效率：O(1)
时间效率：由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题，所以时间复杂度比较难分析。当n在某个特定的范围时，希尔排序的时间复杂度约为O(n^1.3)。 在最坏情况下希尔排序的时间复杂度为O(n^2)。
算法不稳定。
最后写个main方法验证下
public static void main(String[] args) {
int[] arr=new int[]{-1，998857732,995773975,986263711,970050582,978672815,946770900,884642435,885254231,830140516,917959651,768122842,937296273,546931356,861262547,764532283,965184299,918973856,915272981,830623614,728999048,693597252,631219735,884688278,984427390,714012242,537616843,536343860,521612397,659978110,445747969,433183457,641532230,480363996,586696306,31693639,805374069,303753633,215386675,261627544,604354651,733048764,393354006,631784130,241316335,427529125,111935818,698504118,109686701,64838842,353487181,82447697,177571868,691252458,230964510,453463919,340316511,280992325,13701823,77481420,544069623,544526209,193715454,157540946,427514727,292446044,782703840,219297819,151485185,256184773,570872277,695760794,738644784,784607555,433518449,440403918,281397572,493886311,970466103,738026287,819959858,119093579,411203381,306242389,84356804,42607214,462370265,294497342,70309112,158982405,513023688,740856884,784337461,17092337,633020080,387052570,421701576,298738196,54807658,472147510,169670404};
int[] arr2=new int[]{-1,5,4,3,2,1};
//直接插入排序
// InsertSort(arr,arr.length-1);
//折半插入排序
// InsertSort2(arr,arr.length-1);
//希尔排序
ShellSort(arr,arr.length-1);
System.out.println(Arrays.toString(arr));
}
}
注意arr[0]为暂存元素，不算最终排序，所以数组长度应为arr.length-1
