冒泡排序(稳定)—O(n²)
- 基本思想：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。
def bubble_sort(alist):
n = len(alist)
for j in range(n - 1):
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
print(alist)
if (count == 0):
break
if __name__ == '__main__':
alist = [5, 4, 3, 6, 2, 9, 1, 8, 7, 0]
print(alist)
bubble_sort(alist)
[5, 4, 3, 6, 2, 9, 1, 8, 7, 0]
[4, 3, 5, 2, 6, 1, 8, 7, 0, 9]
[3, 4, 2, 5, 1, 6, 7, 0, 8, 9]
[3, 2, 4, 1, 5, 6, 0, 7, 8, 9]
[2, 3, 1, 4, 5, 0, 6, 7, 8, 9]
[2, 1, 3, 4, 0, 5, 6, 7, 8, 9]
[1, 2, 3, 0, 4, 5, 6, 7, 8, 9]
[1, 2, 0, 3, 4, 5, 6, 7, 8, 9]
[1, 0, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
选择排序（不稳定）—O(n²)
- 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
def sellect_sort(alist):
n = len(alist)
for i in range(n):
min = i
for j in range(i + 1, n):
if alist[min] > alist[j]:
min = j
alist[min], alist[i] = alist[i], alist[min]
print(alist)
return alist
if __name__ == '__main__':
alist = [5, 4, 3, 6, 2, 9, 1, 8, 7, 0]
print(alist)
sellect_sort(alist)
[5, 4, 3, 6, 2, 9, 1, 8, 7, 0]
[0, 4, 3, 6, 2, 9, 1, 8, 7, 5]
[0, 1, 3, 6, 2, 9, 4, 8, 7, 5]
[0, 1, 2, 6, 3, 9, 4, 8, 7, 5]
[0, 1, 2, 3, 6, 9, 4, 8, 7, 5]
[0, 1, 2, 3, 4, 9, 6, 8, 7, 5]
[0, 1, 2, 3, 4, 5, 6, 8, 7, 9]
[0, 1, 2, 3, 4, 5, 6, 8, 7, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
插入排序(稳定)—O(n**2)
- 通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
def inser_sort(alist):
n = len(alist)
for i in range(1, n):
# 控制将拿到的元素放到前面的有序序列中的正确位置的过程
for j in range(i, 0, -1):
# 如果比前面的元素小，则往前移
if alist[j] < alist[j - 1]:
alist[j], alist[j - 1] = alist[j - 1], alist[j]
print(alist)
else:
break
if __name__ == '__main__':
alist = [5, 4, 3, 6, 2, 9, 1, 8, 7, 0]
print(alist)
inser_sort(alist)
[5, 4, 3, 6, 2, 9, 1, 8, 7, 0]
[4, 5, 3, 6, 2, 9, 1, 8, 7, 0]
[4, 3, 5, 6, 2, 9, 1, 8, 7, 0]
[3, 4, 5, 6, 2, 9, 1, 8, 7, 0]
[3, 4, 5, 2, 6, 9, 1, 8, 7, 0]
[3, 4, 2, 5, 6, 9, 1, 8, 7, 0]
[3, 2, 4, 5, 6, 9, 1, 8, 7, 0]
[2, 3, 4, 5, 6, 9, 1, 8, 7, 0]
[2, 3, 4, 5, 6, 1, 9, 8, 7, 0]
[2, 3, 4, 5, 1, 6, 9, 8, 7, 0]
[2, 3, 4, 1, 5, 6, 9, 8, 7, 0]
[2, 3, 1, 4, 5, 6, 9, 8, 7, 0]
[2, 1, 3, 4, 5, 6, 9, 8, 7, 0]
[1, 2, 3, 4, 5, 6, 9, 8, 7, 0]
[1, 2, 3, 4, 5, 6, 8, 9, 7, 0]
[1, 2, 3, 4, 5, 6, 8, 7, 9, 0]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 0]
[1, 2, 3, 4, 5, 6, 7, 8, 0, 9]
[1, 2, 3, 4, 5, 6, 7, 0, 8, 9]
[1, 2, 3, 4, 5, 6, 0, 7, 8, 9]
[1, 2, 3, 4, 5, 0, 6, 7, 8, 9]
[1, 2, 3, 4, 0, 5, 6, 7, 8, 9]
[1, 2, 3, 0, 4, 5, 6, 7, 8, 9]
[1, 2, 0, 3, 4, 5, 6, 7, 8, 9]
[1, 0, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
希尔排序(不稳定)—O(n^(3/2))
- 也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
def shell_sort(alist):
n = len(alist)
gap = n // 2
while gap >= 1:
for j in range(gap, n):
i = j
while (i - gap) >= 0:
print(i,gap)
if alist[i] < alist[i - gap]:
alist[i], alist[i - gap] = alist[i - gap], alist[i]
print(alist)
i -= gap
else:
break
gap //= 2
if __name__ == '__main__':
alist = [5, 4, 3, 6, 2, 9, 1, 8, 7, 0]
print(alist)
shell_sort(alist)
[5, 4, 3, 6, 2, 9, 1, 8, 7, 0]
5 5
6 5
[5, 1, 3, 6, 2, 9, 4, 8, 7, 0]
7 5
8 5
9 5
[5, 1, 3, 6, 0, 9, 4, 8, 7, 2]
2 2
[3, 1, 5, 6, 0, 9, 4, 8, 7, 2]
3 2
4 2
[3, 1, 0, 6, 5, 9, 4, 8, 7, 2]
2 2
[0, 1, 3, 6, 5, 9, 4, 8, 7, 2]
5 2
6 2
[0, 1, 3, 6, 4, 9, 5, 8, 7, 2]
4 2
7 2
[0, 1, 3, 6, 4, 8, 5, 9, 7, 2]
5 2
8 2
9 2
[0, 1, 3, 6, 4, 8, 5, 2, 7, 9]
7 2
[0, 1, 3, 6, 4, 2, 5, 8, 7, 9]
5 2
[0, 1, 3, 2, 4, 6, 5, 8, 7, 9]
3 2
1 1
2 1
3 1
[0, 1, 2, 3, 4, 6, 5, 8, 7, 9]
2 1
4 1
5 1
6 1
[0, 1, 2, 3, 4, 5, 6, 8, 7, 9]
5 1
7 1
8 1
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
7 1
9 1