排序算法可以说是每个程序员都必须得掌握的了, 弄明白它们的原理和实现很有必要，以下为大家介绍十大常用排序算法的python实现方式，方便大家学习。
01 冒泡排序——交换类排序
02 快速排序——交换类排序
03 选择排序——选择类排序
04 堆排序——选择类排序
05 插入排序——插入类排序
06 希尔排序——插入类排序
07 归并排序——归并类排序
08 计数排序——分布类排序
09 基数排序——分布类排序
10 桶排序——分布类排序
取一个小于n的整数gap(gap被称为步长)将待排序元素分成若干个组子序列，所有距离为gap的倍数的记录放在同一个组中
对各组内的元素进行直接插入排序， 这一趟排序完成之后，每一个组的元素都是有序的
减小gap的值，并重复执行上述的分组和排序
-
重复上述操作，当gap=1时，排序结束
'''希尔排序'''
def Shell_Sort(arr):
# 设定步长,注意类型
step = int(len(arr) / 2)
while step > 0:
for i in range(step, len(arr)):
# 类似插入排序, 当前值与指定步长之前的值比较, 符合条件则交换位置
while i >= step and arr[i - step] > arr[i]:
arr[i], arr[i - step] = arr[i - step], arr[i]
i -= step
step = int(step / 2)
return arr
arr = [29, 63, 41, 5, 62, 66, 57, 34, 94, 22]
result = Shell_Sort(arr)
print('result list: ', result)
# result list: [5, 22, 29, 34, 41, 57, 62, 63, 66, 94]申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
设定两个索引，最初索引位置分别为两个已经排序序列的起始位置
比较两个索引所指向的元素，选择相对小的元素放入到合并空间，并移动索引到下一位置
重复上一步骤直到某一索引超出序列尾
-
将另一序列剩下的所有元素直接复制到合并序列尾
'''归并排序'''def Merge(left, right):
arr = []
i = j = 0
while j < len(left) and i < len(right):
if left[j] < right[i]:
arr.append(left[j])
j += 1
else:
arr.append(right[i])
i += 1
if j == len(left):
# right遍历完
for k in right[i:]:
arr.append(k)
else:
# left遍历完
for k in left[j:]:
arr.append(k)
return arr
def Merge_Sort(arr):
# 递归结束条件
if len(arr) <= 1:
return arr
# 二分
middle = len(arr) // 2
left = Merge_Sort(arr[:middle])
right = Merge_Sort(arr[middle:])
# 合并
return Merge(left, right)
arr = [27, 70, 34, 65, 9, 22, 47, 68, 21, 18]
result = Merge_Sort(arr)
print('result list: ', result)
# result list: [9, 18, 21, 22, 27, 34, 47, 65, 68, 70]找出待排序的数组中最大和最小的元素
统计数组中每个值为i的元素出现的次数，存入数组C的第i项
对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
'''计数排序'''
def Count_Sort(arr):
max_num = max(arr)
min_num = min(arr)
count_num = max_num - min_num + 1
count_arr = [0 for i in range(count_num)]
res = [0 for i in range(len(arr))]
# 统计数字出现的次数
for i in arr:
count_arr[i - min_num] += 1
# 统计前面有几个比自己小的数
for j in range(1, count_num):
count_arr[j] = count_arr[j] + count_arr[j - 1]
# 遍历重组
for k in range(len(arr)):
res[count_arr[arr[k] - min_num] - 1] = arr[k]
count_arr[arr[k] - min_num] -= 1
return res
arr = [5, 10, 76, 55, 13, 79, 5, 49, 51, 65, 30, 5]
result = Count_Sort(arr)
print('result list: ', result)
# result list: [5, 5, 5, 10, 13, 30, 49, 51, 55, 65, 76, 79]根据个位数的数值，遍历列表将它们分配至编号0到9的桶子中
将这些桶子中的数值重新串接起来
根据十位数的数值，遍历列表将它们分配至编号0到9的桶子中
再将这些桶子中的数值重新串接起来
'''基数排序'''
def Radix_Sort(arr):
max_num = max(arr)
place = 0
while 10 ** place <= max_num:
# 创建桶
buckets = [[] for _ in range(10)]
# 分桶
for item in arr:
pos = item // 10 ** place % 10
buckets[pos].append(item)
j = 0
for k in range(10):
for num in buckets[k]:
arr[j] = num
j += 1
place += 1
return arr
arr = [31, 80, 42, 47, 35, 26, 10, 5, 51, 53]
result = Radix_Sort(arr)
print('result list: ', result)
# result list: [5, 10, 26, 31, 35, 42, 47, 51, 53, 80]计算有限桶的数量
逐个桶内部排序
遍历每个桶，进行合并
'''桶排序'''
def Bucket_Sort(arr):
num = max(arr)
# 列表置零
pre_lst = [0] * num
result = []
for data in arr:
pre_lst[data - 1] += 1
i = 0
while i < len(pre_lst): # 遍历生成的列表，从小到大
j = 0
while j < pre_lst[i]:
result.append(i + 1)
j += 1
i += 1
return result
arr = [26, 53, 83, 86, 5, 46, 5, 72, 21, 4, 75]
result = Bucket_Sort(arr)
print('result list: ', result)
# result list: [4, 5, 5, 21, 26, 46, 53, 72, 75, 83, 86]
