@[TOC]
用python实现常见的九种排序
冒泡排序
列表每相邻的数，如果前面比后面大，则交换这两个数一趟排序完成后，则无序区减少一个数，有序增加一个数
from cal_time import cal_time
@cal_time
def bubble_sort(li):
for i in range(len(li)-1):
exchange = False
for j in range(len(li)-i-1):
if li[j] > li[j+1]:
li[j], li[j+1] = li[j+1], li[j]
exchange = True
if not exchange:
return选择排序
# 算法关键： 有序区和无序区， 记录无序区最小数的位置
def select_sort(li):
for i in range(len(li)-1):
min_loc = i
for j in range(i+1,len(li)):
if li[j] < li[min_loc]:
min_loc = j
li[i], li[min_loc] = li[min_loc], li[i]插入排序
def insert_sort(li):
for i in range(1, len(li)):
tmp = li[i]
j = i-1
# 找插入的位置
# 从右往左比较，如果tmp小于l[j]，l[j]他的位置就向右移一个位置，
while j >= 0 and li[j] > tmp:
li[j+1] = li[j]
j = j-1
li[j+1] = tmp快速排序
def partition(li, left, right):
# 将最左边的元素给tmp
tmp = li[left]
while left < right:
while left < right and li[right]>=tmp: # 从右面找出比tmp小的数
right -= 1
li[left] = li[right] # 将右边第一个小于tmp的数放到左边的空位上
while left < right and li[left] <= tmp: # 从左边找出比tmp大的数
left += 1
li[right] = li[left] # 将左边第一个大于tmp的数放到右边刚才腾出来的空位上
li[left] = tmp # 将tmp归位，放到了左边全比它小，右面全比它大的位置，也就是它最后应在的位置
return left # 这个left代表的就是tmp位置的索引
def quick_sort(li, left, right):
if left < right: # 至少有两个元素,是判断递归是否停止的条件
mid = partition(li, left, right)
quick_sort(li,left, mid-1)
quick_sort(li, mid+1,right)堆排序
def sift(li, low, high):
"""
:param li: 列表
:param low: 堆的根节点位置
:param high: 堆的最后一个元素的位置
:return:
"""
i = low # 最开始指向根节点的
j = 2*i+1 # j 开始是左孩子
tmp = li[low] # 把堆顶存起来
while j <= high:
if j + 1 <= high and li[j+1] > li[j]: # 如果右孩子有且比较大
j = j+1 # j指向右孩子
if li[j] > tmp:
li[i] = li[j]
i = j
j = 2*i+1
else: # tmp更大把tmp放到i的位置吧
li[i] = tmp # 把tmp放到某一领导位置
break
else:
li[i] = tmp # 把tmp放到叶子节点
def heap_sort(li):
n = len(li)
for i in range((n-2)//2-1, -1, -1):
# i 标示建堆的时候调整部分的根下标
sift(li, i, n-1)
# 堆建造完成
for i in range(n-1,-1, -1):
# i 指向当前堆的最后一个元素
li[0], li[i] = li[i], li[0]
sift(li, 0, i-1) # i-1 是新的high归并排序
def marge(li, low,mid,high):
"""
:param li: 列表
:param low: 第一个有序列表的起始位置
:param mid: 分界位置的索引
:param high: 第二个有序列表的结尾位置
:return:
"""
i = low
j = mid+1
ltmp = []
while i <= mid and j <= high:
if li[i] <= li[j]:
ltmp.append(li[i])
i += 1
else:
ltmp.append(li[j])
j += 1
# while执行完，肯定有一部分没有数了
# print(li)
# print(len(li))
while i <= mid:
ltmp.append(li[i])
i += 1
while j <= high:
ltmp.append(li[j])
j += 1
li[low:high+1] = ltmp # 给切片赋值
# li = [1,2,5,8,9,4,5,6,7,8]
# print((len(li)-1)//2)
# marge(li, 0,4,len(li)-1)
# # print(li)
def merge_sort(li,low,high):
if high > low: # 至少有两个元素，递归
mid = (low+high) // 2
merge_sort(li, low, mid)
merge_sort(li, mid+1, high)
marge(li, low, mid, high)
希尔排序
def insert_sort_gap_(li,gap):
for i in range(gap,len(li)): # i 代表摸到的牌的下标
tmp = li[i]
j = i-gap # j指的是手中的牌的下标
while j >= 0 and li[j] > tmp:
li[j+gap] = li[j] # 将大的数放到后面
j -= gap
li[j+gap] = tmp
def shell_sort(li):
d = len(li)//2
while d >= 1:
insert_sort_gap_(li,d)
d //= 2
计数排序
def count_sort(li,max_count=100):
count = [0 for _ in range(max_count+1)]
for val in li:
count[val] += 1
li.clear()
for ind, val in enumerate(count):
for i in range(val):
li.append(ind)基数排序
def radix_sort(li):
max_num = max(li)
it = 0
while 10**it <= max_num:
buckets = [[] for _ in range(10)]
# 分桶
for var in li:
digit = (var // 10**it) % 10
buckets[digit].append(var)
# 将数重新放回li
li.clear()
for buc in buckets:
li.extend(buc)
it += 1
