冒泡排序

基本思想

冒泡排序显然是稳定的排序算法。
假设最终结果是递增有序。使用两层循环，内层循环每轮从头到尾比较相邻数字并交换；外层循环确保最大的数最多能被交换n-1次到末尾。

C/C++实现

# include <iostream>
# include <vector>

using namespace std;

class Solution {
public:
    void swap(int &a, int &b) {
        int temp = a;
        a = b;
        b = temp;
    }

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

int main() {
    vector<int> a = {3, 2, 1, 5, 4};
    Solution s;
    s.bubble_sort(a);
    for (int i : a)
        cout << i << " ";
    cout << endl;
    return 0;
}

Python3实现

class Solution(object):
    def bubble_sort(self, nums):
        n = len(nums)
        for i in range(0, n - 1):
            for j in range(1, n):
                if nums[j - 1] > nums[j]:
                    nums[j - 1], nums[j] = nums[j], nums[j - 1]


a = [2, 1, 3, 4, 7, 5, 4, 6]
s = Solution()
s.bubble_sort(a)
print(a)