一、排序算法的稳定性
1. 概念
例如：如果订单默认按照时间排序，需要按照金额排序，就要保证相同金额的订单原来的时间顺序不会变化；
2. 不稳定排序
(不相邻两数比较) 选择 快速 希尔 堆
3. 稳定排序
(相邻两数依次比较) 冒泡 插入 归并 基数
4. 衡量标准
- 时间复杂度：最好/最坏
- 空间复杂度：原地排序（O(1)）
5. 排序算法总结
二、冒泡排序
1. 定义
2. 动画演示：
3. 代码实现
def bubble_sort(l):
n = len(l)
# 外层循环控制轮数
for i in range(n-1):
count = 0
# 内层循环控制每轮比较的次数
for j in range(n-1-i):
if l[j] > l[j+1]:
count += 1
l[j], l[j+1] = l[j+1], l[j]
print(l)
bubble_sort([6,5,4,3,2,1])
4.效率分析
- 时间复杂度
- 最好：O(n)
- 最坏：O(n2)
-
稳定性：稳定算法
- 空间复杂度：O(1), 为原地排序
三、选择排序
1. 定义
2. 动画演示：
3. 代码实现
def select_sort(l):
n = len(l)
# 第一层循环控制迭代轮数
for i in range(0, n-1):
mix_index = i
# 第二层循环控制比较次数
for j in range(i+1, n):
if l[mix_index] > l[j]:
mix_index = j
if mix_index != i:
l[mix_index], l[i] = l[i], l[mix_index]
print(l)
select_sort([1,2,3,6,5,4])
4. 效率分析
- 时间复杂度： 最好O(n2) 最坏O(n2)
- 稳定性：不稳定算法，例如5 8 5 2（因算法而异）
- 空间复杂度：O(1), 为原地排序
三、插入排序
1. 定义
2. 动画演示：
3. 代码实现
def insert_sort(l):
n = len(l)
# 第一层循环控制轮数
for i in range(1, n):
# 第二层循环控制每一轮比较次数
for j in range(i, 0, -1):
if l[j] < l[j-1]:
l[j], l[j-1] = l[j-1], l[j]
else:
break
print(l)
insert_sort([6,5,4,3,2,1])
4. 效率分析
- 时间复杂度：最好 O(n) 最坏 O(n2)
- 空间复杂度：O(1)
- 稳定性：稳定
四、快速排序
1. 定义
2. 动画演示
3. 代码实现
def quick_sort(l, start, end):
left = start
right = end
if end <= start:
return
mid = l[start]
while start < end:
while l[end] >= mid and start < end:
end -= 1
l[start] = l[end]
while l[start] < mid and start < end:
start += 1
l[end] = l[start]
l[start] = mid
quick_sort(l, left, start-1)
quick_sort(l, start + 1, right)
l = [1,2,3,6,5,4,3,3,3]
quick_sort(l, 0, len(l)-1)
print(l)
4. 效率分析
- 时间复杂度：
- 最差 O(n2)
- 最好 O(nlogn)
- 最差 O(n2)
-
算法稳定性：不稳定
- 空间复杂度：O(1) 原地排序
