python 算法总结

冒泡排序

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

def bubble_sort(ary):
    if len(ary) <= 1: return ary
    for i in range(len(ary) - 1):
        for j in range(len(ary) - 2 - i):
            if ary[j] > ary[j + 1]:
                ary[j], ary[j + 1] = ary[j + 1], ary[j]
    return ary

插入排序

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤2~5

def insert_sort(ary):
    if len(ary)<=1:return ary
    for a in range(1,len(ary)):
        for b in range(a,0,-1):
            if ary[b-1]>ary[b]:
                ary[b-1],ary[b]=ary[b],ary[b-1]
    return ary

快速排序

1. 从数列中挑出一个元素，称为"基准"（pivot），
2. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3. 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

# 原地分区算法
def partition(a, left, right):
    pivotValue = a[right]
    storeIndex = left
    for i in range(left,right):
        if a[i] < pivotValue:
            a[i], a[storeIndex] = a[storeIndex], a[i]
            storeIndex += 1
    a[storeIndex], a[right]= a[right],a[storeIndex]
    return storeIndex

def quick_sort(a,left,right):
    if left<right:
        index=partition(a,left,right)
        quick_sort(a,left,index-1)
        quick_sort(a,index+1,right)
    return

选择排序

1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
2. 然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

def select_sort(ary):
    if len(ary)<=1:return ary
    for i in range(len(ary)):
        for j in range(i,len(ary)):
            if ary[i]>ary[j]:
                ary[i],ary[j]=ary[j],ary[i]
    return ary