【第七天 - Bubble Sort 题目分析】

先简单回顾一下，今天预计分析的题目：

如何利用 Bubble sort 进行排序?

1. 我们要将下图六个数字进行从小到大的排序
   • 
2. 我们现在要把最大的放到最後一个位置(第六个位置)，所以我们会比较六个数字，两两做比较，逐渐将最大值向後移
   • 
3. 我们现在要把第二大的放到第五个位置，所以我们会比较剩下的五个数字，两两做比较，逐渐将最二大值向後移
   • 
4. 我们现在要把第三大的放到第四个位置，所以我们会比较剩下的四个数字，两两做比较，逐渐将第三大值向後移，以此类推，直到将全部的数字排列完成
   • 
5. 我们就会发现有N个数字
   • 我们就要比较 N-1 轮，才能把全部数字排列完
   • 我们要把数字放到正确的第 j 个位置，我们就会比较剩下的 j 个数字
6. 最终排序过程如下
   • 
     (动画来源於 https://pjchender.blogspot.com/2017/09/bubble-sort.html )

• python 实作 bubble sort 如下

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
#       若有 N 个数字要排序，则要执行 N-1 轮
        for i in range(len(nums)-1,0,-1):
#           每次比较会从 0 ~ i-1 个做比较，每次会把最大的数字丢到最後面 
            for j in range(i):
#               若第 j 笔资料 大於 第 j+1 笔资料，则两两交换
                if nums[j] > nums[j+1]:
                    t = nums[j]
                    nums[j] = nums[j+1]
                    nums[j+1] = t
        return nums

• 不过你可以看见，Bubble Sort 基本上需要两个回圈执行，才能排序完成，加上需要不断交换位置，才能将数字排序到正确的位置，在面对多笔资料需要排序的情况下，Bubble Sort 排序效率太低，当资料量变多，便容易造成 Time Limit Exceeded 的情况
• 由於 Bubble Sort 过程容易理解与实作，是排序的基本算法，也是面试常考的算法之一，故在此系列文章提出来做介绍
• 明天我们将介绍 Quick Sort，能够减少排序时间，并且解决 912. Sort an Array 题目