java排序三(插入排序)
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 items for(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; } } }