C++实现冒泡排序
原创
冒泡排序介绍
冒泡排序是一种简单的排序算法，原理如下：
- 从待排序的数组的第一个元素开始，依次比较相邻的两个元素。
- 如果前面的元素大于后面的元素，则交换这两个元素的位置，使较大的元素向后移动。
- 继续比较下一对相邻元素，重复上述步骤，直到遍历到数组的倒数第二个元素。
- 一轮比较完成后，最大的元素会被交换到数组的末尾。
- 对除了已排序的最后一个元素外的剩余元素，重复以上步骤，直到整个数组排序完成。
通过不断地比较和交换相邻元素，较大的元素会逐渐“冒泡”到数组的末尾，因此称为冒泡排序。
冒泡排序的空间复杂度为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 循环。外层循环用于控制比较和交换的次数，内层循环则用于进行相邻元素的比较和交换。我们通过比较相邻元素的大小，如果前面的元素大于后面的元素，则将它们交换位置。
涉及基础知识点
- 头文件引用：#include <iostream> 表示引入了iostream标准库，使得可以使用cout进行输出操作。
- 命名空间：using namespace std; 表示使用std命名空间，这样可以直接使用cout而不需要写成std::cout。
- 函数定义和函数参数传递：void bubbleSort(int arr[], int n) 定义了一个名为bubbleSort的函数，接受一个整型数组和数组长度作为参数。
- 循环结构：使用了for循环来进行数组元素的比较和交换操作。
- 数组操作：定义了一个整型数组arr，并通过sizeof(arr)/sizeof(arr[0])计算数组的长度。
- 输出语句：使用cout语句进行屏幕输出。
- 函数调用：在主函数中通过调用bubbleSort(arr, n)来调用定义的冒泡排序函数。
- 返回值：主函数中使用return 0;表示程序正常结束。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录