直接插入排序： 指每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。 1.首先在当前有序区array[1..i-1]中查找array[i]的正确插入位置j(1≤j≤i-1)；
for(j = i-1; j >= 0 && array[j] > temp; j --) { arr[j+1] = arr[j]; }temp为储存的array[i];将array中 j 后的记录均后移一个位置，腾出j位置上的空间插入array[i]。
public class button { public void charu(int [] array) { int x=0;//计数器，第x趟 for(int i=1;i<array.length;i++) { x++; int temp=array[i]; int j =0; //比目标数大的向后移 for(j= i; j >= 1 && array[j-1] > temp; j --) { array[j] = array[j-1]; } //找到目标位置，放入 array[j]=temp; System.out.print("\n第"+x+"趟："); for(int a:array) { System.out.print(a+" "); } } } public static void main(String []args) { int [] array={8,3,2,5,9,3,6}; System.out.print("初始："+" "); for(int a:array) { System.out.print(a+" "); } button button=new button(); button.charu(array); System.out.print("\n最终："+" "); for(int a:array) { System.out.print(a+" "); } } }
如果是一个有序递增的序列，只需要比较，不需要移动 O（n） 如果为递减序列，每次比较后，还必须依次移动 O（n^2） 若有两个相同的数，排序前后，相对位置不变 所以稳定；
希尔排序： 把待排序的数据元素分成若干个小组，对同一小组内的数据元素用直接插入法排序，小组的个数逐次缩小，当完成了所有数据元素都在一个组内的排序后，排序过程结束。 1，a[0]-a[n-1];待排序数组 2 ，b[0]-b[num-1];排序增量数组； 过程：
public class S{ public void shell(int[] a,int n,int [] b,int num) { int tmpe=0;//增量 int abc=0; int y=0; //循环增量数组，每次排序改变增量 for(int i=0;i<num;i++) { tmpe=b[i]; //小组个数 for(int j=0; j<tmpe; j++) { //在每个小组内直接插入排序，增量为tmpe for(int x=j; x<n-tmpe; x+=tmpe) { abc=a[x+tmpe]; y=x; while(y>-1&&abc<=a[y]) { a[y+tmpe]=a[y]; y=y-tmpe; } a[y+tmpe]=abc; } } System.out.println("第"+(i+1)+"趟："+"增量为"+tmpe+" "); for(int m=0;m<n;m++) { System.out.print(a[m]+" "); } System.out.println(); } } public static void main(String [] args) { int [] arr={9,1,2,5,7,4,8,6,3,5}; int len=arr.length; System.out.print("初始："); for(int i=0;i<len;i++) { System.out.print(arr[i]+" "); } System.out.println(); int [] brr={5,2,1}; int size=brr.length; new S(). shell(arr,len,brr,size); System.out.print("排序后："); for(int i=0;i<len;i++) { System.out.print(arr[i]+" "); } } }平均时间： O(n^1.3) 不稳定
