C++实现冒泡排序

冒泡排序介绍

冒泡排序是一种简单的排序算法，原理如下：

1. 从待排序的数组的第一个元素开始，依次比较相邻的两个元素。
2. 如果前面的元素大于后面的元素，则交换这两个元素的位置，使较大的元素向后移动。
3. 继续比较下一对相邻元素，重复上述步骤，直到遍历到数组的倒数第二个元素。
4. 一轮比较完成后，最大的元素会被交换到数组的末尾。
5. 对除了已排序的最后一个元素外的剩余元素，重复以上步骤，直到整个数组排序完成。

通过不断地比较和交换相邻元素，较大的元素会逐渐“冒泡”到数组的末尾，因此称为冒泡排序。

冒泡排序的空间复杂度为O(1)，即不需要额外的空间来存储数据。在每一轮比较和交换操作中，只需要使用常数级别的额外空间来存储临时变量。因此，冒泡排序是一种原地排序算法，不会占用额外的内存空间。

伪代码如下：

procedure bubbleSort(A: list of sortable items)
    n = length(A)
    for i = 0 to n-1 do:
        for j = 0 to n-i-2 do:
            if A[j] > A[j+1] then:
                swap(A[j], A[j+1])
            end if
        end for
    end for
end procedure

其中，A表示待排序的数组，n为数组长度。循环变量i和j分别控制外层循环和内层循环的次数。在每一轮内层循环中，比较相邻的两个元素，如果前面的元素大于后面的元素，则交换这两个元素的位置。经过n-1轮的循环之后，整个数组就被排序完成了。

C++具体实现

#include <iostream>
using namespace std;

void bubbleSort(int arr[], int n)
{
    int i, j;
    for (i = 0; i < n-1; i++)
    {
        //每一轮排序比较相邻两个元素，如果顺序不对则交换位置
        for (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;
            }
        }
    }
}

int main()
{
    int arr[] = {5, 2, 8, 4, 7, 1, 3, 6};
    int n = sizeof(arr)/sizeof(arr[0]);

    cout << "Original array: ";
    for (int i=0; i < n; i++)
        cout << arr[i] << " ";

    bubbleSort(arr, n);

    cout << "\nSorted array: ";
    for (int i=0; i < n; i++)
        cout << arr[i] << " ";

    return 0;
}

定义了一个整数数组 arr，包含了待排序的元素。然后我们计算出数组元素的个数 n，并输出它们的初始顺序。接着调用 bubbleSort 函数进行冒泡排序，并最终输出排好序的数组。

在 bubbleSort 函数中，我们使用了两个嵌套的 for 循环。外层循环用于控制比较和交换的次数，内层循环则用于进行相邻元素的比较和交换。我们通过比较相邻元素的大小，如果前面的元素大于后面的元素，则将它们交换位置。

涉及基础知识点

1. 头文件引用：#include <iostream> 表示引入了iostream标准库，使得可以使用cout进行输出操作。
2. 命名空间：using namespace std; 表示使用std命名空间，这样可以直接使用cout而不需要写成std::cout。
3. 函数定义和函数参数传递：void bubbleSort(int arr[], int n) 定义了一个名为bubbleSort的函数，接受一个整型数组和数组长度作为参数。
4. 循环结构：使用了for循环来进行数组元素的比较和交换操作。
5. 数组操作：定义了一个整型数组arr，并通过sizeof(arr)/sizeof(arr[0])计算数组的长度。
6. 输出语句：使用cout语句进行屏幕输出。
7. 函数调用：在主函数中通过调用bubbleSort(arr, n)来调用定义的冒泡排序函数。
8. 返回值：主函数中使用return 0;表示程序正常结束。