本文共 3339 字，大约阅读时间需要 11 分钟。

1.直接插入排序

基本思想

在要排序的一组数中，假设前面(n-1) [n>=2] 个数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。

图像示例

算法实现

一种是从后往前插入，也是java.util.Array的实现方式

private static	int[] insertSort(int[] array, int low, int high) {  //从后往前插入，Array里面实现    	for(int i=low+1;i<=high;i++) {    //比较值  无=最后一个值不参与比较  low+1可以为low(Array实现）    		for (int j=i;j>low&&(array[j-1]>array[j]);j--){  //从后开始插入，每次最后的几个元素是有序的    			swap(array,j,j-1);    			    		}    	    	}    	return array;    }

一种是从前往后插入

private static	int[] insertSort2(int[] array, int low, int high) {//从前往后插入    	for(int i=low+1;i<=high;i++) {  //第一个值不用比较，不影响  ,要=high    		    		int insertElem=array[i];//    		int j=i-1;  //    		for (;j>=0;j--){//    			if(array[j]>insertElem) {  //找到比插入值大的值将它和之后的值全部顺移往后一位（从小到大排序）//    				array[j+1]=array[j];//    			}//    			else {break;}//    			//    		}//    		array[j+1]=insertElem;  //插入值位置    		int j=i;  //也可以j=i-1    		for (;j>0;j--){ //如果是j=i-1，这里j要>=0    			if(array[j-1]>insertElem) {  //找到比插入值大的值将它和之后的值全部顺移往后一位（从小到大排序）    				array[j]=array[j-1];//[0,j]有序区？    			}    			else {break;}    			    		}    		array[j]=insertElem;  //插入值位置     j-1为-1  ？这里的j已经在for循环里-1了    	    	}    	return array;    }

简单分析

时间复杂度 O(n^2)

空间复杂度O(1)

满足稳定排序

算法优化

折半插入（二分插入）

优化思路：使用二分查询减少比较次数（在数据量越大时效果越明显）

private static int[] binaryInsertSort(int[] array, int low, int high) {    	int i,j,index,temp;    	for( i=1;i<=high;i++) {    		index=binarySearch(array,0,i,array[i]);    		temp=array[i];    		for(j=i;j>index;j--) {  //j>index?  j和index之间的数后移    			array[j]=array[j-1];    			    		}    		array[index]=temp;  //插入    	}    	return array;    }        private static int binarySearch(int[] array, int low, int high , int key) {    	int mid = (low+high)>>1;    	if(low > high) {    		return low;    	}    	if(array[mid]==key) {    		return mid;    	}    	else if(array[mid]>key) {    		return binarySearch(array,low,mid-1,key);    		    	}    	else {    		return binarySearch(array,mid+1,high,key);    	}    }

2路插入

之前的折半插入是减少了比较次数，那么可不可以减少移动次数，当然可以，一种思路就是表插入，利用链表和数组之间的差异，在数组中移动需要移动其他数组元素，在链表中只需要直接插入即可

还有一种思路就是将数组当做循环数组，大于最大元素时插入到尾端，小于最小元素时插入到首端，中间元素插入到数组中间，这种实现需要一个辅助数组，最后将辅助数组里面的元素复制到原数组（再优化思路可以在插入时用二分插入，或者不用辅助数组，用中间变量，将要改变位置的元素和该位置元素交换，可以将空间复杂度降为O(1)，暂时不实现了，后续再添加）

private static  int[] twoInsertSort(int [] iRawBuff,int low, int high) {    	//21345    	int fin = 0;    	int fir = 0;        int iLenght = (high-low+1);         	int iTempBuff[] = new int[iLenght];    	//int iRawBuff[]  = new int[iLenght];    	iTempBuff[0] = iRawBuff[0];    	for (int i = 1; i < iLenght;i++)    	{    		if(iRawBuff[i] >= iTempBuff[fin])    		{    			//大于当前最大值，后插    			 fin=(fin+1+iLenght)%iLenght;    			iTempBuff[fin] = iRawBuff[i];    		    		}    		if(iRawBuff[i]<= iTempBuff[fir])    		{    			//小于当前最小值,前插    			fir = (fir-1+iLenght)%iLenght;    			iTempBuff[fir] = iRawBuff[i];    		    		}    		if(iRawBuff[i] < iTempBuff[fin]&&iRawBuff[i] > iTempBuff[fir])    		{    			//大于当前最小值，小于当前最大值，中间插    			int j = fin++;    			while (iRawBuff[i] < iTempBuff[j])    			{    				iTempBuff[(j+1)%iLenght] = iTempBuff[j];    				j = (j-1+iLenght)%iLenght;    			}                iTempBuff[j+1] = iRawBuff[i];   //9999?    		    		}    		    	}    	//导入输入到原始数组中    	for (int k = 0; k < iLenght; k++)    	{    		iRawBuff[k] = iTempBuff[(fir+k)%iLenght];    	}    	return iRawBuff;    }