1. 基础思想

1.遍历前N-1个元素，每个元素和后一个元素做比较，若比后面的元素大，则交换这两个元素
2.第一次执行1后，最多的元素出现在最后，然后再重复执行1，只是遍历的元素依次为前N-2,N-3,...,1

这是一种稳定的排序算法。
稳定是指，两个相等的数，在排序过后，相对位置保持不变。

2. 复杂度

平均时间复杂度： $O (n^{2})$
最坏时间复杂度： $O (n^{2})$
空间复杂度： $O (1)$

3. 代码

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    void bubble_sort(vector<int>& nums) {
        for (int i = 1; i < nums.size(); ++i) {
            for (int j = 0; j < nums.size() - i; ++j) {
                if (nums[j] > nums[j + 1]) {
                    swap(j, j + 1, nums);
                }
            }
        }
    }

private:
    void swap(int i, int j, vector<int> & nums) {
        if (i == j) {
            return;
        }
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
};
int main() {
    vector<int> nums = {3, 4, 1, 2, 5};
    Solution a;
    a.bubble_sort(nums);
	for (int i = 0; i < nums.size(); ++i) {
	    cout << nums[i] << endl;
	}
    return 0;
}

4. 参考链接

通俗：https://zh.wikipedia.org/wiki/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F
权威：https://en.wikipedia.org/wiki/Bubble_sort

5. 冒泡排序改进

5.1 鸡尾酒排序或双向冒泡排序

5.1.1 改进点：

1.标记当前轮次的排序是否没有交换过元素（此优化更双向无关，单向就可以了）
2.双向冒泡排序，如果一个很小的元素在末尾，可以很快的把它排到第1位，减少交换次数

排序算法是稳定的

5.1.2 复杂度

平均时间复杂度： $O (n^{2})$
最坏时间复杂度： $O (n^{2})$
空间复杂度： $O (1)$

5.1.3 代码

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
	void cocktail_sort(vector<int>& nums) {
		bool is_swap = true;
		int left = 0;
		int right = nums.size() - 1;
		while (left < right && is_swap == true) {
		    bool is_swap = false;
			for (int j = left; j < right; ++j) {
			    if (nums[j] > nums[j + 1]) {
				    swap(j, j + 1, nums);
					is_swap = true;
				}
			}
			--right;
			for (int j = right; j > left; --j) {
			    if (nums[j] < nums[j - 1]) {
				    swap(j, j - 1, nums);
					is_swap = true;
				}
			}
			++left;
		}
	}

private:
    void swap(int i, int j, vector<int> & nums) {
        if (i == j) {
            return;
        }
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
};
int main()
{
    vector<int> nums = {3, 4, 1, 2, 5};
    Solution a;
    a.cocktail_sort(nums);
	for (int i = 0; i < nums.size(); ++i) {
	    cout << nums[i] << endl;
	}
    return 0;
}

5.1.4 参考链接

权威：https://en.wikipedia.org/wiki/Cocktail_shaker_sort
通俗：https://zh.wikipedia.org/wiki/%E9%B8%A1%E5%B0%BE%E9%85%92%E6%8E%92%E5%BA%8F

5.2 梳排序

5.2.1 改进点

1.不在比较相邻元素，转而比较间隔为gap的元素，且gap初始值为(N-1)/1.3,且是以一定的速率（速率取1.3性能比较优）降低的，即：int((N-1)/1.3), int((N-1)/1.3/1.3), int((N-1)/1.3/1.3/1.3), ..., 直到1
2.当gap=1时，退化为冒泡排序，保证了算法准确性

该排序算法不稳定

5.2.2 复杂度

最坏时间复杂度： $O (n^{2})$
平均时间复杂度： $O (n^{2} / 2^{p})$ ，其中 $p$ 为达到最好排序所需的外层循环数量
最好时间复杂度： $O (n l o g (n))$
空间复杂度： $O (1)$
证明过程：比较复杂：参考：https://cstheory.stackexchange.com/questions/9619/analysis-of-comb-sort，https://homepages.cwi.nl/~paulv/papers/sorting.pdf

5.2.3 代码

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
	void comb_sort(vector<int> & nums) {
	    float ratio = 1.3;
		bool sorted = false;
		int gap = nums.size() - 1;
		while (!sorted) {
			gap = max(int(gap / ratio), 1);
		    if (gap == 1) {
			    sorted = true;
			}
			for (int i = 0; i < nums.size() - gap; ++i) {
			    if (nums[i] > nums[i + gap]) {
				    swap(i, i + gap, nums);
					sorted = false;
				}
			}
		}
	}

private:
    void swap(int i, int j, vector<int> & nums) {
        if (i == j) {
            return;
        }
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
};
int main() {
    vector<int> nums = {3, 4, 1, 2, 5};
    Solution a;
    a.comb_sort(nums);
	for (int i = 0; i < nums.size(); ++i) {
	    cout << nums[i] << endl;
	}
    return 0;
}

5.2.4 参考链接

权威：https://en.wikipedia.org/wiki/Comb_sort
通俗：https://zh.wikipedia.org/zh-cn/%E6%A2%B3%E6%8E%92%E5%BA%8F
复杂度说明：https://cstheory.stackexchange.com/questions/9619/analysis-of-comb-sort，https://homepages.cwi.nl/~paulv/papers/sorting.pdf