一、冒泡排序
# 冒泡排序
def bubbleSort(l):
for i in range(len(l)-1, 0, -1):
exchange = False
for j in range(i):
if l[j] > l[j+1]:
exchange = True
l[j], l[j+1] = l[j+1], l[j]
if not exchange:
return l
return l
二、选择排序
# 选择排序
def selectionSort(l):
for i in range(len(l)-1, 0, -1):
largest = 0
for j in range(1, i+1):
if l[j] > l[largest]:
largest = j
l[i], l[largest] = l[largest], l[i]
return l
三、插入排序
# 插入排序
def insertionSort(l):
for i in range(1, len(l)):
cur = l[i]
position = i-1
while position >= 0 and l[position] > cur:
l[position+1] = l[position]
position -= 1
l[position+1] = cur
return l
四、希尔排序
插入排序的比对次数，在最好的情况下是O(n)，这发生在列表已是有序的情况下。实际上，列表越接近有序，插入排序的比对次数就越少。谢尔排序以插入排序作为基础，对无序表进行间隔划分，并对每个子列表都执行插入排序。随着子列表的数量越来越少，无序表的整体越来越接近有序，从而减少整体排序的比对次数。最后一趟是标准的插入排序，但由于前面几趟已经将列表处理到接近有序，这一趟仅需少数几次移动即可完成。子列表的间隔一般从n/2开始，每趟倍增：n/4, n/8......直到1。
由于每趟都使得列表更加接近有序，这过程会减少很多原先需要的无效比对。对谢尔排序的详尽分析比较复杂，大致说是介于O(n)和O(n^2)之间。
如果将间隔保持在2k-1(1、3、5、7、15、31等等），谢尔排序的时间复杂度约为O(n^1.5)。
希尔排序不稳定。例如[2, 5, 2, 1, 4, 6]，间隔为3，上来就把l[0]和l[3]互换了，那么l[0]与l[2]的顺序就变了。
五、归并排序
归并排序是稳定的：合并两个有序数组的时候，是稳定的。两个有序数组比较第一个元素，哪个小，哪个先。如果相等，则左数组先。
归并排序需要额外的的存储空间，因为合并时需要。
时间复杂度：最好、最差和平均都是。每一层的时间复杂度为
，共有
logn层。
# 归并排序
def mergeSort(l):
if len(l) <= 1:
return l
mid = len(l)//2
left = mergeSort(l[:mid])
right = mergeSort(l[mid:])
merge = []
while left and right:
if left[0] <= right[0]:
merge.append(left.pop(0))
else:
merge.append(right.pop(0))
merge.extend(left if left else right)
return merge
六、快速排序
快速排序是不稳定的：[5, 8, 2, 5, 2]，8和最后一个2交换，则两个2的次序变了。长距离交换，不稳定！
快速排序需要额外的的存储空间，因为虽然不需要存数组，但递归调用是用栈的，需要额外存储空间。
最好情况：每一次的flag刚好都可以平分整个数组，此时的时间复杂度为；
最差情况：每一次的flag刚好都是最大或者最小的数，此时的时间复杂度为；
平均情况：经过推导，平均情况为。
# 快速排序
def quickSort(l, left, right):
if right <= left:
return
leftmark, rightmark = left, right
tmp = l[left]
leftmark += 1
while leftmark <= rightmark:
while leftmark <= rightmark and l[leftmark] <= tmp:
leftmark += 1
while leftmark <= rightmark and l[rightmark] >= tmp:
rightmark -= 1
if leftmark < rightmark:
l[leftmark], l[rightmark] = l[rightmark], l[leftmark]
l[left], l[rightmark] = l[rightmark], l[left]
quickSort(l, left, rightmark-1)
quickSort(l, rightmark+1, right)
return l
