# -*- coding:utf-8 -*-
def bubble_sort(list1):
"""
:param list1:[list] | 随机无序数组
:return: [list] | 经过排序后从小到大的有序数组
| 冒泡排序
时间复杂度 O(n^2)
最优复制度 O(n)
稳定性：稳定【稳定性的意义：需要和初始排位顺序相同才有意义】
"""
n = len(list1)
for i in range(n-1):
for j in range(n-i-1):
if list1[j] > list1[j+1]:
list1[j], list1[j+1] = list1[j+1], list1[j]
return list1
def select_sort(list1):
"""
:param list1:[list] | 随机无序数组
:return: [list] | 经过排序后从小到大的有序数组
|| 选择排序
时间复杂度：O(n^2)
最优时间复杂度: O(n^2)
稳定性：不稳定【相同的数字，经过排序后，相对位置改变】
"""
n = len(list1)
for i in range(n-1):
min_index = i
for j in range(i+1, n):
if list1[min_index] > list1[j]:
min_index = j
list1[i], list1[min_index] = list1[min_index],list1[i]
return list1
def insert_sort(list1):
"""
:param list1:[list] | 随机无序数组
:return: [list] | 经过排序后从小到大的有序数组
|| 插入排序
时间复杂度： O (n^2)
最优时间复杂度：O(n)
稳定性： 稳定
"""
n = len(list1)
for i in range(1, n):
# j = [1, 2, 3, n-1]
# i代表内层循环起始值
j = i # 执行从右边的无序序列中取出一个元素， 即i 位置的元素， 然后将其插入到前面的正确位置中
while j > 0:
if list1[i] < list1[i-1]:
list1[i], list1[i-1] = list1[-1], list1[1]
j -= 1
else:
break
return list1
def shell_sort(list1):
"""
:param list1:[list] | 随机无序数组
:return: [list] | 经过排序后从小到大的有序数组
|| 希尔排序
时间复杂度： O (n^2)
最优时间复杂度：O(n^1.3) 根据步长（暂叫做gap）序列的不同而不同
稳定性： 不稳定
"""
n = len(list1)
gap = n // 2
while gap > 0:
for i in range(gap, n):
j = i
while j > 0:
if list1[i] < list1[i - gap]:
list1[j], list1[j - gap] = list1[j - gap], list1[j]
j -= gap
else:
break
gap //= 2
return list1
if __name__ == '__main__':
list1 = [12, 2, 2, 3, 43, 22, 16, 1]
print(bubble_sort(list1))
print(select_sort(list1))
print(insert_sort(list1))
print(shell_sort(list1))
