冒泡排序Java

如果您听说过编程中的排序方法，很可能是冒泡排序算法。这是一个著名的。每个程序员都知道冒泡排序（或者至少在学习时听说过）并不是因为它是世界上最好的排序算法，而是因为它是最简单的算法。该算法通常用于学习目的，或者您可以在 Java 初级面试中将其作为一项任务。Java 冒泡排序算法很容易理解，但是它不是一个高效的算法。无论如何，让我们弄清楚。

什么是排序

首先，你需要明白排序一般是什么，我们在Java程序中可以排序什么。如果我们可以通过它们的任何属性比较两个或多个元素或对象，则意味着它们可以按该属性进行排序。例如，按升序或降序排列的数字或按字母顺序排列的单词。因此，元素必须相互比较。顺便问一下，什么元素？在Java中，我们可以比较Collections的元素。例如，我们可以对整数、字符串等的 Array 或 ArrayList 进行排序。

冒泡排序是如何工作的

比方说，我们需要对一个整数数组进行升序排序，即从小到大。首先，我们遍历整个数组并比较每 2 个相邻元素。如果它们的顺序错误（左边的邻居比右边的大），我们交换它们。在最后的第一次传递中，它会出现最大的元素（如果我们按升序排序）。你可能会说，最大的元素“弹出”。这就是冒泡排序算法名称的原因。我们从第一个元素到倒数第二个元素重复第一步。我们在倒数第二个位置找到了第二大元素。等等。我们可以通过检查上一步是否至少进行了一次交换来稍微改进算法。如果不是，我们将停止沿着阵列运行。

冒泡排序示例

让我们对整数数组进行排序，您可能会在下面的图片中看到它。 第 1 步：我们正在遍历数组。该算法从前两个元素（索引为 0 和 1）、8 和 7 开始，并检查它们的顺序是否正确。显然，8 > 7，所以我们交换它们。接下来，我们查看第二个和第三个元素（索引 1 和 2），现在它们是 8 和 1。出于同样的原因，我们交换它们。我们第三次比较 8 和 2，至少比较 8 和 5。我们总共进行了四次交换：(8, 7)、(8, 1)、(8, 2) 和 (8, 5)。值 8，此数组中最大的值，在列表末尾弹出到正确位置。 冒泡排序算法第一步工作的结果是下一个数组： 第 2 步。对 (7,1)、(7,2) 和 (7,5) 执行相同的操作。7 现在处于倒数第二的位置，我们不需要将它与列表的“尾巴”进行比较，它已经排好序了。 冒泡排序算法第二步运行的结果是下一个数组： 如您所见，该数组已经排序。无论如何，冒泡排序算法应该至少再运行一次。第三步。我们再次遍历数组。这里没有什么可交换的，所以如果我们使用“改进的”冒泡排序算法（检查上一步是否至少进行了一次交换），这一步就是最后一步。

冒泡排序Java代码

冒泡排序Java实现

让我们为冒泡排序创建两个方法。第一个，bubbleSort(int[] myArray)是平面的。它每次都遍历数组。第二个，optimizedBubbleSort(int myArray[])通过在内部循环没有引起任何交换的情况下停止算法来优化。计数器显示您在排序时执行了多少步。这里我们有冒泡排序 Java 实现：

import java.util.Arrays;

public class BubbleSortExample {

   //  Plane Bubble sort example

   public static int[] bubbleSort(int[] myArray) {

       int temp = 0;  //  temporary element for swapping
       int counter = 0;  //  element to count quantity of steps

       for (int i = 0; i < myArray.length; i++) {
           counter = i + 1;
           for (int j = 1; j < (myArray.length - i); j++) {

               if (myArray[j - 1] > myArray[j]) {
                   //  swap array’s elements using temporary element
                   temp = myArray[j - 1];
                   myArray[j - 1] = myArray[j];
                   myArray[j] = temp;
               }
           }
       }
       System.out.println("Steps quantity, non optimized = " + counter);
       return myArray;
   }
   //  An optimized version of Java Bubble Sorting

   static int[] optimizedBubbleSort(int myArray[]) {
       int temp;
       boolean swapped;
       int counter = 0;  //  element to count quantity of steps
       for (int i = 0; i < myArray.length - 1; i++) {
           counter = i + 1;
           swapped = false;
           for (int j = 0; j < myArray.length - i - 1; j++) {
               //  counter++;
               if (myArray[j] > myArray[j + 1]) {
                   //  swap arr[j] and arr[j+1]
                   temp = myArray[j];
                   myArray[j] = myArray[j + 1];
                   myArray[j + 1] = temp;
                   swapped = true;

               }
           }  //  counter = i;
           //  If there weren't elements to swap in inner loop, then break
           if (swapped == false) {

               break;

           }
       }
       System.out.println("steps quantity, optimized = " + counter);
       return myArray;
   }


   public static void main(String[] args) {
       int arr[] = {8, 7, 1, 2, 5};
       int arr1[] = {8, 7, 1, 2, 5};

       System.out.println("Array arr Before Bubble Sort");
       //  we use java.util.Arrays toString method to print the array  
 System.out.println(Arrays.toString(arr));

       System.out.println("Array arr After Bubble Sort");
       System.out.println(Arrays.toString(bubbleSort(arr)));

       System.out.println("Array arr1 Before Bubble Sort");
       System.out.println(Arrays.toString(arr1));

       System.out.println("Array arr1 After Optimized Bubble Sort");
       System.out.println(Arrays.toString(optimizedBubbleSort(arr1)));
   }
}

冒泡排序Java算法工作的结果：

Array arr Before Bubble Sort
[8, 7, 1, 2, 5]
Array arr After Bubble Sort
Steps quantity, non optimized = 5
[1, 2, 5, 7, 8]
Array arr1 Before Bubble Sort
[8, 7, 1, 2, 5]
Array arr1 After Optimized Bubble Sort
steps quantity, optimized = 3
[1, 2, 5, 7, 8]

冒泡排序的效率如何？

冒泡排序是最容易实现的算法之一，但效率不高。它需要一对嵌套循环。即使在最坏情况下（数据集的每个元素与所需元素的顺序相反）的优化版本的算法中，外循环也会为数据集的 n 个元素中的每一个元素迭代一次。内部循环第一次迭代n 次，第二次迭代 ( n -1 )，依此类推。因此，要对所有n元素进行排序，需要执行循环n*(n-1)/2次。它调用O(n ² )时间复杂度，意味着该算法对数组的 1000 个元素进行大约 500 000 次比较。然而，冒泡排序算法在内存使用方面非常有效（内存复杂度为O(n)）并且对于几乎已排序的小型数据集非常有用。