一、插入排序
核心：通过构建有序序列，对于未排序序列，在已排序序列中从后向前扫描(对于单向链表则只能从前往后遍历)，找到相应位置并插入。实现上通常使用in-place排序(需用到O(1)的额外空间)
从第一个元素开始，该元素可认为已排序取下一个元素，对已排序数组从后往前扫描若从排序数组中取出的元素大于新元素，则移至下一位置重复步骤3，直至找到已排序元素小于或等于新元素的位置插入新元素至该位置重复2~5性质：
交换操作和数组中倒置的数量相同比较次数>=倒置数量，<=倒置的数量加上数组的大小减一每次交换都改变了两个顺序颠倒的元素的位置，即减少了一对倒置，倒置数量为0时即完成排序。每次交换对应着一次比较，且1到N-1之间的每个i都可能需要一次额外的记录(a[i]未到达数组左端时)最坏情况下需要~N^2/2次比较和~N^2/2次交换，最好情况下需要N-1次比较和0次交换。平均情况下需要~N^2/4次比较和~N^2/4次交换二、实现
实现方式一：
package sort; public class InsertionSort { /** * 插入排序: * 1、从第一个元素开始，该元素可认为已排序 2、取下一个元素，对已排序数组从后往前扫描 3、若从排序数组中取出的元素大于新元素，则取出的元素移至下一位置 4、重复步骤3，直至找到已排序元素小于或等于新元素的位置 5、插入新元素至该位置 6、重复2~5 * @param args */ public static void main(String[] args) { int[] unsortedArray = new int[]{6, 5, 3, 1, 8, 7, 2, 4}; insertionSort(unsortedArray) ; System.out.println("After sort: "); for (int item : unsortedArray) { System.out.print(item + " "); } } public static void insertionSort(int[] array){ int len = array.length; for (int i = 0; i < len; i++) { int index = i, temp = array[i] ; while (index > 0 && array[index - 1] > temp) { array[index] = array[index - 1] ; index -= 1 ; } array[index] = temp ; for (int item : array) { System.out.print(item + " "); } System.out.println(); } } }实现方式二：
定义一个类，实现插入排序，并显示元素。
package insertionSort; public class ArrayIns { private long[] a ; // ref to Array a private int nElems ; // number of data items public ArrayIns(int max){ // constructor a = new long[max] ; // create the array nElems = 0 ; // no items yet } public void insert(long value){ // put element into array a[nElems] = value ; // insert it nElems++ ; // increment size } public void display(){ // display array contents for (int i = 0; i < nElems; i++) { System.out.print(a[i] + " "); } System.out.println(); } public void insertionSort(){ int out , in ; for (out = 1; out < nElems; out++) { // outer loop long temp = a[out] ; // remove marked item in = out ; // start shifts at out while(in > 0 && a[in-1] >= temp){ a[in] = a[in-1] ; // shift item to right in-- ; // go left one position } a[in] = temp ; // insert marked item } } }定义主程序入口，main函数
package insertionSort; import bubbleSort.ArrayBub; public class InsertionSort { public static void main(String[] args) { int maxSize = 100 ; // array size ArrayIns arr ; // reference to array arr = new ArrayIns(maxSize) ; // create the array arr.insert(6); arr.insert(5); arr.insert(3); arr.insert(1); arr.insert(8); arr.insert(7); arr.insert(2); arr.insert(4); arr.display(); // display items arr.insertionSort(); // bubble sort them arr.display(); // display items again } }
转载于:https://www.cnblogs.com/Wyao/p/7043663.html
相关资源：微信小程序源码-合集4.rar