Java 数据结构 - 冒泡排序

排序是指以特定格式排列数据。排序算法指定以特定顺序排列数据的方式。最常见的顺序是数值顺序或字典顺序。

排序的重要性在于，如果数据以排序方式存储，则数据搜索可以被优化到非常高的水平。排序还用于以更易读的格式表示数据。以下是现实生活中排序的一些示例。

• 电话簿 - 电话簿按姓名对人员的电话号码进行排序存储，以便可以轻松搜索姓名。

• 字典 - 字典按字母顺序存储单词，以便于搜索任何单词。

原地排序和非原地排序

排序算法可能需要一些额外的空间来比较和临时存储一些数据元素。这些算法不需要任何额外的空间，排序据说发生在原地，或者例如，在数组本身内。这称为原地排序。冒泡排序就是一个原地排序的例子。

但是，在某些排序算法中，程序需要的空间大于或等于正在排序的元素。使用等于或更多空间的排序称为非原地排序。归并排序就是一个非原地排序的例子。

Java 中的冒泡排序

冒泡排序是一种简单的排序算法。这种排序算法是一种基于比较的算法，其中比较每对相邻元素，如果不按顺序则交换元素。该算法不适用于大型数据集，因为其平均和最坏情况的复杂度为 Ο(n2)，其中 n 是项目数。

算法

我们假设list是一个包含n个元素的数组。我们进一步假设swap()函数交换给定数组元素的值。

Step 1: Assume i is the first element of the list then, compare the elements i and i+1. (first two elements of the array)
Step 2: If the i (first element) is greater than the second (i+1) swap them.
Step 3: Now, increment the i value and repeat the same.(for 2nd and 3rd elements) 
Step 4: Repeat this till the end of the array.

示例

import java.util.Arrays;
public class BubbleSort {
   public static void main(String args[]) {
      int[] myArray = {10, 20, 65, 96, 56};      
      System.out.println("Contents of the array before sorting : ");
      System.out.println(Arrays.toString(myArray));
      
      int n = myArray.length;
      int temp = 0;
      
      for(int i = 0; i<n-1; i++) {
         for(int j = 0; j<n-1; j++) {
            if (myArray[j] > myArray[j+1]) {
               temp = myArray[i];
               myArray[j] = myArray[j+1];
               myArray[j+1] = temp;
            }
         }         
      }           
      System.out.println("Contents of the array after sorting : ");
      System.out.println(Arrays.toString(myArray));       
   }
}

输出

Contents of the array before sorting : 
[10, 20, 65, 96, 56]
Contents of the array after sorting : 
[10, 10, 20, 10, 20]