流年似水博客开通了,本站主要是写关于Web和大数据方面内容,正在更新中,欢迎大家光临!
  1. 文章:97 篇
  2. 总浏览:54,191 次
  3. 评论:22条
  4. 最后更新:2020-06-08
  5. 分类目录:39 个

Java之插入排序详解

Java l, xy 430℃ 0评论

数据结构排序算法之插入排序详解(java实现)

前言

  1. 相信学过数据结构的人都知道这个插入排序算法,不多说,今天就总结一下这个算法。
  2. 注意:测试环境为java8

知识点一:插入排序思想

  1. 插入排序:将一个记录插入到一个已经排好序的列表中,使得新列表仍然有序。
  2. 可能你看到这个会有点晕,没关系听我慢慢解释一下:
  3. 1,首先假设我们的列表项的第一个项是有序的
  4. 2,我们从列表的第二项开始遍历,在循环中遍历当前项以前有序列表,找到当前项插入的位置
  5. 3,移动有序列表的位置,空出插入位置
  6. 4,在插入位置插入当前项

插入排序原理动画图:

知识点二:插入排序分类

  1. 1,直接插入排序:逐个遍历查找
  2. 2,折半插入排序:查找插入位置阶段使用二分查找实现

知识点三:时间复杂度、稳定性、辅助空间

  1. 时间复杂度:O(n^2)
  2. 稳定性:稳定排序
  3. 辅助空间:O(1)

知识点四:java实现

1.java实现直接排序(默认升序)

  1. /**
  2. * 直接选择排序实现 (默认升序)
  3. */
  4. private void selectionSort(int[] ints) {
  5. Objects.requireNonNull(ints);
  6. for (int i = 1; i < ints.length; i++) {
  7. int temp = ints[i];
  8. //后面一项小于前面一下需要排序
  9. if (temp < ints[i - 1]) {
  10. int j;
  11. for (j = i - 1; j >= 0; j--) {
  12. if (ints[j] > temp) {
  13. //移动位置
  14. ints[j + 1] = ints[j];
  15. } else {
  16. break;
  17. }
  18. }
  19. ints[j + 1] = temp;
  20. }
  21. }
  22. }

测试类:

  1. @Test
  2. public void test() {
  3. int[] ints = { 1,52, 16,78, 1, 1};
  4. selectionSort(ints);
  5. Arrays.stream(ints).forEach(System.out::println);
  6. }

结果:

  1. 1
  2. 1
  3. 1
  4. 16
  5. 52
  6. 78

2.java实现折半插入排序

  1. /**
  2. * 折半选择排序,升序
  3. */
  4. private void halfSelectionSort(int[] ints) {
  5. Objects.requireNonNull(ints);
  6. for (int i = 1; i < ints.length; i++) {
  7. int temp = ints[i];
  8. if (temp < ints[i - 1]) {
  9. //遍历查找i元素插入的位置
  10. int low = 0, high = i - 1, mid = (low + high) / 2;
  11. while (low <= high) {
  12. if (ints[mid] > temp) {
  13. high = mid - 1;
  14. } else {
  15. low = mid + 1;
  16. }
  17. mid = (low + high) / 2;
  18. }
  19. //移动插入位置之前的元素
  20. for (int j = i; j > low; j--) {
  21. ints[j] = ints[j - 1];
  22. }
  23. //插入当前元素
  24. System.out.println("当前元素ints[i] = " + temp + "插入到了" + low + "位置");
  25. ints[low] = temp;
  26. }
  27. }
  28. }

测试代码:

  1. @Test
  2. public void test() {
  3. int[] ints = { 1,52, 16,78, 1, 1};
  4. //selectionSort(ints);
  5. halfSelectionSort(ints);
  6. //halfSelectionSortDesc(ints);
  7. Arrays.stream(ints).forEach(System.out::println);
  8. }

测试结果:

  1. 当前元素ints[i] = 16插入到了1位置
  2. 当前元素ints[i] = 1插入到了1位置
  3. 当前元素ints[i] = 1插入到了2位置
  4. 1
  5. 1
  6. 1
  7. 16
  8. 52
  9. 78

3.java实现折半查找倒序

  1. /**
  2. *折半选择排序,降序
  3. * */
  4. private void halfSelectionSortDesc(int[] ints) {
  5. Objects.requireNonNull(ints);
  6. for (int i = 1; i < ints.length; i++) {
  7. int temp = ints[i];
  8. if (temp > ints[i - 1]) {
  9. //遍历查找i元素插入的位置
  10. int low = 0, high = i - 1, mid = (low + high) / 2;
  11. while (low <= high) {
  12. if (ints[mid] >= temp) {
  13. low = mid + 1;
  14. } else {
  15. high = mid - 1;
  16. }
  17. mid = (low + high) / 2;
  18. }
  19. //移动插入位置之前的元素
  20. for (int j = i; j > low; j--) {
  21. ints[j] = ints[j - 1];
  22. }
  23. //插入当前元素
  24. System.out.println("当前元素ints[i] = " + temp + "插入到了" + low + "位置");
  25. ints[low] = temp;
  26. }
  27. }
  28. }

测试代码:

  1. @Test
  2. public void test() {
  3. int[] ints = { 1,52, 16,78, 1, 1};
  4. halfSelectionSortDesc(ints);
  5. Arrays.stream(ints).forEach(System.out::println);
  6. }

测试结果:

  1. 当前元素ints[i] = 52插入到了0位置
  2. 当前元素ints[i] = 16插入到了1位置
  3. 当前元素ints[i] = 78插入到了0位置
  4. 78
  5. 52
  6. 16
  7. 1
  8. 1
  9. 1

总结:

  1. 插入排序算是常用排序中简单的一个了,好好理解一下还是可以弄明白的。其核心的特点就是假设数据集合中的第一个元素已经是有序的了,
  2. 从第二个元素开始遍历插入到前面的有序列表中,使得插入后的有序列表仍然有序。

转载请注明:流年似水 » Java之插入排序详解

喜欢 (0)or分享 (0)

Warning: copy(https://cn.gravatar.com/avatar/?s=54&d=%2Fwp-content%2Fthemes%2Fyusi1.0%2Fimg%2Fdefault.png&r=g): failed to open stream: HTTP request failed! HTTP/1.1 400 Bad Request in /usr/share/nginx/html/timewentby/wp-content/themes/yusi1.0/functions.php on line 239

Warning: copy(/wp-content/themes/yusi1.0/img/default.png): failed to open stream: No such file or directory in /usr/share/nginx/html/timewentby/wp-content/themes/yusi1.0/functions.php on line 243
发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址