插入排序 の implementation
插入排序就像打赌的时候，比如双扣。抽牌的时候，一次拿一张牌，这张牌和之前的牌一张张比较。选择把这张牌插入什么位置，排好顺序的位置后打牌更顺。要不然得一个一个找到时麻烦。也不利于打牌的大局观。看下图
假设第一次抽到梅花7， 不用排序。因为只有一张
接着抽到梅花10 
。因为10比7大，所以不用排序。
再接着抽卡。发现抽到了梅花5 
。这个时候不要犹豫，2点真的不算大的。果断弃牌
立即学习“Java免费学习笔记（深入）”；
接着我们拿 5 和 10 比较。 5 小于 10 所以交换位置。
拿5再和7比。 5 比 7 小。 所以交换 5 和 7 的位置 得到
。
这个时候就已经是sorted的了。 原理就是这样子。
因为比较简单。直接贴上代码
// O(n^2) 最坏的情况
// 最好的情况 O(n)
public static void sort(Comparable[] a) {
for (int i = 1; i < a.length; i++) {
for (int j = i ; j > 0; j--) {
if (less(a[j], a[j - 1]))
exch(a, j, j - 1);
else
break;
}
}
}
public static void sort(Comparable[] a, int low, int hi) {
for (int i = low; i <= hi ; i++) {
for (int j = i ; j > low; j--) {
if (less(a[j], a[j - 1]))
exch(a, j, j - 1);
else
break;
}
}
}
InsertSort
性能分析
最坏的情况就是每次抽到的卡是最小的。这个时候每次都需要从尾部遍历到头部。时间是N ^ 2成正比
最好的情况就是已经排好序了。因为已经排好序了。所以每次抽到的牌都不需要排序。 时间是 N 成正比
以上就是Java排序之InsertionSort插入排序的实例的详细内容，更多请关注php中文网其它相关文章！
java怎么学习？java怎么入门？java在哪学？java怎么学才快？不用担心，这里为大家提供了java速学教程(入门到精通)，有需要的小伙伴保存下载就能学习啦！
广告![ThinkPHP5快速开发企业站点[全程实录]](https://img.php.cn/upload/course/000/000/068/6253d918a3ce7278.png)
收藏
收藏
Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
974
