数据结构——排序与查找（3）——冒泡排序（C++实现）_c++冒泡排序法代码数据结构

交换排序算法

所谓交换，意思是说根据所给的序列，对其中的两个元素进行大小比较，若为逆序，那么我们就交换它。这样就达到了排序的目的。接下来介绍最简单的交换排序——冒泡排序。

冒泡排序的原理

冒泡排序的原理很简单，它反复遍历要排序的列表，比较每对相邻的项目，如果它们的顺序错误则交换它们。 重复遍历列表，直到不需要交换，这表示列表已排序。我们可以从后往前（或者从前往后）两两比较相邻的元素，若为逆序，则交换他们。（这跟插入排序不同，插入排序一开始是局部排序，也就是说一开始排完的数字的位置，有可能下次排序的时候还会变动，而冒泡排序是全局排序，一旦位置排好就是固定位置）。
举个例子来说说冒泡排序的步骤：
假设我们对 5 1 4 2 8 这一组数据进行排序，那么第一趟的过程如下：

如果这个时候我们将图倒过来看，就会发现5就像从底下往上冒的水泡，这也是为什么这个算法称为冒泡排序的原因。
好，接下来我们看看第二趟会发生什么：

那么我们对5排完之后，应该对谁排序呢？当然是对 1 了，因为我们是遍历要排序的序列的，得按顺序来。于是发现1比后面的都小，于是不用交换，保留原地不动。（这个时候就注意了，1是不动没错，那么就意味着它真的不动？当然不是，它还是得跟其他元素遍历比较，否则我怎么知道它比其他的元素都要小？所以这是一种对时间资源的浪费）。
排完之后，对4排序，重复第一步的算法，如图所示；
排完之后，对2排序，（实际上这个时候，我们的排序已经完成，但是对于算法来说它并不知道此时的序列已经处于有序状态，因此它依旧执行比较操作，依旧执行遍历，直到所有要排序的元素都已经处于有序状态）
下面贴一个动态图（来自维基百科），直观的描述这一过程：

冒泡排序的C++实现

下面我们用C++语言来写一下这个算法

#include <iostream>
#include <vector>
using namespace std;
/*函数声明*/
void bubbleSort(vector<int> &vec);
void swap(int &i, int &j);
/*主函数*/
int main() {
	vector<int> vec;
	cout << "请输入待排序的序列" << endl;
	//假设我们对5个数进行排序
	for (int i = 0; i < 5; i++) {
		int n;
		cin >> n;
		vec.push_back(n);
	}
	
	bubbleSort(vec);//使用希尔排序对vector进行排序
	//输出结果
	cout << "冒泡排序后：" << endl;
	for (int k = 0; k < vec.size(); k++) {
		cout << vec[k] << " ";
	}
	return 0;
}
//冒泡排序的实现，由小到大
void bubbleSort(vector<int> &vec) {
	//遍历序列中的每个元素
	for (int i = 0; i < vec.size() - 1; i++) {
		bool IsSwap = false; //设立是否交换的标记
		for (int j = vec.size() - 1; j > i; j--) { //一趟排序
			if (vec[j - 1] > vec[j]) { //后面的大于左边的大于右边的数,交换
				swap(vec[j - 1], vec[j]);
				IsSwap = true;//交换标记为true
			}
		}
		//当交换标记为flase的时候，意味着本次遍历没有发生交换，跳出循环
		if (IsSwap = false) return;
	}

}
//交换两个数的函数
void swap(int &i, int &j) {
	int temp = j;
	j = i;
	i = temp;
}
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

复杂度分析

显然这种做法造成了极大的时间浪费，做了很多不必要的操作。考虑极端的情况，当被排数列有序的时候，要进行n - 1次比较。（最后一次不用比较，因为已经排好）。当为逆序的时候，进行N-1次排序，并且，第I趟要进行N-I次比较，复杂度为O（n^2）.
另外一种用的最广泛的交换排序，叫快速排序，我之前写过我就不再赘述了，链接贴上：C++抽象编程——算法分析（6）——快速排序算法