今日份鸡汤：你战胜了苦难，它就是你的财富；
      苦难战胜了你，它就是你的屈辱。

0. 排序算法介绍

  排序算法是数据结构中最基本的算法，也是最经典的算法之一。
  排序算法有多种分类方法，如：内部排序和外部排序、比较排序和非比较排序、稳定排序和非稳定排序等。

0.1 内部排序和外部排序

• 内部排序和外部排序：
  （1）内部排序：内部排序是数据记录在内存中进行排序。
  （2）外部排序：外部排序因为排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。
• 按照内部排序和外部排序进行分类：
  （1）内部排序：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序。
  （2）外部排序：

0.2 比较排序和非比较排序

• 比较排序和非比较排序：
  （1）比较排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
  （2）非比较排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
• 按比较排序和非比较排序进行分类：
  （1）比较排序：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。
  （2）非比较排序：计数排序，基数排序，桶排序等。

0.3 稳定排序和非稳定排序

• 稳定排序和非稳定排序
    排序算法的稳定性是：当元素列表中出现相等的元素时，相等元素的相对次序是否固定不变。如果相对次序固定不变，则排序算法是稳定的，反之就是不稳定的。
• 按照稳定排序和非稳定排序进行分类：
  （1）稳定排序：冒泡排序，
  （2）非稳定排序：
  
  

1. 冒泡排序

1.1 冒泡排序的思想

  冒泡排序的思想就是：从第一个数开始，两两进行比较，逆序时交换。经过一趟比较之后，最大的数会被交换到最后，即最大的数会沉底，类似于最大的水泡在池子最底层（反之，从大到小排序也是一样的原理）。然后接着对前n-1个记录重复上述过程，直到排序完毕，类似于冒泡过程。
  注意：在某趟排序的比较中，如果发现两两比较无一交换，则说明数组已经有序。

1.2 冒泡排序的算法步骤

（1）以从小到大排序为例：从第1个元素和第二个元素开始，比较相邻的两个元素，如果前一个比后一个大，就互相调换位置，否则保持原状。
（2）第2个元素与第3个元素比较，如果第2个元素比第3个元素大，就互相调换位置，否则保持原状。
（3）对每一对相邻的元素，重复上述“比较”与“交换”的过程，直到最后一对元素。此时最大的数字已经被交换到了最后，也就是说，最大的泡泡已经冒出来啦。
（注意哦，此时最大的泡泡已经冒出来了，就不需要参与下一步的比较与交换的排序过程了，下一步的任务是：让次大的泡泡冒出来。）
（4）同理，针对所有的元素（除了最大的数字不参与）开始进行第二轮的比较与交换的排序过程，找出次大的泡泡。
（5）持续每次对越来越少的元素重复上面的步骤，直到排序完成（没有任何一对数字需要比较）。
（6）注意：在某趟排序的过程中，如果发现两两比较没有一个需要交换的元素，这说明整个排列已经有序，不必进行到最后一轮剩下两个元素进行比较。


     从上图中就可以看出：冒泡排序属于稳定排序。

1.3 冒泡排序的代码

# coding:utf-8
'''
# @Method：冒泡排序
# @Author: wlhr62
'''
import os
import sys


