搜公众号
推荐 原创 视频 Java开发 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库
Lambda在线 > 朝阳杨大爷 > Java常见排序算法——直接插入排序

Java常见排序算法——直接插入排序

朝阳杨大爷 2019-04-16
举报
Java常见算法
直接插入排序


概念:

将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录递增1的有序表。
插入排序是进行值移动,而是不值交换。所以在量较小的情况下插入排序性能要优于冒泡和简单选择排序。

原理:

设有一组关键字{K1, K2,…, Kn};排序开始就认为 K1 是一个有序序列;让 K2 插入上述表长为 1 的有序序列,使之成为一个表长为 2 的有序序列;然后让 K3 插入上述表长为 2 的有序序列,使之成为一个表长为 3 的有序序列;依次类推,最后让 Kn 插入上述表长为 n-1 的有序序列,得一个表长为 n 的有序序列。
具体算法描述如下:

  1. 从第一个元素开始,该元素可以认为已经被排序

  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描

  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置

  4. 重复步骤 3,直到找到已排序的元素小于或者等于新元素的位置

  5. 将新元素插入到该位置后

  6. 重复步骤 2~5

列如我们有一个数组[5 7 4 29 10 11]共六个,我们按照从小到大排序:
排序过程如下

[5]   7   4   29   10   11
↑ │
└───┘

[5 7] 4 29 10 11
↑ │
└─────────┘

[4 5 7] 29 10 11
↑ │
└────┘

[4 5 7 29] 10 11
↑ │
└────────┘

[4 5 7 10 29] 11
↑ │
└────────┘

[4 5 7 10 11 29]

从中我们可以看到
在最好的情况下,只需进行比较n - 1次,无需进行移动;
在最坏的情况下,比较(n + 2)(n - 1)/2次,交换(n + 4)(n - 1)/2次。

代码

  //从小到大排序
public void insertionSort() {
for (int i = 1; i < array.length; i++) {
int key = array[i];
int j = i - 1;
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = key;
}

}

//从大到小排序
public void insertionSort2() {
for (int i = 1; i < array.length; i++) {
int key = array[i];
int j = i - 1;
while (j >= 0 && array[j] < key) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = key;
}
}

另一个版本:

//将arr[i] 插入到arr[0]...arr[i - 1]中
public static void insertion_sort(int[] arr) {
for (int i = 1; i < arr.length; i++ ) {
int temp = arr[i];
int j = i - 1;
//如果将赋值放到下一行的for循环内, 会导致在第10行出现j未声明的错误
for (; j >= 0 && arr[j] > temp; j-- ) {
arr[j + 1] = arr[j];
}
arr[j + 1] = temp;
}
}

算法系列:



二分插入排序

Java和Kotlin代码我均放在了GitHub上,欢迎Star!

https://github.com/yang0range/MyAlgorithm


据说,每个年轻、优秀、颜值高的互联网人都关注了我!


版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《Java常见排序算法——直接插入排序》的版权归原作者「朝阳杨大爷」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注朝阳杨大爷微信公众号

朝阳杨大爷微信公众号:CY_YANG_DA_YE

朝阳杨大爷

手机扫描上方二维码即可关注朝阳杨大爷微信公众号

朝阳杨大爷最新文章

精品公众号随机推荐

举报