目录
冒泡排序
冒泡排序（英语：Bubble Sort）是一种简单的排序算法。从未排序序列中的第一个元素开始，比较相邻的两个元素，如果第一个比第二个大，则交换它们的位置，一直比较到最后一个元素，针对所有的元素重复以上的步骤，除了最后一个。
动图演示：
?代码实现：
def bubble_sort(alist):
for j in range(len(alist) - 1, 0, -1):
# j表示每次遍历需要比较的次数，是逐渐减小的
for i in range(j):
if alist[i] > alist[i + 1]:
alist[i], alist[i + 1] = alist[i + 1], alist[i]
li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
bubble_sort(li)
print(li)
选择排序
选择排序（Selection sort）是一种简单直观的排序算法。从未排序序列中，找到最小的元素放在序列的第一位，接着再从剩下的序列中找到最小的放在第二位，直到所有元素排序完毕。
动图演示：
红色表示当前最小值，黄色表示已排序序列，蓝色表示当前位置。
?代码实现：
def selection_sort(alist):
n = len(alist)
# 需要进行n-1次选择操作
for i in range(n-1):
# 记录最小位置
min_index = i
# 从i+1位置到末尾选择出最小数据
for j in range(i+1, n):
if alist[j] < alist[min_index]:
min_index = j
# 如果选择出的数据不在正确位置，进行交换
if min_index != i:
alist[i], alist[min_index] = alist[min_index], alist[i]
alist = [54,226,93,17,77,31,44,55,20]
selection_sort(alist)
print(alist)插入排序
插入排序（英语：Insertion Sort），通过构建有序序列，对于未排序数据，在已排序序列中依次比较，若小，则交换位置，找到相应位置并插入。
动图演示
?代码实现
def insert_sort(alist):
# 从第二个位置，即下标为1的元素开始向前插入
for i in range(1, len(alist)):
# 从第i个元素开始向前比较，如果小于前一个元素，交换位置
for j in range(i, 0, -1):
if alist[j] < alist[j - 1]:
alist[j], alist[j - 1] = alist[j - 1], alist[j]
alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
insert_sort(alist)
print(alist)
快速排序
快速排序的原理：从序列中选择一个基数，比它小的放在左边，比它大的放在右边，递归地将左右边再一次进行数列排序。
过程分析：
?代码实现
def quick_sort(alist, start, end):
"""快速排序"""
# 递归的退出条件
if start >= end:
return
# 设定起始元素为要寻找位置的基准元素
mid_value = alist[start]
# low为序列左边的由左向右移动的游标
low = start
# high为序列右边的由右向左移动的游标
high = end
while low < high:
# 如果low与high未重合，high指向的元素不比基准元素小，则high向左移动
while low < high and alist[high] >= mid_value:
high -= 1
# 将high指向的元素放到low的位置上
alist[low] = alist[high]
# 如果low与high未重合，low指向的元素比基准元素小，则low向右移动
while low < high and alist[low] < mid_value:
low += 1
# 将low指向的元素放到high的位置上
alist[high] = alist[low]
# 退出循环后，low与high重合，此时所指位置为基准元素的正确位置
# 将基准元素放到该位置
alist[low] = mid_value
# 对基准元素左边的子序列进行快速排序
quick_sort(alist, start, low - 1)
# 对基准元素右边的子序列进行快速排序
quick_sort(alist, low + 1, end)
alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
quick_sort(alist, 0, len(alist) - 1)
print(alist)
希尔排序
希尔排序(Shell Sort)是插入排序的一种。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序。
假设有这样一个数组：[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]? 长度为16，我们可以取步长为5，则可以分成如下几组
第一组：13 14 94 33 82
第二组：25 59 94 65 23
第三组：45 27 73 25 39
第四组：10
分完组后，进行简单的插入排序，则：
第一组的13 和第二组的25比较，排序 13 25
第三组的45 和 13 25进行排序 结果：13 25 45
第四组的10 和 13 25 45 排序 结果： 10 13 25 45
接着是第一组的14 和第二组的59排序，依次进行后。。
我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]
然后再以步长为3进行排序，最后以步长为1进行排序，则完成排序代码实现
def shell_sort(alist):
n = len(alist)
# 初始步长
gap = n // 2
while gap > 0:
# 按步长进行插入排序
for i in range(gap, n):
j = i
# 插入排序
while j >= gap and alist[j - gap] > alist[j]:
alist[j - gap], alist[j] = alist[j], alist[j - gap]
j -= gap
# 得到新的步长
gap = gap // 2
alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
shell_sort(alist)
print(alist)
归并排序
归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。
动图演示
代码实现?
def merge_sort(alist):
if len(alist) <= 1:
return alist
# 二分分解
num = len(alist) // 2
left = merge_sort(alist[:num])
right = merge_sort(alist[num:])
# 合并
return merge(left, right)
def merge(left, right):
'''合并操作，将两个有序数组left[]和right[]合并成一个大的有序数组'''
# left与right的下标指针
l, r = 0, 0
result = []
while l < len(left) and r < len(right):
if left[l] < right[r]:
result.append(left[l])
l += 1
else:
result.append(right[r])
r += 1
result += left[l:]
result += right[r:]
return result
alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
sorted_alist = merge_sort(alist)
print(sorted_alist)
常见排序算法效率比较
?