排序算法 - 冒泡排序

一、冒泡排序的基本思想

冒泡排序（Bubble Sort）是一种简单直观的排序算法。它的原理是重复地走访要排序的数列，一次比较两个相邻元素，如果它们的顺序不是预期的顺序就交换它们。这个过程持续进行，直到没有再需要交换，也就是说该数列已经排序完成。

二、实例讲解

第四轮过后，将第四大的元素位置确定，此时总共5个元素，已经排序好4个，从而最后一个自然而然就是排好序的了

三、算法步骤总结

设总的元素个数为n，那么由上边的排序过程可以看出：

（1）总计需要进行（n-1）轮排序，也就是（n-1）次大循环

（2）每轮排序比较的次数逐轮减少

（3）如果发现在某趟排序中，没有发生一次交换， 可以提前结束冒泡排序。（详见下边优化部分）

四、代码实现

#include <stdio.h>

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

int main() {
    int arr[] = {
        22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70
    };
    int len = sizeof(arr) / sizeof(arr[0]);
    bubble_sort(arr, len);
    for (int i = 0; i < len; i++){
        printf("%d ", arr[i]);
    }
    return 0;
}

五、算法优化

通过上边讲解的例子，我们也可以看出从第二轮过后，其实数组已经是有序的了，但是按照算法步骤来走的话，即使已经排好序了，但仍是会进行后边的比较，知道全部比较完成。

因此，我们可以对代码进行优化，如果发现在某趟排序中，没有发生一次交换， 可以提前结束冒泡排序。

解决方式：可以通过一个标志位来进行判断

下面是优化后的代码：

#include <stdio.h>

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

int main() {
    int arr[] = {
        22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70
    };
    int len = sizeof(arr) / sizeof(arr[0]);
    bubble_sort(arr, len);
    for (int i = 0; i < len; i++){
        printf("%d ", arr[i]);
    }
    return 0;
}