首页 > 代码库 > BasicSort — InsertionSort
BasicSort — InsertionSort
一、插入排序
核心:通过构建有序序列,对于未排序序列,在已排序序列中从后向前扫描(对于单向链表则只能从前往后遍历),找到相应位置并插入。实现上通常使用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 } }
BasicSort — InsertionSort
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。