排序算法(python实现)

冒泡排序

思想为对一个序列中的每两个都进行比较，把大的放到后面
第一趟比较完后(第二个for循环第一次遍历)，最大的就到了最后
第二趟比较的的时候就不用管最后一个，所以第一层循环让遍历的数量不带最后一个

def bubble_sort(l):
    for i in range(len(l),0,-1):
        for j in range(len(l)-1):
            if l[j] > l[j+1]:
                tmp = l[j]
                l[j] = l[j+1]
                l[j+1] = tmp
l = [3,5,1,1,2,5,3,4,7]
bubble_sort(l)
print l

插入排序

一开始以第一个数的序号为index
第二层的循环依次和第一个数相比，如果比第一个数小，就把这个数的序号作为index，第二层循环一次后最小的那个数的序号就是index，然后把这个数和最开始作为index的那个数交换，一次排序后，最小的在最前面
第二次遍历就不用管第一个了
感觉上插入排序和冒泡差不多，插入是把最小的先放在最前面，冒泡是把最大的先放在最后面，不过，插入是先遍历，然后交换序号，确定序号后，最后把相对应的元素放到对应的位置上，冒泡是每次都交换，不过两者的时间复杂度都是O(n2)

def insertion_sort(a):
    for i in range(len(a)):
        index = i
        for j in range(i+1,len(a)):
            if a[j] < a[index]:
                index = j
        tmp = a[i]
        a[i] = a[index]
        a[index] = tmp
a = [3,5,2,2,1,4,5,7,-1,0,99,8976789659,897689,75,6]
insertion_sort(a)
print a

合并排序(归并排序)

源网址
此算法为分而治之思想的典型应用
其原理为，要对一个序列进行排序，可以先将其分成两个子序列，子序列再递归的分下去，直到分成数量为一个的序列，然后再合起来，合起来的过程是对两个相邻的子序列进行比较，小的放入一个新的空序列的前面，大的放在后面(看代码比较直白，归并排序需要定义一个辅助方法merge,负责对两个子序列进行比较并合并)，将一个序列分成子序列的时间复杂度为logN，排序的复杂度为N，故其总的时间复杂度为NlogN

def merge(a, b):
    c = []
    h = j = 0
    while j < len(a) and h < len(b):
        if a[j] < b[h]:
            c.append(a[j])
            j += 1
        else:
            c.append(b[h])
            h += 1

    if j == len(a):
        for i in b[h:]:
            c.append(i)
    else:
        for i in a[j:]:
            c.append(i)
    return c

def merge_sort(lists):
    if len(lists) <= 1:
        return lists
    middle = len(lists)/2
    left = merge_sort(lists[:middle])
    right = merge_sort(lists[middle:])
    return merge(left, right)
        
l = [23,3,5,346,23546,25461,12345546,1234]
merge_sort(l)

快速排序

快速排序的原理，用递归的方式，取一个序列中的一个数作为基准数，然后把比这个基准数大的放到一个数列，比他小的放到另一个数列，然后对每一个数列递归的重复这一过程，直到分成的序列只有一个数为止，然后就递归的返回
看到下面这个很酷炫的写法，，，酷到炸裂，用到了python的列表推导式，每次都选用序列的第一个数作为基准数

def qsort(L):  
    if len(L) <= 1: return L  
    return qsort([lt for lt in L[1:] if lt < L[0]]) + [L[0]] + qsort([ge for ge in L[1:] if ge >= L[0]])        
l = [23,3,5,346,23546,25461,12345546,1234]
qsort(l)