【最基础最直观的排序 —— 冒泡排序算法】

最基础最直观的排序 —— 冒泡排序算法

冒泡排序（Bubble Sort）是一种计算机科学领域的较简单的排序算法，属于交换排序。其基本思想是在待排序的一组数中，将相邻的两个数进行比较，若前面的数比后面的数大就交换两数，否则不交换；如此下去，直至最终完成排序。

在冒泡排序中以升序为例，算法将待排序的 n 个数中相邻两个数进行比较，将较大的数交换到后面的一个位置上。重复这一操作，直到处理完本轮数列中最后两个元素，称为一轮排序。
当一轮排序完成时，最大的数就被轮换到本轮排序数列最右端位置上。重复上面的过程，经过 n - 1 轮后，就实现了数据升序排序。冒泡排序是一种稳定排序算法，即如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变。

以下是各种语言的冒泡排序代码示例：

• C 语言：

void bubble_sort(int* src,int length)//整数数组的排序
{
    int i =0,j = 0;
    int tmp = 0;
    /* 入参检查 */
    if(NULL == src || length <=0)
    {
        printf("(Error):Func:%s input...");
    }
    for (i = 0; i < length - 1; i++)
    {
        for (j = 0; j < length - i - 1; j++)
        {
            if(src[j]>src[j+1])
            {
                tmp = src[j];
                src[j] = src[j+1];
                src[j+1] = tmp;
            }
        }
    }
}

• JavaScript：

//冒泡排序的排序过程是简单直观的，主要的执行步骤：
//1. 比较未排序序列中的相邻元素，如果两者的顺序不正确，则对两个元素进行交换；
//2. 重复地对剩余未排序的元素执行上一步，直至完成排序；
var bubbleSort = function (nums) {
    const n = nums.length;
    // 控制执行轮数
    for (let i = 0; i < n - 1; i++) {
        // 当次的所...
        for (let j = 0; j < n - i - 1; j++) {
            if (nums[j]> nums[j + 1]) {
                // 交换相邻元素的位置
                let temp = nums[j];
                nums[j]= nums[j + 1];
                nums[j + 1]= temp;
            }
        }
    }
    return nums;
}

• Java：

public class BubbleSort{
    public static void bubbleSort(int[] array){
        int n = array.length;
        for(int i =0; i < n -1; i++){
            for(int j =0; j < n - i -1; j++){
                if(array[j]> array[j +1]){
                    // 交换相邻元素的位置
                    int temp = array[j];
                    array[j]= array[j +1];
                    array[j +1]= temp;
                }
            }
        }
    }
    public static void main(String[] args){
        int[] array ={64,34,25,12,22,11,90};
        bubbleSort(array);
        System.out.println("排序后的数组：");
        for(int i : array){
            System.out.print(i +" ");
        }
    }
}

综上所述，冒泡排序算法虽然简单，但在一些小规模数据的排序场景中仍然有其应用价值。

冒泡排序算法的基本思想

冒泡排序是一种简单的排序算法，其基本思想是重复地走访要排序的数列，一次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。具体来说，从数列的第一个元素开始，依次比较相邻的两个元素，若前面的元素比后面的元素大，则交换它们的位置。这样一轮比较下来，最大的元素就会“冒泡”到数列的末尾。接着，对剩余的未排序部分重复上述过程，直到整个数列都有序为止。

例如，对于数列[5, 3, 8, 2, 7]，首先比较5和3，因为5大于3，所以交换它们的位置，数列变为[3, 5, 8, 2, 7]。接着比较5和8，不交换，再比较8和2，交换位置，数列变为[3, 5, 2, 8, 7]。最后比较8和7，交换位置，第一轮结束后数列变为[3, 5, 2, 7, 8]。然后对[3, 5, 2, 7]进行第二轮比较，以此类推，直到整个数列有序。

