01
冒泡排序
基本思想：循环比较两个数，大的数下沉，小的数上浮，所以叫冒泡
步骤：
- 比较相邻两个数的大小，如果第二个数小就交换位置
- 从前往后依次比较，每一轮最后一组比较完成后，最大数会被排在末尾
- 重复上述过程。
图解:
def bubbleSort(arr):
count = 0
for i in range(0, len(arr) - 1):
for j in range(0, len(arr) - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
count = count + 1
print("循环比较次数：{0}".format(count))
return arr
arr = [1, 2, 3, 4, 5, 7, 6]
print(bubbleSort(arr))
循环比较次数：21
[1, 2, 3, 4, 5, 6, 7]
平均时间复杂度：O(n²)
空间复杂度：O(1)，比较和交换数据，仅需要一个辅助存储空间
稳定性：冒泡排序是稳定算法，“6 7 6 2 8” 排序后两个“6”的相对位置不变
优化：
冒泡排序一定会进行arr.length-1次的循环比较，但一旦数据已经排好序，之后的比较是没意义的，因此我们设置标志位，跳过无意义的比较，优化算法。
def bubbleSort(arr):
count = 0
for i in range(0, len(arr) - 1):
flag = False # 标志位：未完成排序
for j in range(0, len(arr) - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
flag = True # 已完成排序
count = count + 1
if not flag:
break
print("循环比较次数：{0}".format(count))
return arr
arr = [1, 2, 3, 4, 5, 7, 6]
print(bubbleSort(arr)) 输出结果：
循环比较次数：6
[1, 2, 3, 4, 5, 6, 7]
02
选择排序
基本思想：每次找出最小的数，排到队头，直到排序完成
步骤：
- 首先从未排序数列中找到最小数，排到队头
- 从剩余数列这个继续找最小的数，排到队头
- 重复，直到所有的元素均排列完毕
图解:
def selectionSort(arr):
for i in range(0, len(arr) - 1):
min = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[min]:
min = j
if i != min:
arr[i], arr[min] = arr[min], arr[i]
return arr
arr = [3, 6, 2, 4, 2, 13, 9, 21, 11]
print(selectionSort(arr)) 输出结果：
[2, 2, 3, 4, 6, 9, 11, 13, 21]
平均时间复杂度：O(n²)
空间复杂度：O(1)，比较和交换数据，仅需要一个辅助存储空间
稳定性：选择排序是不稳定算法，“6 7 6 2 8” 在第一次排序时，会将第一个位置的6和之后的2调换位置，此时两个6的相对位置已经改变。
03
插入排序
基本思想：会打扑克就会插入排序
步骤：
把数组第一个元素视为有序数列，将剩下的元素插入到有序数列。
图解:
def insertionSort(arr):
# 从数组第二个元素开始插入
for i in range(1, len(arr)):
current = arr[i] # 要插入的元素
preIndex = i - 1 # 从相邻的开始比较
while preIndex >= 0 and arr[preIndex] > current:
arr[preIndex + 1] = arr[preIndex]
preIndex = preIndex - 1 # 指针前进一格
arr[preIndex + 1] = current # 完成当前元素的插入
return arr
arr = [3, 6, 2, 4, 2, 13, 9, 21, 11]
print(insertionSort(arr)) 输出结果：
[2, 2, 3, 4, 6, 9, 11, 13, 21]
平均时间复杂度：O(n²)
空间复杂度：O(1)，比较交换数据，仅需要一个辅助存储空间
稳定性：插入排序是稳定算法，“6 7 6 2 8” 是相邻比较，排序后两个“6”的相对位置不变
04
总结
| 排序算法 | 平均时间复杂度 | 空间复杂度 | 稳定性 |
| 冒泡排序 | O(n²) | O(1) | 稳定 |
| 选择排序 | O(n²) | O(1) | 不稳定 |
| 插入排序 | O(n²) | O(1) | 稳定 |