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

Java之冒泡排序详解

Java l, xy 587℃ 0评论

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

前言:

  1. 说起冒泡排序应该没有几个人不知道吧,今天来总结一下冒泡排序的知识。

知识点一:排序思想

  1. 冒泡排序:比较两个元素,如果不有序,则交换位置。每循环一次都会有某个元素放到恰到的位置。
  2. 另一种说法:
  3. 两两比较数据列表中的相邻的两项,满足条件,交换位置。每一轮循环中都会有一个元素放到指定的位置上,直到有序为止;

补充:动画原理图


知识点二:冒泡排序算法分类

  1. 1,基础冒泡排序
  2. 2,改进冒泡排序
  3. 3,进一步改进的冒泡排序
  4. 说明:
  5. 这里分类没有严格的意义,只是用来说明对冒泡排序改进的的一种说明。
  6. 建议大家写冒泡排序使用3,相对来说效率高一下。

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

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

知识点四:java实现

1.基础冒泡排序实现

  1. /**
  2. * 基础冒泡排序 (升序)
  3. */
  4. private void bubbleSort(int[] ints) {
  5. Objects.requireNonNull(ints);
  6. for (int i = 0; i < ints.length; i++) {
  7. //这里j要小于ints.length - 1,如果j < ints.length会报ArrayIndexOutOfBoundsException
  8. for (int j = 0; j < ints.length - 1; j++) {
  9. if (ints[j] > ints[j + 1]) {
  10. int temp = ints[j];
  11. ints[j] = ints[j + 1];
  12. ints[j + 1] = temp;
  13. }
  14. }
  15. }
  16. }

测试类:

  1. @Test
  2. public void test() {
  3. int[] ints = {12, 5, 78, 99, 31, 8};
  4. bubbleSort(ints);
  5. Arrays.stream(ints).forEach(System.out::println);
  6. }

测试结果:

  1. 5
  2. 8
  3. 12
  4. 31
  5. 78
  6. 99

2.改进的冒泡排序

改进说明:
  1. 定义一个标识变量来标志一次循环中有没有交换位置,如果在一次循环中没有交换位置,此时说明数据集合中已经有序,直接跳出循环即可。
  2. 这样可以避免内部循环多次判断,提高效率。
  1. /**
  2. * 改进冒泡排序 (升序)
  3. */
  4. private void bubbleSort1(int[] ints) {
  5. Objects.requireNonNull(ints);
  6. for (int i = 0; i < ints.length; i++) {
  7. //标志是否交换
  8. boolean flag = false;
  9. //这里j要小于ints.length - 1,如果j < ints.length会报ArrayIndexOutOfBoundsException
  10. for (int j = 0; j < ints.length - 1; j++) {
  11. if (ints[j] > ints[j + 1]) {
  12. int temp = ints[j];
  13. ints[j] = ints[j + 1];
  14. ints[j + 1] = temp;
  15. flag = true;
  16. }
  17. }
  18. //没有交换,说明现在已经是有序的,直接跳出循环
  19. if (!flag) {
  20. break;
  21. }
  22. }
  23. }

测试代码:

  1. @Test
  2. public void test() {
  3. int[] ints = {12, 5, 78, 99, 31, 8};
  4. //bubbleSort(ints);
  5. bubbleSort1(ints);
  6. //bubbleSort2(ints);
  7. Arrays.stream(ints).forEach(System.out::println);
  8. }

测试结果:

  1. 5
  2. 8
  3. 12
  4. 31
  5. 78
  6. 99

3.进一步改进的冒泡排序 (建议使用这个)

改进思想:
  1. 可以使用一个变量记录每次交换的最后位置,因为交换最后位置后面的元素都已经是有序的了,不需要在进行排序。默认交换的位置为数据集合的最后一个位置。
  2. 这样可以提高内部循环的效率,从而提高冒泡排序的整体效率。
  1. /**
  2. * 进一步改进的冒泡排序 (升序)
  3. * */
  4. private void bubbleSort2(int[] ints) {
  5. Objects.requireNonNull(ints);
  6. int lastSwap = ints.length - 1;
  7. for (int i = 0; i < ints.length; i++) {
  8. boolean flag = false;
  9. int m = lastSwap;
  10. for (int j = 0; j < m; j++) {
  11. if (ints[j] > ints[j + 1]) {
  12. int temp = ints[j];
  13. ints[j] = ints[j + 1];
  14. ints[j + 1] = temp;
  15. flag = true;
  16. lastSwap = j;
  17. }
  18. }
  19. if (!flag) {
  20. break;
  21. }
  22. }
  23. }

测试代码:

  1. @Test
  2. public void test() {
  3. int[] ints = {12, 5, 78, 99, 31, 8};
  4. //bubbleSort(ints);
  5. //bubbleSort1(ints);
  6. bubbleSort2(ints);
  7. Arrays.stream(ints).forEach(System.out::println);
  8. }

测试结果:

  1. 5
  2. 8
  3. 12
  4. 31
  5. 78
  6. 99

总结:

  1. 平时我们使用冒泡排序尽量使用我们改进过的,这样可以提高效率。

转载请注明:流年似水 » 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,您需要填写昵称和邮箱!

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