之前在这C语言实现八大排序算法（一）和C语言实现八大排序算法（二）2篇文章中，已经详细介绍了各种排序算法的思想，参考资料主要是用C语言实现的。本文主要用python语言再次实现十大排序算法。
十大排序算法的复杂度及稳定性分析如下表所示：
插入排序
代码
''' 1. 从第一个元素开始，该元素可以认为已经被排序 2.取出下一个元素，在已经排序的元素序列中从后向前扫描 3.如果该元素（已排序）大于新元素，将该元素移到下一位置 4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置 5.将新元素插入到该位置中 6.重复步骤2 '''
def insert_sort(list):
for i in range(1,len(list)):
print("第{}轮：".format(i))
key=list[i]
j=i-1
while j>=0:
if list[j]>key:
list[j+1]=list[j]
list[j]=key
j-=1
print(list)
return list
a=[2,4,3,8,1,5,7,6]
result=insert_sort(a)
#print(result)
结果
第1轮：
[2, 4, 3, 8, 1, 5, 7, 6]
第2轮：
[2, 3, 4, 8, 1, 5, 7, 6]
第3轮：
[2, 3, 4, 8, 1, 5, 7, 6]
第4轮：
[1, 2, 3, 4, 8, 5, 7, 6]
第5轮：
[1, 2, 3, 4, 5, 8, 7, 6]
第6轮：
[1, 2, 3, 4, 5, 7, 8, 6]
第7轮：
[1, 2, 3, 4, 5, 6, 7, 8]
希尔排序
代码
''' 1.希尔排序是把记录按下标的一定量分组，对每组使用直接插入算法排序； 2.随着增量逐渐减少，每组包1含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法被终止。 '''
def shell_sort(list):
# 设定步长
step = int(len(list)/2)
while step > 0:
print(step)
for i in range(step, len(list)):
# 类似插入排序, 当前值与指定步长之前的值比较, 符合条件则交换位置
while i >= step and list[i-step] > list[i]:
list[i], list[i-step] = list[i-step], list[i]
i -= step
step = int(step/2)
print(list)
return list
a=[2,4,3,8,1,5,7,6]
result=shell_sort(a)
#print(result)
结果
4
[1, 4, 3, 6, 2, 5, 7, 8]
2
[1, 4, 2, 5, 3, 6, 7, 8]
1
[1, 2, 3, 4, 5, 6, 7, 8]
冒泡排序
代码
''' 1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。 2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 3.针对所有的元素重复以上的步骤，除了最后一个。 4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。 '''
def bubble_sort(list):
global flag
for i in range(len(list)-1):
print("第{}轮：".format(i))
flag=False #本次冒泡是否发生交换的标志
for j in range(len(list)-i-1):
if list[j]>list[j+1]:
list[j],list[j+1]=list[j+1],list[j]
flag=True
print(list)
if flag==False: #未交换，数组已经有序，无须冒泡
return
a=[2,4,3,8,1,5,7,6]
result=bubble_sort(a)
结果
第0轮：
[2, 3, 4, 1, 5, 7, 6, 8]
第1轮：
[2, 3, 1, 4, 5, 6, 7, 8]
第2轮：
[2, 1, 3, 4, 5, 6, 7, 8]
第3轮：
[1, 2, 3, 4, 5, 6, 7, 8]
第4轮：
[1, 2, 3, 4, 5, 6, 7, 8]
快速排序
代码
''' 1.从数列中挑出一个元素，称为 “基准”（pivot）； 2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）； 3.对所有两个小数列重复第二步，直至各区间只有一个数。 '''
def quicksort(list,start,end):
if start>=end:
return
low=start
high=end
base=list[start]
while low<high:
while low<high and list[high]>=base: #从后向前找第一个小于基准值的数
high-=1
if low<high:
list[low]=list[high]
low+=1
while low<high and list[low]<base: #从前向后找第一个大于基准值的数
low+=1
if low<high:
list[high]=list[low]
high-=1
list[low]=base #填坑
quicksort(list,start,low-1) #递归排序
quicksort(list,low+1,end)
a=[2,4,3,8,1,5,7,6]
quicksort(a,0,len(a)-1)
print(a)
结果
[1, 2, 3, 4, 5, 6, 7, 8]
选择排序
代码
''' 选择排序的基本思想：比较 + 交换。 第一趟，在待排序记录r1 到 r[n]中选出最小的记录，将它与r1交换； 第二趟，在待排序记录r2 到 r[n]中选出最小的记录，将它与r2交换； 以此类推，第 i 趟，在待排序记录ri 到 r[n]中选出最小的记录，将它与r[i]交换,使有序序列不断增长直到全部排序完毕。 '''
def select_sort(list):
for i in range(0,len(list)):
print("第{}轮：".format(i))
min=i
for j in range(i+1,len(list)):
if list[min]>list[j]:
min=j
list[min],list[i]=list[i],list[min] #每轮找出最小的交换
print(list)
return list
a=[2,4,3,8,1,5,7,6]
result=select_sort(a)
#print(result)
结果
第0轮：
[1, 4, 3, 8, 2, 5, 7, 6]
第1轮：
[1, 2, 3, 8, 4, 5, 7, 6]
第2轮：
[1, 2, 3, 8, 4, 5, 7, 6]
第3轮：
[1, 2, 3, 4, 8, 5, 7, 6]
第4轮：
[1, 2, 3, 4, 5, 8, 7, 6]
第5轮：
[1, 2, 3, 4, 5, 6, 7, 8]
第6轮：
[1, 2, 3, 4, 5, 6, 7, 8]
第7轮：
[1, 2, 3, 4, 5, 6, 7, 8]
堆排序
代码
''' 大根堆：每个节点的值都大于或等于其子节点的值，用于升序排列； 小根堆：每个节点的值都小于或等于其子节点的值，用于降序排列。 以大根堆为例，每次将最大元素放置在堆顶 '''
def adjust_heap(lists, i, size): #向下调整大根堆
''' :param lists: 数组元素 :param i: 当前结点 :param size: 数组长度 '''
# 非叶子结点的左右两个孩子
lchild = 2 * i + 1
rchild = 2 * i + 2
# 在当前结点、左孩子、右孩子中找到最大元素的索引
max = i
if i < size // 2:
if lchild < size and lists[lchild] > lists[max]:
max = lchild
if rchild < size and lists[rchild] > lists[max]:
max = rchild
# 如果最大元素的索引不是当前结点，把大的结点交换到上面，继续调整堆
if max != i:
# 第 2 个参数传入 max 的索引是交换前大数字对应的索引
# 交换后该索引对应的是小数字，应该把该小数字向下调整
lists[max], lists[i] = lists[i], lists[max]
adjust_heap(lists, max, size)
def build_heap(lists, size): #建立大根堆
for i in range(0, (size//2))[::-1]: # 从倒数第一个非叶子结点开始建立大根堆
adjust_heap(lists, i, size) # 对所有非叶子结点进行堆的调整
def heap_sort(lists):
size = len(lists)
build_heap(lists, size)
for i in range(0, size)[::-1]:
lists[0], lists[i] = lists[i], lists[0] # 每次根结点都是最大的数，最大数放到后面
adjust_heap(lists, 0, i) # 交换完后还需要继续调整堆，只需调整根节点，此时数组的 size 不包括已经排序好的数
print("第{}轮：".format(size-i))
print(lists) # 由于每次大的都会放到后面，因此最后的 lists 是从小到大排列
a=[2,4,3,8,1,5,7,6]
result=heap_sort(a)
结果
第1轮：
[7, 6, 5, 4, 1, 2, 3, 8]
第2轮：
[6, 4, 5, 3, 1, 2, 7, 8]
第3轮：
[5, 4, 2, 3, 1, 6, 7, 8]
第4轮：
[4, 3, 2, 1, 5, 6, 7, 8]
第5轮：
[3, 1, 2, 4, 5, 6, 7, 8]
第6轮：
[2, 1, 3, 4, 5, 6, 7, 8]
第7轮：
[1, 2, 3, 4, 5, 6, 7, 8]
第8轮：
[1, 2, 3, 4, 5, 6, 7, 8]
归并排序
代码
''' 1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列； 2.设定两个指针，最初位置分别为两个已经排序序列的起始位置 3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置； 4.重复步骤③直到某一指针达到序列尾； 5.将另一序列剩下的所有元素直接复制到合并序列尾。 '''
def merge(left_list,right_list):
left_index=0
right_index=0
merge_list=[]
while left_index<len(left_list) and right_index<len(right_list):
if left_list[left_index]<right_list[right_index]: #哪一部分小，就添加到合并的列表中
merge_list.append(left_list[left_index])
left_index+=1
else:
merge_list.append(right_list[right_index])
right_index+=1
merge_list+=left_list[left_index:] #将剩余的部分添加到合并列表中
merge_list+=right_list[right_index:]
return merge_list
def merge_sort(list):
if len(list)<=1:
return list
mid_index=len(list)//2 #拆分数组为两部分
left_list=merge_sort(list[:mid_index])
right_list=merge_sort(list[mid_index:])
return merge(left_list,right_list)
a=[2,4,3,8,1,5,7,6]
result=merge_sort(a)
print(result)
结果
[1, 2, 3, 4, 5, 6, 7, 8]
基数排序
代码
''' 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。 然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。 '''
def radix_sort(list):
i = 0 # 记录当前正在排拿一位，最低位为1
max_num = max(list) # 最大值
j = len(str(max_num)) # 记录最大值的位数
while i < j:
bucket_list =[[] for _ in range(10)] #初始化桶数组
for x in list:
bucket_list[int(x / (10**i)) % 10].append(x) # 找到位置放入桶数组
print("第{}轮：".format(i+1))
print(bucket_list)
list.clear()
for x in bucket_list: # 放回原序列
for y in x:
list.append(y)
print(list)
i += 1
return list
a = [334,5,67,345,7,5345,99,4,23,78,45,1,453,3424]
result=radix_sort(a)
# print(result)
结果
第1轮：
[[], [1], [], [23, 453], [334, 4, 3424], [5, 345, 5345, 45], [], [67, 7], [78], [99]]
[1, 23, 453, 334, 4, 3424, 5, 345, 5345, 45, 67, 7, 78, 99]
第2轮：
[[1, 4, 5, 7], [], [23, 3424], [334], [345, 5345, 45], [453], [67], [78], [], [99]]
[1, 4, 5, 7, 23, 3424, 334, 345, 5345, 45, 453, 67, 78, 99]
第3轮：
[[1, 4, 5, 7, 23, 45, 67, 78, 99], [], [], [334, 345, 5345], [3424, 453], [], [], [], [], []]
[1, 4, 5, 7, 23, 45, 67, 78, 99, 334, 345, 5345, 3424, 453]
第4轮：
[[1, 4, 5, 7, 23, 45, 67, 78, 99, 334, 345, 453], [], [], [3424], [], [5345], [], [], [], []]
[1, 4, 5, 7, 23, 45, 67, 78, 99, 334, 345, 453, 3424, 5345]
计数排序
代码
''' 1.找到给定序列的最小值与最大值 2.创建一个长度为最大值-最小值+1的数组，初始化都为0 然后遍历原序列，记录每个数据出现的次数 此时数组中已经记录好每个值的数量，自然也就是有序的了 '''
def count_sort(list):
# 找到最大最小值
min_num = min(list)
max_num = max(list)
# 计数列表，即桶的个数
count_list = [0]*(max_num-min_num+1)
print(count_list)
# 将元素值作为键值存储在桶中，记录其出现的次数
for i in list:
count_list[i-min_num] += 1 #最小值作为一个偏移量存在，因为数据可能存在负数的
print(count_list)
list.clear()
# 填回
for ind,i in enumerate(count_list): #ind为索引，i为数据
while i != 0:
list.append(ind+min_num) #数据的真实值
i -= 1 #该数据出现的次数
return list
a = [34,5,7,34,9,5,23,12,1]
result=count_sort(a)
print(result)
结果
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 2, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2]
[1, 5, 5, 7, 9, 12, 23, 34, 34]
桶排序
代码
''' 桶排序与计数排序类似，但可以解决非整数的排序 1.桶排序相当于把计数数组划分为按顺序的几个部分 2.每一部分叫做一个桶，它来存放处于该范围内的数 3.然后再对每个桶内部进行排序，可以使用其他排序方法如快速排序 4.最后整个桶数组就是排列好的数据，再将其返回给原序列 '''
def bucket_sort(list):
min_num = min(list)
max_num = max(list)
# 桶的大小
bucket_range = (max_num-min_num) / len(list)
# 桶数组
count_list = [ [] for i in range(len(list) + 1)]
print(count_list)
# 向桶数组填数
for i in list:
count_list[int((i-min_num)//bucket_range)].append(i)
print(count_list)
list.clear()
# 回填，这里桶内部排序直接调用了sorted
for i in count_list:
for j in sorted(i):
list.append(j)
print(list)
return list
a = [37,5,7.8,37,9,5,23,12,1]
result=bucket_sort(a)
#print(result)
结果
[[], [], [], [], [], [], [], [], [], []]
[[1], [5, 7.8, 5], [9, 12], [], [], [23], [], [], [], [37, 37]]
[1]
[1, 5, 5, 7.8]
[1, 5, 5, 7.8, 9, 12]
[1, 5, 5, 7.8, 9, 12]
[1, 5, 5, 7.8, 9, 12]
[1, 5, 5, 7.8, 9, 12, 23]
[1, 5, 5, 7.8, 9, 12, 23]
[1, 5, 5, 7.8, 9, 12, 23]
[1, 5, 5, 7.8, 9, 12, 23]
[1, 5, 5, 7.8, 9, 12, 23, 37, 37]
京公网安备 11010502036488号