冒泡排序
特点
时间复杂度 O(n^2 )，非常慢。算法
外层指针，循环整个列表。
内层指针，循环整个列表 - 外层循环次数
遍历每个元素和该元素的下一个元素，如果顺序不一致，则调换两个元素。
- 代码
def bubble_sort(arr):
"""
poping the greatest value to the right
"""
for i in range(1, len(arr)):
for j in range(0, len(arr) - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
插入排序
特点
最坏情况时间复杂度 O(n^2 )，非常慢。
对于近乎有序的列表，速度很快。算法
外层指针，循环整个列表一次。每次指向一个元素。
内层指针，对于每个外层指针指到的元素，从该角标处开始，倒序循环，
判断内层指针指到的元素与外层指针指到的元素的大小关系。
如果和排序要求不一致，则将内层指针指到的元素后移一位。
如果和排序要求一致，则停止该内层指针的循环。
如果内层指针回到列表起始处，也停止该内层指针的循环。
停止循环后，在内层指针的位置插入外层指针指到的元素。代码
def insertion_sort(arr）:
"""
shift all greater values to the right
"""
for i in range(1, len(arr)):
cur = arr[i]
prev = i - 1
while prev >= 0 and arr[prev] > cur:
arr[prev + 1] = arr[prev]
prev -= 1
arr[prev + 1] = cur
return arr
插入法从小到大排序，当外层指针指到数字1时的内层循环
选择排序
- 特点
时间复杂度 O(n^2 )，非常慢。 - 算法
外层指针，循环整个列表
内层指针，循环整个列表 - 外层循环次数
每次循环，取出循环范围内的最大或最小值，放到一边。 - 代码
def selection_sort(arr):
"""
exchange the greatest value and the right last value
"""
for i in range(0, len(arr)):
max_index = 0
for j in range(1, len(arr) - i):
if arr[j] > arr[max_index]:
max_index = j
arr[len(arr) - 1 - i], arr[max_index] = arr[max_index], arr[len(arr) - 1 - i]
return arr
希尔排序
特点
插入排序的改进版。
时间复杂度介于O(n(logn))与O(n^2 )之间。适用于中等规模排序。-
算法
不对整个列表进行外层循环，而是拆成若干组各自进行插入排序。
拆成组的个数：len(li) / 2 → len(li) / 4 → len(li) / 8 → ... → 2 → 1
分成 8 / 2 = 4 组
分成 8 / 4 = 2 组
分成 1 组
归并排序
特点
时间复杂度为O(nlogn)，速度快，稳定。适用于数据量大的排序。-
算法
基于分治法的排序。
基础是将两个有序的列表，合并为一个有序的列表。
为两个有序列表各定义一个指针。定义一个新的空列表。
两个指针指向的元素进行比较。较小的元素放入空列表，同时指向该较小元素的指针后移一位。
当其中一个列表的元素遍历完成后，将另一个列表剩下的元素放入空列表。
空列表是两个就是排好序的合并列表。
合并有序列表A和B，结果为列表C
递归由下至上进行归并排序
