def bubble_sort(alist):
"""冒泡排序"""
n = len(alist)
for i in range(n-1): #外层循环次数
for j in range(n-1-i): #这里 记得要 -i
if alist[j] > alist[j+1]:
alist[j], alist[j + 1] = alist[j+1], alist[j]
def bubble_sort_2(alist): #优化
"""冒泡排序"""
n = len(alist)
for i in range(n-1): #外层循环次数
count = 0
for j in range(n-1-i): #这里 记得要 -i
if alist[j] > alist[j+1]:
alist[j], alist[j + 1] = alist[j+1], alist[j]
count += 1
if 0 == count:
return
''' 原理： 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，
再从剩余未排序元素中继续寻找最小（大）元素
，然后放到已排序序列的末尾， 以此循环'''
def select_sort(alist):
"""选择排序"""
n = len(alist)
for i in range(n - 1): # 外层循环次数
min_ind = i
for j in range(i+1,n):
if alist[min_ind] > alist[j]:
min_ind = j
#找到最小值索引，下面进行交换,这样i每变化一次就确定一个数的位置了
#alist[i], alist[min_ind] = alist[min_ind], alist[i] #推荐用下面的
if i != min_ind:
alist[i], alist[min_ind] = alist[min_ind], alist[i]
#理解其思想: i从1开始，i为无序序列 中的第一个元素索引，i-1为有序序列 中的第最后一个元素索引
def insert_sort(alist):
"""插入排序"""
n = len(alist)
#从第二个位置，即下标为i的元素开始向前插入
for i in range(1, n):
#从第i个元素开始向前比较，如果小于前一个元素，交换位置
for j in range(i, 0, -1):
if alist[j] < alist[j-1]:
alist[j], alist[j - 1] = alist[j - 1], alist[j]
# 如果不小于的化，就可以退出本次循环， 因为i-1为有序序列的最后一个元素索引，所以前面都是有序的
else:
break
'''思想:快排是一种分而治之的策略,快排的工作过程其实比较简单，三步走：:
1) 选择基准值 pivot 将数组分成两个子数组：小于基准值的元素和大于基准值的元素。
2) 对这两个子数组进行快速排序。
3) 合并结果
'''
def quick_sort_v1(alist):
if len(alist)<2: #递归结束条件
return alist
#用分治法解决
pivot = alist[0] #假设数组的第一个元素为pivot
less_pivot = [i for i in alist[1:] if i <=pivot]
more_pivot = [i for i in alist[1:] if i > pivot]
return quick_sort_v1(less_pivot) + [pivot] + quick_sort_v1(more_pivot)
#总结：
#第一是它需要额外的存储空间，不是inplace 原地排序。
#第二是它的 partition 操作每次都要两次遍历整个数组
def quick_sort(alist, start, end):
"""快速排序"""
if start >= end: # 递归结束条件
return
pivot = alist[start] # 假设基准值
low = start
high = end
while (low < high):
# 必须 high先左移
while (low < high) and alist[high] >= pivot:
high =high -1
alist[low] = alist[high] # 改变low的值
while (low < high) and alist[low] < pivot:
low =low + 1
alist[high] = alist[low] # 改变high的值
# 从循环退出时，low==high, 这样就找到了pivot应该在的位置
alist[low] = pivot
# 对low左边的列表执行快速排序
quick_sort(alist, start, low - 1)
# 对low右边的列表排序
quick_sort(alist, low + 1, end)
'''归并排序把数组递归成只有单个元素的数组，之后再不断两两 合并，最后得到一个有序数组。
1)分解：将待排序的 n 个元素分成各包含 n//2 个元素的子序列
2)解决：使用归并排序递归排序两个子序列
3)合并：合并两个已经排序的子序列以产生已排序的答案
'''
def merge(left_li,right_li):
res = [] #新的已排序好的列表
i, j =0, 0
#对2个列表中的元素 两两对比，将较小的追加到res中，并对当前列表下标加1
while( i<len(left_li) and j<len(right_li) ):
if left_li[i] <= right_li[j]:
res.append(left_li[i])
i += 1
else:
res.append(right_li[j])
j += 1
#退出循环后 至少有1个列表遍历完了
res += left_li[i:] #a = [1,2,3] ---> a[3:] ---> []
res += right_li[j:]
return res
def merge_sort(alist):
"""归并排序"""
n = len(alist)
if n < 2 :
return alist
mid = n // 2
# left 采用归并排序后形成的有序的新的列表
left_li = merge_sort(alist[:mid])
# right 采用归并排序后形成的有序的新的列表
right_li = merge_sort(alist[mid:])
#d对排序好的两个列表合并，产生一个新的排序好的列表
return merge(left_li, right_li)
转播
