57 lines
1.7 KiB
C++
57 lines
1.7 KiB
C++
|
/**
|
||
|
|
* File: bubble_sort.cpp
|
||
|
|
* Created Time: 2022-11-25
|
||
|
|
* Author: krahets (krahets@163.com)
|
||
|
|
*/
|
||
|
|
|
||
|
|
#include "../utils/common.hpp"
|
||
|
|
|
||
|
|
/* 冒泡排序 */
|
||
|
|
void bubbleSort(vector<int> &nums) {
|
||
|
|
// 外循环：未排序区间为 [0, i]
|
||
|
|
for (int i = nums.size() - 1; i > 0; i--) {
|
||
|
|
// 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
|
||
|
|
for (int j = 0; j < i; j++) {
|
||
|
|
if (nums[j] > nums[j + 1]) {
|
||
|
|
// 交换 nums[j] 与 nums[j + 1]
|
||
|
|
// 这里使用了 std::swap() 函数
|
||
|
|
swap(nums[j], nums[j + 1]);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
/* 冒泡排序（标志优化）*/
|
||
|
|
void bubbleSortWithFlag(vector<int> &nums) {
|
||
|
|
// 外循环：未排序区间为 [0, i]
|
||
|
|
for (int i = nums.size() - 1; i > 0; i--) {
|
||
|
|
bool flag = false; // 初始化标志位
|
||
|
|
// 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
|
||
|
|
for (int j = 0; j < i; j++) {
|
||
|
|
if (nums[j] > nums[j + 1]) {
|
||
|
|
// 交换 nums[j] 与 nums[j + 1]
|
||
|
|
// 这里使用了 std::swap() 函数
|
||
|
|
swap(nums[j], nums[j + 1]);
|
||
|
|
flag = true; // 记录交换元素
|
||
|
|
}
|
||
|
|
}
|
||
|
|
if (!flag)
|
||
|
|
break; // 此轮“冒泡”未交换任何元素，直接跳出
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
/* Driver Code */
|
||
|
|
int main() {
|
||
|
|
vector<int> nums = {4, 1, 3, 1, 5, 2};
|
||
|
|
bubbleSort(nums);
|
||
|
|
cout << "冒泡排序完成后 nums = ";
|
||
|
|
printVector(nums);
|
||
|
|
|
||
|
|
vector<int> nums1 = {4, 1, 3, 1, 5, 2};
|
||
|
|
bubbleSortWithFlag(nums1);
|
||
|
|
cout << "冒泡排序完成后 nums1 = ";
|
||
|
|
printVector(nums1);
|
||
|
|
|
||
|
|
return 0;
|
||
|
|
}
|