首页 > 代码库 > 排序算法(一) 直接插入排序及改进
排序算法(一) 直接插入排序及改进
-
直接插入排序
直接插入排序就是每步将一个待排序的记录按其关键字的大小插到前面已经排序的序列中的适当位置,直到全部记录插入完毕为止。比较简单就直接上代码了。
-
代码
public static <T extends Comparable<? super T>> void insertionSort(T[] a) { int j; for (int i = 1; i < a.length; i++) { T tmp = a[i]; for (j = i; j > 0 && tmp.compareTo(a[j-1]) < 0; j--) { a[j] = a[j-1]; } a[j] = tmp; } }
-
二叉查找插入排序
又之前的代码可以看出,直接插入排序的时间复杂度为O(n2),而且还可以看出,每次有新数据往里插的时候,都是从最后开始往前遍历,因为之前的数据已经是排好序的了,所以,我在查找应该插哪的时候,就可以使用二叉查找法来定位。这也是我看JDK源码Arrays.sort()方法时发现的。
-
代码
public static <T> void insertionSortWithBinary(T[] a, Comparator<? super T> c) { int lo = 0; int hi = a.length; int start = 1; for ( ; start < hi; start++) { T pivot = a[start]; int left = lo; int right = start; while (left < right) { int mid = (left + right) >>> 1; if (c.compare(pivot,a[mid]) < 0) right = mid; else left = mid + 1; } assert left == right; int n = start - left; switch (n) { case 2: a[left + 2] = a[left + 1]; case 1: a[left + 1] = a[left]; break; default: System.arraycopy(a, left, a, left + 1, n); } a[left] = pivot; } }
排序算法(一) 直接插入排序及改进
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。