4.希尔排序
# -*- coding:utf-8 -*-
def shell_sort(alist):
"""希尔排序"""
n = len(alist)
gap = n // 2
while gap >= 1:
for j in range(gap,n):
i = j
while i > 0:
if alist[i] < alist[i-gap]:
alist[i],alist[i-gap] = alist[i-gap],alist[i]
i -=gap
else:
break
gap //= 2
if __name__ == "__main__":
a = [6,86,3,5,0,43,90,100]
print(a)
shell_sort(a)
print(a)
# [6, 86, 3, 5, 0, 43, 90, 100]
# [0, 3, 5, 6, 43, 86, 90, 100]
5.快速排序
# -*- coding:utf-8 -*-
def quick_sort(alist,first,last):
"""快速排序"""
if first >= last:
return
# n = len(alist)
mid_value = alist[first]
low = first
high = last
while low < high:
#High左移
while low <high and alist[high] >= mid_value:
high -= 1
alist[low] = alist[high]
# Low右移
while low <high and alist[low] < mid_value:
low += 1
alist[high]=alist[low]
alist[low]=mid_value
quick_sort(alist,first,low-1)
quick_sort(alist,low+1, last)
if __name__ == "__main__":
a = [6,86,3,5,0,43,90,100]
print(a)
quick_sort(a,0,len(a)-1)
print(a)
# [6, 86, 3, 5, 0, 43, 90, 100]
# [0, 3, 5, 6, 43, 86, 90, 100]
6.归并排序
# -*- coding:utf-8 -*-
def merge_sort(alist):
"""归并排序"""
n = len(alist)
if n <= 1:
return alist
mid =n // 2
left_alist = merge_sort(alist[:mid])
right_alist = merge_sort(alist[mid:])
left_pointer,right_pointer = 0,0
result = []
while left_pointer < len(left_alist) and right_pointer < len(right_alist):
if left_alist[left_pointer] < right_alist[right_pointer]:
result.append(left_alist[left_pointer])
left_pointer += 1
else:
result.append(right_alist[right_pointer])
right_pointer += 1
result += left_alist[left_pointer:]
result += right_alist[right_pointer:]
return result
if __name__ == "__main__":
a = [6, 86, 3, 5, 0, 43, 90, 10]
print(a)
sorted_list = merge_sort(a)
print(sorted_list)
# [6, 86, 3, 5, 0, 43, 90, 10]
# [0, 3, 5, 6, 10, 43, 86, 90]
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。