class Solution:
    def BubbleSort(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        n = len(nums)
        for i in range(n):
            for j in range(0, n-i-1):
                if nums[j] > nums[j+1]:
                    # temp = nums[j]
                    # nums[j] = nums[j+1]
                    # nums[j+1] = temp
                    nums[j], nums[j+1] = nums[j+1], nums[j]
            print("第", i+1, "轮的排序结果：", nums)
        return nums
        

if __name__ == "__main__":
    nums = [50, 36, 66, 76, 95, 12, 25, 36]
    A = Solution()
    res = A.BubbleSort(nums)
    print("最后的排序结果：", res)
    

代码运行结果如下：

第 1 轮的排序结果： [36, 50, 66, 76, 12, 25, 36, 95]
第 2 轮的排序结果： [36, 50, 66, 12, 25, 36, 76, 95]
第 3 轮的排序结果： [36, 50, 12, 25, 36, 66, 76, 95]
第 4 轮的排序结果： [36, 12, 25, 36, 50, 66, 76, 95]
第 5 轮的排序结果： [12, 25, 36, 36, 50, 66, 76, 95]
第 6 轮的排序结果： [12, 25, 36, 36, 50, 66, 76, 95]
第 7 轮的排序结果： [12, 25, 36, 36, 50, 66, 76, 95]
第 8 轮的排序结果： [12, 25, 36, 36, 50, 66, 76, 95]
最后的排序结果： [12, 25, 36, 36, 50, 66, 76, 95]

存在的问题：
  到这里大家就已经看出问题了，从第6轮开始就已经没有需要交换的元素了，后面又多比较了两轮。
  不要忘记上面一开始就说过的注意事项：在某趟排序的比较中，如果发现两两比较无一交换，则说明数组已经有序。

修改代码如下：
  增加一个标记变量，用来判断本轮排序过程中有无交换。如果没有，则直接结束排序过程。

# coding:utf-8
'''
# @Method：冒泡排序
# @Author: wlhr62
'''
import os
import sys


class Solution:
    def BubbleSort(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        n = len(nums)
        for i in range(n):
            changeNum = 0  # 加入一个变量，用于判断本轮排序过程中有无交换
            for j in range(0, n-i-1):
                if nums[j] > nums[j+1]:
                    nums[j], nums[j+1] = nums[j+1], nums[j]
                    changeNum += 1
            print("第", i+1, "轮的排序结果：", nums)
            # 如果发现两两比较无一交换，则说明数组已经有序
            if changeNum == 0:
                break
        return nums
        

if __name__ == "__main__":
    nums = [50, 36, 66, 76, 95, 12, 25, 36]
    A = Solution()
    res = A.BubbleSort(nums)
    print("最后的排序结果：", res)
    

修改代码后的运行结果如下：

第 1 轮的排序结果： [36, 50, 66, 76, 12, 25, 36, 95]
第 2 轮的排序结果： [36, 50, 66, 12, 25, 36, 76, 95]
第 3 轮的排序结果： [36, 50, 12, 25, 36, 66, 76, 95]
第 4 轮的排序结果： [36, 12, 25, 36, 50, 66, 76, 95]
第 5 轮的排序结果： [12, 25, 36, 36, 50, 66, 76, 95]
第 6 轮的排序结果： [12, 25, 36, 36, 50, 66, 76, 95]
最后的排序结果： [12, 25, 36, 36, 50, 66, 76, 95]

思考：第6轮的重复是否可以省去？

1.4 冒泡排序的复杂度分析

• 最坏时间复杂度：O(n^2)
• 没有特殊说明时，一般都是计算最坏时间复杂度。
• 冒泡排序中，最坏的情况是：列表的初始状态完全逆序排列。这种情况下，需要进行 n-1 轮冒泡，每一轮冒泡都需要进行 n-i-1 次比较和交换的操作。i 的平均值为 n/2 ，时间复杂度为 n(n-1)/2。
• 最坏情况下，冒泡排序的时间复杂度为 O(n^2) 。
• 最优时间复杂度：O(n)
• 冒泡排序中，最好的情况是：列表的初始状态完全符合预期排列。这种情况下，只需要进行 1 轮冒泡，此过程中没有进行比较和交换的操作。要用一个标记变量来判断本轮排序过程中有无交换。如果没有，则直接结束排序过程。
• 最好情况下，冒泡排序的时间复杂度为 O(n) 。
• 平均时间复杂度：O(n^2)
• 冒泡排序中，平均时间复杂度为 O(n^2) 。
• 空间复杂度：O(1)

1.5 冒泡排序的稳定性分析

• 冒泡排序属于稳定排序。
• 分析：在冒泡排序中，每次比较两个元素，当元素的大小顺序错误时才会进行交换。如果元素列表中有两个相等的元素，它们最后肯定会相邻在一起，但在进行比较时，并不是顺序错误的情况，所以对它们比较时不会进行交换，相对次序是保持不变的。因此，冒泡排序是一种稳定的排序算法。

2. 选择排序

3. 插入排序

4. 希尔排序

5. 归并排序

6. 快速排序

7. 堆排序

8. 计数排序

9. 桶排序

10. 基数排序