冒泡排序 Bubble Sort
原理
冒泡排序(Bubble Sort)是一种简单的排序算法,其核心思想是通过相邻元素的比较和交换,把较大的元素逐渐“冒泡”到序列的末尾,从而完成排序。
其具体步骤如下:
- 比较相邻的元素,如果前一个比后一个大,就交换它们的位置。
- 每一轮遍历完成后,当前未排序部分中最大的元素会被放到末尾。
- 重复上述步骤,对未排序部分继续进行比较和交换,直到整个序列有序。
示例
有一组无序数组:
6 | 2 | 4 | 1 |
---|
从头开始依次比较,6
比2
大,6
与2
交换。
此时数组为:
4 | 1 |
---|
顺次比较,6
比4
大,6
与4
交换。
此时数组为:
2 | 1 |
---|
顺次比较,6
比1
大,6
与1
交换。
第一轮比较结束,此时数组为:
2 | 4 |
---|
从头开始依次比较,2
比4
小,不交换。
此时数组为:
1 | 6 |
---|
顺次比较,4
比1
大,4
与1
交换。
第二轮比较结束,此时数组为:
2 | 6 |
---|
最终比较,2
比1
小,2
与1
交换。
此时数组为:
4 | 6 |
---|
排序完成。
实现
C++
cpp
#include <iostream>
#include <vector>
using namespace std;
std::vector<int> BubbleSort(std::vector<int> besortedArray);
std::vector<int> myArray = { 6, 2, 4, 1, 9, 0, 3, 10, 15 };
int main()
{
std::vector<int> testArray = BubbleSort(myArray);
//输出:0 1 2 3 4 6 9 10 15
for (int i = 0; i < testArray.size(); i++) {
cout << testArray[i] << " ";
}
return 0;
}
//冒泡排序
std::vector<int> BubbleSort(std::vector<int> besortedArray)
{
int length = besortedArray.size();
for (int i = 0; i < length - 1; i++)
{
for (int j = 0; j < length - i - 1; j++)
{
if (besortedArray[j] > besortedArray[j + 1]) {
int t = besortedArray[j];
besortedArray[j] = besortedArray[j + 1];
besortedArray[j + 1] = t;
}
}
}
return besortedArray;
}
可视化
数组长度
动画间隔
数组:
[]