本文共 4413 字，大约阅读时间需要 14 分钟。

今日内容

• 冒泡排序

冒泡排序（Bubble Sort）

• 原理：重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。
• 步骤：
  1.比较相邻的元素。如果第一个比第二个大，就交换他们两个；
  2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数；
  3.针对所有的元素重复以上的步骤，除了最后一个；
  4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
• 动图演示：
  
• 代码实现

//冒泡排序基本做法public class BubbleSort {
       private static void main(int[] arr) {
           //第一轮：比4次        for (int i = 0; i < arr.length - 1; i++) {
               if (arr[i] > arr[i + 1]) {
                   int t = arr[i];                arr[i] = arr[i + 1];                arr[i + 1] = t;            }        }        System.out.println(Arrays.toString(arr));        //第二轮比3次        for (int i = 0; i < arr.length - 1 - 1; i++) {
               if (arr[i] > arr[i + 1]) {
                   int t = arr[i];                arr[i] = arr[i + 1];                arr[i + 1] = t;            }        }        System.out.println(Arrays.toString(arr));        //第三轮比2次        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
               if (arr[i] > arr[i + 1]) {
                   int t = arr[i];                arr[i] = arr[i + 1];                arr[i + 1] = t;            }        }        System.out.println(Arrays.toString(arr));        //第三轮比1次        for (int i = 0; i < arr.length - 1 - 1 - 1 - 1; i++) {
               if (arr[i] > arr[i + 1]) {
                   int t = arr[i];                arr[i] = arr[i + 1];                arr[i + 1] = t;            }        }        System.out.println(Arrays.toString(arr));    }}//代码优化1(双层for循环)public class BubbleSort {
       public static void main(String []args) {
           int []arr={
   13,45,34,23,56,23,14,33};        for (int i = 0; i < arr.length - 1; i++) {
               for (int j = 0; j < arr.length - 1 - i; j++) {
                   if (arr[j] > arr[j + 1]) {
                       int temp = arr[j];                    arr[j] = arr[j + 1];                    arr[j + 1] = temp;                }            }        }        System.out.println(Arrays.toString(arr));    }}//代码优化2：在排序过程中，我们可能会重复的去多次比较已排好的序列，这样就造成了冗余，当数据量大时，会明显的耗时。/*为解决这个问题，我们在这里添加一个lastIndex索引，用于标记最后一次交换的位置（注意，这里是交换不是比较），当交换到arr数组中7之前，也就是下标为4的时候，不再交换，说明后面的已经有序，下次就直接比较到下标为4的位置，后面的不再比较。另外，如果是倒序排正序，则没有优化，比较n*(n-1)/2次。*/public class BubbleSort {
       public static void main(String []args) {
           int []arr={
   13,45,34,23,56,23,14,33};            int i = arr.length - 1;            int count = 0; // 计数            while (i > 1) {
                   int lastChange = 1; // 记录最后一次交换位置                for (int j = 1; j < i; j++) {
                       // 前面比后面大，则进行交换                    if (arr[j] > arr[j + 1]) {
                           arr[j] = arr[j] + arr[j + 1];                        arr[j + 1] = arr[j] - arr[j + 1];                        arr[j] = arr[j] - arr[j + 1];                        lastChange = j; // 每交换一次更新一次                    }                    count++;                }                i = lastChange;            }            System.out.println(count);        }    }

• 时间复杂度与空间复杂度的计算

public class BubbleSort {
       public static void main(String []args) {
           //测试时间顺序        int arr[]=new int[10000];        Random r = new Random();        //给数组元素赋值        for(int i = 0;i
   
     arr[n + 1]) {
                       int temp = arr[n];                    arr[n] = arr[n + 1];                    arr[n + 1] = temp;                }                count++;            }        }        System.out.println(count);    }}
   

• 可以清楚的看到在测试数据量为10000时，双层for循环所需的次数为49995000次以及所耗时间为285ms。

优化代码：public class BubbleSort {
       public static void main(String []args) {
           //测试时间顺序        int arr[]=new int[10000];        Random r = new Random();        //给数组元素赋值        for(int i = 0;i
   
     1) {
                   int lastChange = 1; // 记录最后一次交换位置                for (int j = 1; j < i; j++) {
                       // 前面比后面大，则进行交换                    if (arr[j] > arr[j + 1]) {
                           arr[j] = arr[j] + arr[j + 1];                        arr[j + 1] = arr[j] - arr[j + 1];                        arr[j] = arr[j] - arr[j + 1];                        lastChange = j; // 每交换一次更新一次                    }                    count++;                }                i = lastChange;            }            System.out.println(count);        }    }
   

-可以清楚的看到在测试数据量为10000时，优化后的冒泡排序所需的次数为49944191次以及所耗时间为189ms。

转载地址：https://blog.csdn.net/yzl109zj125/article/details/117001048 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！