冒泡排序

简介：首先介绍冒泡排序的方法，然后介绍一些优化方法，给出普通版本和优化版本的代码。最后在对冒泡排序进行分析（时间、空间复杂度、稳定性、是否为原地算法）

方法：

从头开始比较每一对相邻元素，如果第一个元素比第二个大，就交换它们的位置；执行完一轮后，可以将未排序的最大元素上浮至右侧忽略步骤1中曾经找到的最大元素，重复执行步骤1，直到全部元素有序。

优化：

第一种优化（常用）：如果序列完全有序，可以提前终止冒泡排序。用一个标志位来标识。但是未必效率高，因为提前有序的概率较低，但是整体代码却比普通版多了三个操作，所以效率未必会提升。

第二种优化：如果序列尾部已经局部有序，这一部分是不用参加比较和交换的。我们可以记录最后一次交换的位置。第二种优化要比第一种优化的概率高，因为序列尾部部分有序的概率比序列完全有序的概率高。

 

普通版代码：

#include <iostream> #include <vector> using namespace std; void BubbleSort(vector<int>& nums) { int N = nums.size(); bool isSorted = false; for (int i = N - 1; i > 0; --i) { for (int j = 1; j <= i; ++j) { if (nums[j - 1] > nums[j]) { int tmp = nums[j]; nums[j] = nums[j - 1]; nums[j - 1] = tmp; } } } } int main() { vector<int> test = { 5, 8, 4, 9, 2 }; BubbleSort(test); for (auto a : test) cout << a << " "; }

优化1版本代码

#include <iostream> #include <vector> using namespace std; void BubbleSort1(vector<int>& nums) { int N = nums.size(); bool isSorted = false; //标志位 for (int i = N - 1; i > 0 && isSorted == false; --i) { isSorted = true; //假定已经有序 for (int j = 1; j <= i; ++j) { if (nums[j - 1] > nums[j]) { isSorted = false; //进入循环，进行交换，所以不能说明数组已经有序，还要进行循环 int tmp = nums[j]; nums[j] = nums[j - 1]; nums[j - 1] = tmp; } } } } int main() { vector<int> test = { 5, 8, 4, 9, 2 }; BubbleSort(test); for (auto a : test) cout << a << " "; }

优化2版本代码

#include <iostream> #include <vector> using namespace std; void BubbleSort2(vector<int>& nums) { int N = nums.size(); bool isSorted = false; for (int i = N - 1; i > 0; --i) { //sortedIndex的初始值在数组完全有序的时候有用，这时进行一轮扫描 int sortedIndex = 1; for (int j = 1; j <= i; ++j) { if (nums[j - 1] > nums[j]) { int tmp = nums[j]; nums[j] = nums[j - 1]; nums[j - 1] = tmp; sortedIndex = j; //sortedIndex会在最后一轮循环记录下最后一次交换的位置 } } i = sortedIndex; } } int main() { vector<int> test = { 5, 8, 4, 9, 2 }; BubbleSort(test); for (auto a : test) cout << a << " "; }

分析：

时间复杂度：最好O（n）,最坏O（n * n）,平均O（n * n）。

稳定性：稳定（只有左边元素大于右边才交换）。

原地算法：是。