1.冒泡排序
def bubble_sort(alist):
"""冒泡排序"""
n = len(alist)
for j in range(n - 1):
"""j=0,1,2,n-2"""
count = 0
"""内层循环控制从头到尾的遍历"""
for i in range(0, n - 1 - j):
if alist[i] > alist[i + 1]:
alist[i], alist[i + 1] = alist[i + 1], alist[i]
count += 1
if 0 == count:
break
1.1冒泡排序的测试
if __name__ == '__main__':
li = [54, 26, 77, 17, 77, 31, 44, 55, 20]
print(li)
bubble_sort(li)
print(li)2.选择排序
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]
2.2选择排序的测试
alist = [54, 226, 93, 17, 77, 31, 44, 55, 20]
selection_sort(alist)
print(alist)3.插入排序
def insert_sort(alist):
n = len(alist)
for j in range(1, n):
for i in range(j, 0, -1):
if alist[i] < alist[i - 1]:
alist[i], alist[i - 1] = alist[i - 1], alist[i]
else:
break
print(alist)
3.3插入排序的测试
if __name__ == '__main__':
li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(li)
insert_sort(li)4.快速排序
def quick_sort(alist, start, end):
if start >= end:
return
mid = alist[start]
left = start
right = end
"""left与right未重合，就向中间移动"""
while left < right:
while left < right and alist[right] >= mid:
right -= 1
alist[left] = alist[right]
while left < right and alist[left] <= mid:
left += 1
alist[right] = alist[left]
"""循环退出来后，left与right相遇，即left=right"""
alist[left] = mid
print(alist)
quick_sort(alist, start, left - 1)
quick_sort(alist, left + 1, end)
4.4快速排序测试
if __name__ == '__main__':
li = [54, 26, 93, 1, 7, 31, 44, 55, 20]
quick_sort(li, 0, len(li) - 1)
# print(li)5.希尔排序
def shell_sort(alist):
n = len(alist)
gap = n // 2 # 4
while gap >= 1:
"j是从间隔gap到序列末尾的值"
for j in range(gap, n): # j=4 ，5，6，7，8
i = j # i=4 ，5，6，7，8
while (i - gap) >= 0: # i-gap=4-4,5-4,6-4,7-4,8-4
if alist[i] < alist[i - gap]: # 下标为i的和下标为i-gap的比较(alist[4]<alist[0])
alist[i], alist[i - gap] = alist[i - gap], alist[i] # 如果小于交换位置
else:
break # 如果大于，不交换位置
gap = gap // 2 # 减小间隔
5.5希尔排序测试
if __name__ == '__main__':
li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(li)
shell_sort(li)
print(li)6.归并排序
def merge_sort(alist):
"""归并排序"""
n = len(alist)
if 1 == n:
return alist
mid = n // 2
"""对左半部分进行归并排序"""
left_sorted_li = merge_sort(alist[:mid])
"""对右半部分进行归并排序"""
right_sorted_li = merge_sort(alist[mid:])
"""合并两个有序集合"""
left, right = 0, 0 # 设定两个游标，让其初始值为0
merge_sortted_li = [] # 设定一个空列边用于添加合并元素
left_n = len(left_sorted_li)
right_n = len(right_sorted_li)
while left < left_n and right < right_n:
if left_sorted_li[left] <= right_sorted_li[right]:
merge_sortted_li.append(left_sorted_li[left])
left += 1
else:
merge_sortted_li.append(right_sorted_li[right])
right += 1
merge_sortted_li += left_sorted_li[left:]
merge_sortted_li += right_sorted_li[right:]
return merge_sortted_li
6.6归并排序测试
if __name__ == '__main__':
alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print("before sort: %s" % alist)
sorted_alist = merge_sort(alist)
print("after sort: %s" % alist)
print("sorted new list: %s" % sorted_alist)