排序算法(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)