经典算法之一的冒泡排序，相信程序员小伙伴们都会遇到，无论哪种后端语言开发都会遇到面试算法必备题之一，今天我们就来讲下冒泡排序。

冒泡排序是一种简单的排序算法，它通过重复地遍历要排序的数列，比较相邻的两个元素，如果它们的顺序错误就交换它们的位置。这个过程会重复进行直到没有需要交换的元素为止，也就是说该数列已经排序完成。

时间复杂度

冒泡排序的时间复杂度为 O(n^2)，其中 n 是数组的长度。这是因为在最坏的情况下，每个元素都需要与其他所有元素进行比较和可能的交换。

排序原理举例

假设我们有一个数组 [64, 34, 25, 12, 22, 11, 90]，我们需要对它进行升序排序。

• 第一次遍历：[34, 25, 12, 22, 11, 64, 90]（64 被移动到最后）
• 第二次遍历：[25, 12, 22, 11, 34, 64, 90]（34 被移动到倒数第二）
• 第三次遍历：[12, 22, 11, 25, 34, 64, 90]（25 被移动到倒数第三）
• 第四次遍历：[12, 11, 22, 25, 34, 64, 90]（22 被移动到倒数第四）
• 第五次遍历：[11, 12, 22, 25, 34, 64, 90]（12 被移动到倒数第五）
• 第六次遍历：[11, 12, 22, 25, 34, 64, 90]（11 被移动到倒数第六）

经过以上步骤，数组已经完全排序。

Python 示例代码

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

# 测试代码
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = bubble_sort(arr)
print("Sorted array is:", sorted_arr)

PHP 示例代码

function bubbleSort(&$arr) {
    $n = count($arr);
    for ($i = 0; $i < $n; $i++) {
        for ($j = 0; $j < $n - $i - 1; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                // 交换元素
                $temp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $temp;
            }
        }
    }
}

// 测试代码
$arr = array(64, 34, 25, 12, 22, 11, 90);
bubbleSort($arr);
echo "Sorted array is: ";
print_r($arr);

Java 示例代码

public class BubbleSort {
    void bubbleSort(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n-1; i++) {
            for (int j = 0; j < n-i-1; j++) {
                if (arr[j] > arr[j+1]) {
                    // 交换 arr[j+1] 和 arr[j]
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }

    // 测试代码
    public static void main(String args[]) {
        BubbleSort ob = new BubbleSort();
        int arr[] = {64, 34, 25, 12, 22, 11, 90};
        ob.bubbleSort(arr);
        System.out.println("Sorted array");
        for (int i=0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}