起泡排序算法

发表于 | 分类于

起泡排序

起泡排序作为排序算法里最基础的算法

从本质来将，起泡排序可以分成两部分：前缀无序序列 和 后缀有序序列

思路和代码实现如下：

其中Bubble函数负责一轮从前到后的扫描交换，返回true代码本轮有逆序对

BubbleSort函数负责调用Bubble函数

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
#include <vector>
#include <iostream>
using namespace std;

vector<int> elem_ = { 3, 5, 8, 6, 7 , 9, 88, 55, 66 };

bool Bubble(size_t lo, size_t hi)
{
	bool sorted = true;
	while (++lo < hi) {
		if (elem_[lo - 1] > elem_[lo]) {
			sorted = false;
			swap(elem_[lo - 1], elem_[lo]);
		}
	}
	return sorted;
}

void BubbleSort(size_t lo, size_t hi)
{
	while (!Bubble(lo, hi--));
}

int main()
{
	cout << "排序前: ";
	for (auto item : elem_) {
		cout << item << " ";
	}
	cout << endl;
	BubbleSort(0, elem_.size());
	cout << "排序后: ";
	for (auto item : elem_) {
		cout << item << " ";
	}
}

运行结果：

1
2
排序前: 3 5 8 6 7 9 88 55 66
排序后: 3 5 6 7 8 9 55 66 88
再改进

上面算法是在基础起泡排序算法上改进了的：通过sorted标记本轮扫描比较是否有逆序对（是否进行了交换），如果上一趟扫描交换过程中不存在逆序对说明序列已经是有序的了，此时可以结束排序算法。

再改进方法：记录上一趟扫描交换过程中的所进行的最后一次交换

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
#include <vector>
#include <iostream>
using namespace std;

std::vector<int> _elem = {3, 100, 5, 200, 8, 7, 99, 88};

size_t BubbleAdvance(size_t lo, size_t hi)
{
    size_t position = lo;
     while(++lo < hi) {
        if (_elem[lo - 1] > _elem[lo]) {
            position = lo;
            std::swap(_elem[lo - 1], _elem[lo]);
        }
    }
    cout << position << endl;
    return position;
}

void BubbleSort(size_t lo, size_t hi)
{
    auto position = BubbleAdvance(lo, hi);
    while (lo < position) {
        position = BubbleAdvance(lo, position);
    }
}

int main()
{
    BubbleSort(0, _elem.size());
    for (auto item : _elem) {
        std::cout << item << " ";
    }
}