首页 / 算法 / 排序算法(一) 直接插入排序及改进
排序算法(一) 直接插入排序及改进
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了排序算法(一) 直接插入排序及改进，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1119字，纯文字阅读大概需要2分钟。
内容图文
-
直接插入排序
直接插入排序就是每步将一个待排序的记录按其关键字的大小插到前面已经排序的序列中的适当位置，直到全部记录插入完毕为止。比较简单就直接上代码了。
-
代码
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;
}
}
原文：http://www.cnblogs.com/yangtong/p/6906278.html
内容总结
以上是互联网集市为您收集整理的排序算法(一) 直接插入排序及改进全部内容，希望文章能够帮你解决排序算法(一) 直接插入排序及改进所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。