C++ 冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <vector>
using namespace std;

void BubbleSort(vector<int>& vec);
void Print(const vector<int>& vec);

int main()
{
vector<int> vec = { 49, 38, 65, 97, 76, 13, 27, 49 };
cout << "before sort:" << endl;
Print(vec);
cout << "sort:" << endl;
BubbleSort(vec);
cout << "after sort:" << endl;
Print(vec);
}

void BubbleSort(vector<int>& vec)
{
int length = vec.size();
bool flag = true; //flag用来标记某一趟排序是否发生交换
for( int i = 0; i < length - 1; i++ )
{
flag = false; //flag置为false,如果本趟排序没有发生交换,则不会执行下一趟排序
for( int j = 0; j < length - 1 - i; j++ )
{
if( vec[j] > vec[j + 1] )
{
int temp = vec[j];
vec[j] = vec[j + 1];
vec[j + 1] = temp;
flag = true; //flag置为true,表示本趟排序发生了交换
}
}
Print(vec);
if( flag == false ) break;
}
}

void Print(const vector<int>& vec)
{
for( int v : vec )
{
cout << v << " ";
}
cout << endl;
}

原本8个元素应该进行7趟排序,因为加入了flag,最后进行了6趟,第6趟发现没有进行任何元素的交换,说明已经有序,退出排序。

作者

DullSword

发布于

2021-11-26

更新于

2024-11-05

许可协议

评论