01.Array-Bubble-Sort.md

1. 冒泡排序算法思想

冒泡排序（Bubble Sort）基本思想：

第 i (i = 1，2，… ) 趟排序时从序列中前 n - i + 1 个元素的第 1 个元素开始，相邻两个元素进行比较，若前者大于后者，两者交换位置，否则不交换。

冒泡排序法是通过相邻元素之间的比较与交换，使值较小的元素逐步从后面移到前面，值较大的元素从前面移到后面，就像水底的气泡一样向上冒，故称这种排序方法为冒泡排序法。

2. 冒泡排序算法步骤

• 先将序列中第 1 个元素与第 2 个元素进行比较，若前者大于后者，则两者交换位置，否则不交换；
• 然后将第 2 个元素与第 3 个元素比较，若前者大于后者，则两者交换位置，否则不交换；
• 依次类推，直到第 n - 1 个元素与第 n 个元素比较（或交换）为止。经过如此一趟排序，使得 n 个元素中值最大元素被安置在序列的第 n 个位置上。
• 此后，再对前 n - 1 个元素进行同样过程，使得该 n - 1 个元素中值最大元素被安置在第 n - 1 个位置上。
• 然后再对前 n - 2 个元素重复上述过程，直到某一趟排序过程中不出现元素交换位置的动作，排序结束。

3. 冒泡排序动画演示

4. 冒泡排序算法分析

• 最好的情况下，初始时序列已经是从小到大有序（升序），则只需经过一趟 n - 1 次元素之间的比较，并且不移动元素，算法就可结束排序。此时，算法的时间复杂度为 $O(n)$。
• 最差的情况是当参加排序的初始序列为逆序，或者最小值元素处在序列的最后时，则需要进行 n - 1 趟排序，总共进行 $∑^n_{i=2}(i−1) = \frac{n(n−1)}{2}$ 次元素之间的比较，因此，冒泡排序算法的平均时间复杂度为 $O(n^2)$。
• 冒泡排序方法在排序过程中需要移动较多次数的元素。因此，冒泡排序方法比较适合于参加排序序列的数据量较小的情况，尤其是当序列的初始状态为基本有序的情况；而对于一般情况，这种方法是排序时间效率最低的一种方法。
• 由于元素交换是在相邻元素之间进行的，不会改变值相同元素的相对位置，因此，冒泡排序法是一种 稳定排序法。

5. 冒泡排序代码实现

class Solution:
    def bubbleSort(self, arr):
        for i in range(len(arr)):
            for j in range(len(arr) - i - 1):
                if arr[j] > arr[j + 1]:
                    arr[j], arr[j + 1] = arr[j + 1], arr[j]

        return arr

    def sortArray(self, nums: List[int]) -> List[int]:
        return self.bubbleSort(nums)