算法基础 - 冒泡排序

算法基础 - 冒泡排序

引用

CSDN

1.

https://m.blog.csdn.net/limeigui/article/details/144958597

冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。重复进行直到没有再需要交换的元素，这意味着数列已经排序完成。冒泡排序法采用不停地交换彼此位置来实现，故而形象地称之为冒泡。大致一个气泡从水底一直冒到水面。

原理演示

1. 循环两个变量：外层（轮数）、内层每轮的次数；
2. 总轮数=元素长度-1=最大下标
3. 每轮次数=元素长度-1-轮数=最大下标-轮数；
4. 轮数（++），次数（++）；
5. 两两交换，大的放后面

示例一

一小段排序程序如下：

1. 外层循环：主要是用来轮询
2. 内层循环：主要用来交换位置（前提是满足if条件）
3. 外层循环的停止条件 i < len 这应该能理解，内层循环的停止条件 j < len -i -1 来说明一下： 首先 len - 1 这个为什么要减掉 1， 因为下面 if 中有使用 buf [j+1]， 所以这里要减掉1，不然 buf [j+1] 就会发生越界行为（超出了数组最大数组下标），接着看 len-i，为什么又要减掉 i 呢？因为内层循环每完成一次，最大那个值（或最小那个值），就已经交换到了最后的位置，所以下次交换的时候我们就要减少一次交换已经排序好的元素，依次类推，所以就有 len - i 这样的条件，最后合起来就是 j < len - i - 1 了。

以下是冒泡排序的C++实现：

#include <iostream>
using namespace std;

void bubbleSort(int arr[], int n) 
{
    int cnt = 0;
    for (int i = 0; i < n - 1; i++) 
    {
        // 设定一个标记，判断本次遍历是否进行了交换
        bool swapped = false;
    
        // 最后的元素是在上一轮遍历中已经冒到最后的，所以不需要再比较
        for (int j = 0; j < n - i - 1; j++) 
        {
            if (arr[j] > arr[j + 1]) 
            {
                // 交换
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                
                // 表示进行了交换
                swapped = true;
            }
        }
        
        // 如果这一轮没有交换，意味着数组已经排序好了
        if (swapped == false)
            break;
            
        ++cnt;
        
    }
           
    cout << "一共执行了：" << cnt << endl;
    
}

void printArray(int arr[], int size) 
{
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() 
{
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    bubbleSort(arr, n);
    cout << "Sorted array: \n";
    printArray(arr, n);
    return 0;
}

执行结果：

一共执行了：14
Sorted array: 
11 12 22 25 34 64 99