文章目录
今日份鸡汤：你战胜了苦难，它就是你的财富；
苦难战胜了你，它就是你的屈辱。
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 冒泡排序的稳定性分析
- 冒泡排序属于稳定排序。
- 分析：在冒泡排序中，每次比较两个元素，当元素的大小顺序错误时才会进行交换。如果元素列表中有两个相等的元素，它们最后肯定会相邻在一起，但在进行比较时，并不是顺序错误的情况，所以对它们比较时不会进行交换，相对次序是保持不变的。因此，冒泡排序是一种稳定的排序算法。