冒泡排序的优点是实现简单，容易理解，对于小规模数据的排序比较方便。但其缺点也很明显，时间复杂度较高，在最坏情况下，即待排序的元素已经按照逆序排列时，需要进行 n - 1 轮比较和交换操作，每轮需要进行 n - i 次比较和交换操作，其中 n 是待排序数组的元素数量，i 是当前轮数。因此，最坏情况下的时间复杂度为 O(n²)。

冒泡排序算法的稳定性

冒泡排序是一种稳定的排序算法。所谓稳定性，是指在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变。

在冒泡排序中，如果两个元素相等，是不会进行交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换。所以相同元素的前后顺序并没有改变，这就保证了冒泡排序的稳定性。

例如，对于数列[5, 3, 5’, 2, 7]，其中5’表示另一个值为5的元素。在冒泡排序过程中，当比较到5和5’时，由于它们相等，不会进行交换。这样，在排序后的数列中，5和5’的相对位置与原数列保持一致。

冒泡排序算法的时间复杂度

冒泡排序的时间复杂度在最坏情况下为 O(n²)，其中 n 为待排序的元素个数。在最坏情况下，即待排序的元素已经按照逆序排列，需要进行 n - 1 轮比较和交换操作，每轮需要进行 n - i 次比较和交换操作，因此总的时间复杂度为 O(n²)。

在最好情况下，即已经排好序的数组，时间复杂度为 O(n)，因为只需要进行一轮比较就可以确定已经排好序。

平均情况下，时间复杂度也为 O(n²)，因为平均需要进行 n/2 轮比较，每轮比较需要进行 n/2 次交换。

例如，对于一个包含 10 个元素的数组，在最坏情况下，第一轮需要比较 9 次，第二轮需要比较 8 次……以此类推，总共需要比较的次数为 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45 次，接近 n²/2 的值。

冒泡排序算法的应用场景

冒泡排序适用于一些特定的场景：

1. 数据规模较小：当数据规模较小时，冒泡排序的运行时间可能与其他更快的排序算法相差无几，或者甚至更快。例如，对包含几十个元素的数组进行排序。
2. 数据已经接近有序：如果待排序的数据已经基本有序，冒泡排序的时间复杂度可以降低到 O(n)。比如，在一些数据处理过程中，已经经过了初步的整理，数据大部分已经有序，此时使用冒泡排序可以快速完成排序。
3. 内存限制：冒泡排序是一种原地排序算法，它只需要在原始数组上进行交换操作，因此不需要额外的内存空间。这在内存受限的情况下可能会是一个优点。

但是，在大多数情况下，对于大规模数据集，更高效的排序算法如快速排序、归并排序等可能更适合使用。

C 语言冒泡排序代码示例

以下是用 C 语言实现冒泡排序的代码示例：

void bubble_sort(int arr[], int len) {
    int i, j, temp;
    for (i = 0; i < len - 1; i++) {
        for (j = 0; j < len - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

这段代码中，外层循环控制排序的轮数，内层循环对未排序的部分进行相邻元素的比较和交换。如果前面的元素大于后面的元素，就交换它们的位置，使较大的元素“冒泡”到后面。

JavaScript 冒泡排序代码示例

以下是用 JavaScript 实现的冒泡排序代码示例：

function bubbleSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}

这段代码中，外层循环控制趟数，里层循环控制每一趟的循环次数。通过比较相邻的两个元素，如果顺序错误就进行交换，最终实现数组的排序。

Java 冒泡排序代码示例

以下是用 Java 实现的冒泡排序代码示例：

public class BubbleSort {
    public static void bubbleSort(int[] array) {
        int n = array.length;
        boolean swapped;
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            for (int j = 0; j < n - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    swapped = true;
                }
            }
            if (!swapped) {
                break;
            }
        }
    }
}

这段代码中，外层循环控制趟数，通过设置一个标志位 swapped，如果在一趟排序中没有发生交换，说明数组已经有序，可以提前退出循环，提高效率。

总结

冒泡排序算法虽然简单易懂，但时间复杂度较高，适用于数据规模较小、数据接近有序或内存受限的场景。在实际应用中，应根据具体情况选择合适的排序算法。