本文介绍的排序包括：冒泡，选择，快排，插入，希尔
一、 冒泡排序
冒泡排序：
冒泡排序是基于相邻位置的两两比较，交换位置这个想法来的，每轮有一个数确定最终位置
1.从第一个数开始，第一个数和第二个数比较，如果前一个数大于后一个数，交换两者的位置，否则，不动
2.比较第二个数和第三个数的大小，如果前一个数大于后一个数，交换两者的位置，否则，不动
3.比较第三个和第四个数的大小，如果前一个数大于后一个数，交换两者的位置，否则，不动
……
4.直到倒数的两个数比较和交换完成，至此，完成了第一轮的排序，把最大的数放在了最后一个位置，确定倒数第一个位置的数（下图是一轮的图例）
5.把第一位到倒数第二位的数进行以上步骤，确定倒数第二个位置的数
6.把第一位到倒数第三位的数进行以上步骤，确定倒数第三个位置的数
……
7.直到第一个位置的数确定，完成整个的冒泡排序
def bubble_sort(alist):
end = len(alist)-1
#执行完每轮循环都会少一个数，所以从后开始算
for i in range(end, 0, -1):
for j in range(i):
if alist[j] > alist[j+1]:
#相邻两个数的比较，把大的换到后面
alist[j], alist[j+1] = alist[j+1], alist[j]
else:
continue
return alist
if __name__ == '__main__':
alist = [54,26,93,17,77,31,44,55,20]
res = bubble_sort(alist)
print(res)
二、选择排序
选择排序：
它的原理很简单，遍历（这个实际上是有一个比较过程，遍历的第一个数作为最大的数，不断当前位置的数比较，如果当前的数更大，把它的值给最大的数）数列找到最大的数直接放在它的最终位置
下面用排列成从大到小的数列举例解释：
遍历所有的数，找到最大/小的数放在第一位/最后一位
遍历剩下的数，找到剩下的数里最大/小的数放在第二位/最后二位
……
重复以上步骤
直到最后一个数放在了它最终位置
动图是整个排序的图示过程：
白色表示未排序的数
淡黄色表示已排序好的数
蓝色表示当前遍历的位置
红色表示遍历过程中得到的最小的数
def select_sort(alist):
end = len(alist)
#从大到小排序
for j in range(0, end):
#记录当前（开始的第一个数就是当前时间点的最大值）最大值的index，
max = j
for i in range(end-1, j, -1):
if alist[max] < alist[i]:
#依次和剩余的数进行比较，把更大的数的index给max
max = i
#循环完一次后，把最大的数直接放到最终位置
alist[max], alist[j] = alist[j], alist[max]
return alist
if __name__ == '__main__':
alist = [54, 26, 93, 7, 77, 31, 44, 55, 20]
res = select_sort(alist)
print(res)
三、快速排序
**快速排序：
选择一个数作为基准，一般是选第一位，理论上是任意一位都可以
将剩下的数一次和基准做比较，把比基准大的数放基准右边，小的放左边
文字不太好描述，上图（下图只是一趟排序的示例）。
假设左边从 i 开始，右边从 j 开始，先 j 从右往左开始遍历，遇到比基准小的数，交换位置，j 不动， i 从左往右开始遍历，遇到比基准大的数时，交换位置，i 不动，j 开始从右往左遍历
重复以上，直到 i 、j 相遇，第一趟排序结束
**
#常规写法
def quick_sort(alist, start, end):
#参数错误或者列表为空
if start >= end:
return
i, j = start, end
#选择基准
base = alist[start]
#一趟排序结束的条件，i、j 相遇
while i < j:
#i、j未相遇， j 指向的值比基准更大，j 继续往左遍历
while i < j and base <= alist[j]:
j -= 1
#当遇到比基准大的数，把 j 指向的值给 i 指向的位置
alist[i] = alist[j]
# i、j未相遇， i 指向的值比基准更小，i 继续往右遍历
while i < j and base > alist[i]:
i += 1
# 当遇到比基准小的数，把 i 指向的值给 j 指向的位置
alist[j] = alist[i]
#把基准值给中间的位置
alist[j] = base
#对基准左边进行快排
quick_sort(alist, start, i-1)
#对基准右边进行快排
quick_sort(alist, i+1, end)
if __name__ == '__main__':
alist = [57, 68, 59, 52, 72, 28, 96, 33, 24, 19]
quick_sort(alist, 0, len(alist)-1)
print(alist)
#代码量少，但是会耗费一点的资源（python自己有内存回收机制，所以多创建的列表没有指向时（在这里是程序运行完）会被回收了）
def quick_sort(alist):
if len(alist) < 2:
return alist
#取中间作为基准
mid = alist[len(alist) // 2]
#创建左右列表
left, right = [], []
alist.remove(mid)
#把数根据基准，分别存入左右列表
for num in alist:
if num >= mid:
right.append(num)
else:
left.append(num)
#合并已经左右列表和mid，递归思维该出来啦
return quick_sort(left) + [mid] + quick_sort(right)
if __name__ == '__main__':
alist = [57, 68, 59, 52, 72, 28, 96, 33, 24, 19]
res = quick_sort(alist)
print(res)
四、插入排序
def insert_sort(alist):
#总插入次数循环
for i in range(0, len(alist)-1):
#从第i+1 位开始，依次和前面的数进行比较
for j in range(i+1, 0, -1):
if alist[j] < alist[j-1]:
alist[j], alist[j-1] = alist[j-1], alist[j]
else:
break
return alist
if __name__ == '__main__':
alist = [57, 68, 59, 52, 72, 28, 96, 33, 24, 19]
res = insert_sort(alist)
print(res)
五、希尔排序
希尔排序：
它是基于插入排序的
根据下标+步长的倍数进行划分，并且进行排序
新步长再划分，并排序
下图中同一趟中同颜色的数为同一划分组，组内的数进行插入排序
def shell_sort(alist):
n = len(alist)
#设置初始步长
step = n // 2
while step > 0:
# 按步长进行插入排序
for i in range(step, n):
j = i
# 插入排序
while j >= step and alist[j-step] > alist[j]:
alist[j-step], alist[j] = alist[j], alist[j-step]
j -= step
step = step // 2
if __name__ == '__main__':
alist = [57, 68, 59, 52, 72, 28, 96, 33, 24, 19]
shell_sort(alist)
print(alist)
转载：https://blog.csdn.net/Ann__Liang/article/details/102477339