【排序】详解冒泡排序

一、思想

冒泡排序的基本思想是利用两两比较相邻记录的方式，通过一系列的比较和交换操作，使得较大或较小的元素逐渐移动到数列的一端。在每一轮的排序过程中，都会从数列的起始位置开始，对相邻的元素进行比较，如果它们的顺序不符合要求（例如，前一个元素大于后一个元素），则交换它们的位置。这样，每轮遍历后，至少会有一个元素被移动到其最终位置。重复这个过程，直到没有任何一对元素需要交换位置，即整个数组变为有序。

冒泡排序的过程可以形象地比喻为水中的气泡上升过程，较小的元素逐渐“冒”到数列的顶端，而较大的元素则沉到底部。这个过程就像是在水中的气泡一样，不断向上冒出，直到所有的气泡都排好序。

冒泡排序的时间复杂度为O(n^2)，这使得它在处理大规模数据时效率不高。尽管如此，由于其实现简单，对于小规模数据集或者基本有序的数组，冒泡排序仍然是一个不错的选择。

二、图解

i指针控制次数，j指针每次遍历时进行两两比较，j每遍历一遍都会将一个最大的数排好序

依次重复上述步骤，直到j遍历完n-1遍。如果一个数组本来就是有序或者经过小于n-1次就已经排好了序，那么j指针后续的遍历就是徒劳，所以我们可以根据j指针在遍历过程中是否有交换进行判断，如果没有交换说明已经排好序，这个时候就可直接返回

三、代码实现

void bubble_sort(vector<int>& arr) {
    for (int i = 0; i < arr.size(); i++) {
        bool f = false;
        for (int j = 0; j < arr.size() - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                f = true;
            }
        }
        if (!f) return;
    }
}

    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            boolean f = true;
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    f = false;
                    swap(arr, j, j + 1);
                }
            }
            if (f) {
                break;
            }
        }
    }