1.冒泡排序
#普通版
def test_sort(alist):
n = len(alist)
for j in range(n-1,0,-1):
for i in range(j):
if alist[i] > alist[i+1]:
alist[i], alist[i+1] = alist[i+1], alist[i]
if __name__ == "__main__":
li = [16,13,18,29,7,30,66,77,22,55,0,23,45,63]
test_sort(li)
print(li)
#改进版
def test_sort(alist):
n = len(alist)
for j in range(n-1,0,-1):
count = 0
for i in range(j):
if alist[i] > alist[i+1]:
alist[i], alist[i+1] = alist[i+1], alist[i]
count +=1
if 0 == count:
return
#优化已经是排好顺序的，可以不用在排序。
if __name__ == "__main__":
li = [16,13,18,29,7,30,66,77,22,55,0,23,45,63]
test_sort(li)
print(li)
2.选择排序
def test_sort(alist):
n = len(alist)
for j in range(n-1):
min_index = j
for i in range(j+1, n):
if alist[min_index] > alist[i]:
min_index = i
alist[j], alist[min_index] = alist[min_index], alist[j]
if __name__ == "__main__":
li = [16,13,18,29,7,30,66,77,22,55,0,23,45,63]
test_sort(li)
print(li)
3.插入排序
def test_sort(alist):
n = len(alist)
for j in range(1,n):
#代表内层循环的起始值
i = j
#执行从右边的无序序列中取出第一个元素，既i位置的元素，然后插入到前面的位置
while i > 0:
if alist[i] < alist[i-1]:
alist[i], alist[i-1] = alist[i-1], alist[i]
i -= 1
else:
break
if __name__ == "__main__":
li = [16,13,18,29,7,30,66,77,22,55,0,23,45,63]
test_sort(li)
print(li)
4.希尔排序
def test_sort(alist):
n = len(alist)
gap = n//2
#gap变成1的时候就是一个插入排序
while gap > 0:
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 -= 1
else:
break
#缩短步长
gap //=2
if __name__ == "__main__":
li = [16,13,18,29,7,30,66,77,22,55,0,23,45,63]
test_sort(li)
print(li)
5.快速排序
def test_sort(alist, start, end):
#退出条件
if start >= end:
return
#初始值
mid = alist[start]
#游标
low = start
high = end
while low < high:
while low < high and alist[high] >= mid:
high -= 1
alist[low] = alist[high]
while low < high and alist[low] < mid:
low += 1
alist[high] = alist[low]
#退出循环后程序结束后将基准元素放到该位置
alist[low] = mid
#对基准元素左右子序列分别进行快速排序
test_sort(alist, start, low-1)
test_sort(alist, low+1, end)
if __name__ == "__main__":
li = [16,13,18,29,7,30,66,77,22,55,0,23,45,63]
test_sort(li, 0, len(li)-1)
print(li)
image.png
