Java与算法之(1) - 冒泡排序

2022-07-13 07:24:14

冒泡排序法的原理是，每次比较相邻的两个元素，如果它们的顺序错误就把它们交换过来。

例如对4 3 6 2 7 1 5这7个数字进行从小到大的排序，从最左侧开始，首先比较4和3

Java与算法之(1) - 冒泡排序

因为是从小到大排序，4和3的顺序显然是错误的，交换他们，得到

Java与算法之(1) - 冒泡排序

接下来比较4和6

Java与算法之(1) - 冒泡排序

顺序是正确的，不需要任何操作。接下来进行下一步，比较6和2

Java与算法之(1) - 冒泡排序

6显然应该排在2的后面，怎么办？交换它们，得到

Java与算法之(1) - 冒泡排序

经过前面几步，已经可以总结出规律，那么接下来要做的比较依次是：

7 > 1? 得到 3 4 2 6 1 7 5

7 > 5? 得到

Java与算法之(1) - 冒泡排序

到此，7的右边已经没有数可以比较，第一轮排队结束。经过这一轮，已经成功的把最大的数，即7放在了最后。但是前面6个数的顺序还是不对，但是按照上面的思路很容易想到，对前面6个数再来一遍，即可把6放到倒数第二的位置。然后再对前面5个数重复逐个比较的步骤。。。

7个数字需要进行7-1=6次排队，每完成一轮排队，下一轮排队需要比较的数字个数减1，来看代码

  1. public class BubbleSort {
  2. public void sort(int... numbers) {
  3. //n个数执行n-1轮
  4. //每一轮后完成一个数字归位, 下一轮要比较的数字个数减1(所以内层循环是j < n - i)
  5. int n = numbers.length - 1;
  6. int t;
  7. for(int i = 0; i < n; i++) {
  8. for(int j = 0; j < n - i; j++) {
  9. if(numbers[j] > numbers[j + 1]) {
  10. t = numbers[j];
  11. numbers[j] = numbers[j + 1];
  12. numbers[j + 1] = t;
  13. }
  14. }
  15. }
  16. }
  17. }

测试

  1. public static void main(String[] args) {
  2. int[] numbers = new int[]{ 4, 3, 6, 2, 7, 1, 5 };
  3. System.out.print("before: ");
  4. for(int i = 0; i < numbers.length; i++) {
  5. System.out.print(numbers[i] + "  ");
  6. }
  7. System.out.println();
  8. new BubbleSort().sort(numbers);
  9. System.out.print("after: ");
  10. for(int i = 0; i < numbers.length; i++) {
  11. System.out.print(numbers[i] + "  ");
  12. }
  13. System.out.println();
  14. }

输出

  1. before: 4  3  6  2  7  1  5
  2. after: 1  2  3  4  5  6  7

冒泡排序的核心是两层嵌套的循环，时间复杂度是O(N^2)，即对N个数排序，需要近似执行N的平方次。因为效率较低，实际开发中基本不会使用，但是因为简单易懂通常做为学习算法的入门案例。

如果用上面的代码对1 2 3 4 5 6 7做从小到大排列，会发现虽然数字已经排列好，但是程序还是要忠实的执行完全部两层循环。对这种情况，我们可以引入一个变量来记录一次内层循环中交换数字的个数，如果交换个数为0，则提前终止循环，在某些情况下可以提高效率。

  1. public void betterSort(boolean descend, int... numbers) {
  2. System.out.print("before: ");
  3. for(int i = 0; i < numbers.length; i++) {
  4. System.out.print(numbers[i] + "  ");
  5. }
  6. System.out.println();
  7. //n个数执行n-1轮
  8. //每一轮后完成一个数字归位, 下一轮要比较的数字个数减1(所以内层循环是j < n - i)
  9. int n = numbers.length - 1;
  10. int t;
  11. int flag = 0;
  12. for(int i = 0; i < n; i++) {
  13. for(int j = 0; j < n - i; j++) {
  14. if(descend) { //从大到小
  15. if(numbers[j] < numbers[j + 1]) {
  16. t = numbers[j];
  17. numbers[j] = numbers[j + 1];
  18. numbers[j + 1] = t;
  19. flag = 1;
  20. }
  21. } else {
  22. if(numbers[j] > numbers[j + 1]) {
  23. t = numbers[j];
  24. numbers[j] = numbers[j + 1];
  25. numbers[j + 1] = t;
  26. flag = 1;
  27. }
  28. }
  29. }
  30. if(flag == 0) {
  31. break;
  32. } else {
  33. flag = 0;
  34. }
  35. }
  36. System.out.print("after: ");
  37. for(int i = 0; i < numbers.length; i++) {
  38. System.out.print(numbers[i] + "  ");
  39. }
  40. System.out.println();
  41. }

增加一个变量需要额外占用内存空间，因此，这个方法是以空间换时间。

上一篇：JavaScript控制页码的显示与隐藏


下一篇：JavaScript判断某个对象属性是否存在