java排序3（插入排序）

package hello;import java.util.Random;/** *插入排序: * 需要时间O(N*N),但是在一般情况下,要比冒泡排序快一倍,也比选择排序快 * 它经常用在较复杂排序算法的最后阶段,例如快速排序 * 局部有序,再进行插入比较 *  * 但是:对于逆序排序的数据,每次比较和移动都会执行,所以这样并不比冒泡排序快. *  * 不变性: */public class InsertSortApp {public static void main(String[] args) {long ls = System.currentTimeMillis();int maxSize = 10000;InsertSort arr;arr = new InsertSort(maxSize);Random r = new Random();//insert 10 itemsfor(int i=0;i<10000;i++){arr.insert(r.nextInt(100));}arr.display();arr.insertionSort();arr.display();System.out.println(System.currentTimeMillis()-ls);}}class InsertSort extends BubbleSort{public InsertSort(int max) {super(max);}/** * 在外层的for循环中,out变量从1开始,向右移动. * 他标记了未排序部分的最左端的数据. * 内层的while循环中,in的变量从out开始,向左移动, * 直到temp变量小于in所指的数组数据项,或者它已经不能左移为止. * while循环的每一趟都向右移动了一个已经排好序的数据项. *  */public void insertionSort(){int in,out;for(out=1;out<nElems;out++){long temp = a[out];in = out;while(in>0&&a[in-1]>=temp){a[in] = a[in-1];--in;}a[in] = temp;}}}