文章出处： https://blog.csdn.net/qq_35955528/article/details/98344262
1、冒泡排序
工作原理：
比较相邻两个元素，如果第一个元素比第二个元素大（升序），则将这两个元素交换；对每一对相邻的元素做同样的工作，从开始第一对到结尾最后一对。做完一次之后，最后一个元素就是最大的元素；针对所有元素作上述操作，除最后一个元素外；持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
def bullet_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__':
a
= [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(a
)
bullet_sort
(a
)
print(a
)
时间复杂度
最优时间复杂度：O(n) （表示遍历一次发现没有任何可以交换的元素，排序结束。）最坏时间复杂度：O(n2)稳定性：稳定（当两个属性相等时，不会更改原有顺序）
图例
2、选择排序
工作原理：
查找最小的元素，放在起始位置；在未排序的序列中再找出最小元素，放在已排序序列的末尾；针对剩下元素上述操作，直到末尾截止。
def select_sort(aList
):
n
= len(aList
)
for j
in range(n
- 1):
min_index
= j
for i
in range(j
+ 1, n
):
if aList
[i
] < aList
[min_index
]:
min_index
= i
if min_index
!= j
:
aList
[j
], aList
[min_index
] = aList
[min_index
], aList
[j
]
if __name__
== '__main__':
a
= [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(a
)
select_sort
(a
)
print(a
)
时间复杂度
最优时间复杂度：O(n2)最坏时间复杂度：O(n2)稳定性：不稳定（考虑升序每次选择最大的情况）
图例
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]
if __name__ == '__main__':
a = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(a)
insert_sort(a)
print(a)
时间复杂度
最优时间复杂度：O(n) （升序排列，序列已经处于升序状态）最坏时间复杂度：O(n2)稳定性：稳定
图例
4、快速排序
工作原理：
从数列中挑出一个元素，称为"基准"（pivot），重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
def quick_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
quick_sort
(aList
, start
, low
- 1)
quick_sort
(aList
, low
+ 1, end
)
if __name__
== '__main__':
a
= [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(a
)
quick_sort
(a
, 0, len(a
) - 1)
print(a
)
时间复杂度
最优时间复杂度：O(nlogn)最坏时间复杂度：O(n2)稳定性：不稳定
图例
5、希尔排序
工作原理：
将序列按照步长进行分组将分组后的元素进行插入排序；缩短步长，继续执行上述操作；直到步长为0时结束。
def shell_sort(aList
):
n
= len(aList
)
gap
= n
// 2
while gap
> 0:
for j
in range(gap
, n
):
i
= j
while i
>= gap
and aList
[i
] < aList
[i
- gap
]:
aList
[i
], aList
[i
- gap
] = aList
[i
- gap
], aList
[i
]
i
-= gap
gap
= gap
// 2
if __name__
== '__main__':
a
= [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(a
)
shell_sort
(a
)
print(a
)
时间复杂度
最优时间复杂度：根据步长序列的不同而不同最坏时间复杂度：O(n2)稳定性：不稳定
图例
6、归并排序
工作原理：
将序列进行拆分；将拆分后的序列进行两两排序合并；将有序序列再进行两两排序合并；直至合并成一条序列。
def merge_sort(aList
):
n
= len(aList
)
if n
<= 1:
return aList
num
= n
// 2
left_list
= merge_sort
(aList
[:num
])
right_list
= merge_sort
(aList
[num
:])
left
, right
= 0, 0
result
= []
while left
< len(left_list
) and right
< len(right_list
):
if left_list
[left
] <= right_list
[right
]:
result
.append
(left_list
[left
])
left
+= 1
else:
result
.append
(right_list
[right
])
right
+= 1
result
+= left_list
[left
:]
result
+= right_list
[right
:]
return result
if __name__
== '__main__':
a
= [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(a
)
b
= merge_sort
(a
)
print(b
)
时间复杂度
最优时间复杂度：O(nlogn)最坏时间复杂度：O(nlogn)稳定性：稳定
图例
常见排序算法比较
