2019独角兽企业重金招聘Python工程师标准>>> 
特点：局部有序
操作：标记需要需要插入的数，从右边开始比较，如果标记数大于比较数，比较数右侧数全体右移，标记数插入到比较数的右边
package sort.InsertSort;// insertSort.java
// demonstrates insertion sort
// to run this program: C>java InsertSortApp
//--------------------------------------------------------------
class ArrayIns{private long[] a; // ref to array aprivate int nElems; // number of data items
//--------------------------------------------------------------public ArrayIns(int max) // constructor{a = new long[max]; // create the arraynElems = 0; // no items yet}
//--------------------------------------------------------------public void insert(long value) // put element into array{a[nElems] = value; // insert itnElems++; // increment size}
//--------------------------------------------------------------public void display() // displays array contents{for(int j=0; j<nElems; j++) // for each element,System.out.print(a[j] + " "); // display itSystem.out.println("");}
//--------------------------------------------------------------public void insertionSort(){int in, out;for(out=1; out<nElems; out++) // out is dividing line {long temp = a[out]; // 标记插入数in = out; while(in>0 && a[in-1] >= temp) // 从右边开始比较，如果标记数大于比较数，比较数右侧数全体右移 {a[in] = a[in-1]; --in; }a[in] = temp; //标记数插入到比较数的右边// insert marked item} // end for} // end insertionSort()
//--------------------------------------------------------------} // end class ArrayInsclass InsertSortApp{public static void main(String[] args){int maxSize = 100; // array sizeArrayIns arr; // reference to arrayarr = new ArrayIns(maxSize); // create the arrayarr.insert(77); // insert 10 itemsarr.insert(99);arr.insert(44);arr.insert(55);arr.insert(22);arr.insert(88);arr.insert(11);arr.insert(00);arr.insert(66);arr.insert(33);arr.display(); // display itemsarr.insertionSort(); // insertion-sort themarr.display(); // display them again} // end main()} // end class InsertSortApp
