Chow's Notes

用python实现的常用算法

发表于 | 分类于 |

##乘法表

1
2
3
4
def MultiplyTable():
    for x in range(1,10):
        for y in range(1,x+1):
            print "%s * %s = %2s" % (y,x,x*y)

#求平方

1
2
3
4
5
6
7
8
9
10
def sqrt(n):
    if n>0:
        ans=0 
        while ans*ans<n:ans+=1
        if ans*ans!=n:
            print "n不是有完全开方数"
        else:
            print ans
    else:
        print "不能开方"

#折半搜索针对排过序的列表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def bsearch(lst,val,start,end):
    if (end-start)<2:return lst[start]==val or lst[start]==val
    mid=start+(end-start)/2
    if lst[mid]==val:return True
    if val>lst[mid]:
        bsearch(lst,val,mid+1,end)
    else:
        bsearch(lst,val,start,mid-1)
def bsearch(lst,val):
    start=0
    end=len(lst)-1
    while(start<=end):
        mid=start+(end-start)/2
        if lst[mid]<val:
            start=mid+1
        elif lst[mid]>val:
            end=mid-1
        else:
            return mid
    return "none"

#选择排序O[n2]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def selSort(lst):
    for i in range(len(lst)-1):
        min=lst[i]
        minIdx=i
        j=i+1
        while j<len(lst):
            if lst[j]<min:
                min=lst[j]
                minIdx=j
            j=j+1
        temp=lst[i]
        lst[i]=lst[minIdx]
        lst[minIdx]=temp
        print lst
        
#selSort([5,4,2,1])
print "ssssssssssssssss"

#冒泡排序 最坏O[n2]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def bubbleSort(lst):
    flag=True
    while flag:
        flag=False
        for i in range(len(lst)-1):
            if lst[i]>lst[i+1]:
                temp=lst[i]
                lst[i]=lst[i+1]
                lst[i+1]=temp
                flag=True
    return lst
        
#bubbleSort([5,4,2,1])
print "ssssssssssssss"

#插入排序

1
2
3
4
5
6
7
8
9
def InsertionSort(A):
    for j in range(1,len(A)):
        key = A[j]
        i = j-1
        #向前查找插入位置
        while i>=0 and A[i]>key:
            A[i+1] = A[i]
            i = i-1
        A[i+1] = key

#归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def merge(left,right):#合并
    res=[]
    i,j=0,0
    while i<len(left) and j<len(right):
        if left[i]<=right[j]:
            res.append(left[i])
            i+=1
        else:
            res.append(right[j])
            j+=1
            
    while i<len(left):
        res.append(left[i])
        i+=1
    while j<len(right):
        res.append(right[j])
        j+=1
    return res
def mergeSort(lst):
#    print "start",lst
    if len(lst)<2:
        return lst[:]
    else:
        mid=len(lst)/2
        left=mergeSort(lst[:mid])
#        print "left",left
        right=mergeSort(lst[mid:])
#        print "right",right
        together=merge(left,right)
#        print "later",together
        return together
        
#mergeSort([5,4,2,1])

#快排
该方法的基本思想是：
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def quicksort(data, low = 0, high = None):
    if high == None:
        high = len(data) - 1
    if low < high:
        s, i, j = data[low], low, high
        while i < j:
            while i < j and data[j] >= s:
                j = j - 1
            if i < j:
                data[i] = data[j]
                i = i + 1
            while i < j and data[i] <= s:
                i = i + 1
            if i < j:
                data[j] = data[i]
                j = j - 1
        data[i] = s
        quicksort(data, low, i - 1)
        quicksort(data, i + 1, high)
    return data
import random,datetime
import copy      
data=[random.randint(1,5) for i in range(2000)]#如果有大量重复数据，归并效率最高
def sort_perfmon(sortfunc, data):
    sort_data = copy.deepcopy(data)
    t1 = datetime.datetime.now()
    sortfunc(sort_data)
    t2 = datetime.datetime.now()
    print sortfunc.__name__, t2 - t1
sort_perfmon(quicksort, data)
sort_perfmon(bubbleSort, data)
sort_perfmon(mergeSort, data)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def mean( sorted_list ):
    if not sorted_list:
        return (([],[]))
    big = sorted_list[-1]
    small = sorted_list[-2]
    big_list, small_list = mean(sorted_list[:-2])
    big_list.append(small)
    small_list.append(big)
    big_list_sum = sum(big_list)
    small_list_sum = sum(small_list)
    if big_list_sum > small_list_sum:
        return ( (big_list, small_list))
    else:
        return (( small_list, big_list))
a=[2,1,3,4]
b=[3,5,7,8]
#sorted=sorted((a+b))
#print sorted
#print mean(sorted)
1
2
3
4
5
6
7
8
9
def fibnaci():
    a,b=0,1
    while True:
        yield b
        a,b=b,a+b 
        
def fib(x):
    if x == 0 or x == 1: return 1
    else: return fib(x-1) + fib(x-2)