冒泡排序
def bubble_sort(alist):
"""
冒泡排序
最坏时间复杂度：O(n2)
稳定性：稳定
"""
n = len(alist)
for i in range(0, n-1):
for j in range(0, n-1-i):
if alist[j] > alist[j+1]:
alist[j], alist[j+1] = alist[j+1], alist[j]
优化:
def bubble_sort(alist):
"""
对冒泡排序的优化
利用count标记,如果某一次循环中没有交换,说明已经排好序了
"""
n = len(alist)
for i in range(0, n-1):
for j in range(0, n-1-i):
if alist[j] > alist[j+1]:
alist[j], alist[j+1] = alist[j+1], alist[j]
选择排序 最优时间复杂度：O(n2) 最坏时间复杂度：O(n2) 稳定性：不稳定（考虑升序每次选择最大的情况） 思路:第一次循环从第一个元素遍历到最后一个元素,挑出最小的放到第一个 第二次循环从第二个元素遍历到最后一个元素,挑出最小的放到第二个
def selection_sort(alist):
n = len(alist)
for i in range(n-1):
# 记录最小的位置
min_index = i
for j in range(i + 1, n):
if alist[i] > alist[j]:
min_index = j
alist[i], alist[min] = alist[min], alist[i]
插入排序
最优时间复杂度：O(n) （升序排列，序列已经处于升序状态）
最坏时间复杂度：O(n2)
稳定性：稳定
def insert_sort(alist):
"""
插入排序:
"""
n = len(alist)
for i in range(1, n):
for j in range(i, 0, -1):
if alist[j] < alist[j-1]:
alist[j], alist[j-1] = alist[j-1], alist[j]
