1 ##乘法表 2 3 def MultiplyTable(): 4 for x in range(1,10): 5 for y in range(1,x+1): 6 print "%s * %s = %2s" % (y,x,x*y) 7 8 #求平方 9 def sqrt(n): 10 if n>0: 11 ans=0 12 while ans*ans<n:ans+=1 13 if ans*ans!=n: 14 print "n不是有完全开放数" 15 else: 16 print ans 17 else: 18 print "不能开放" 19 20 #折半搜索针对排过序的列表 21 def bsearch(lst,val,start,end): 22 if (end-start)<2:return lst[start]==val or lst[start]==val 23 mid=start+(end-start)/2 24 if lst[mid]==val:return True 25 if val>lst[mid]: 26 bsearch(lst,val,mid+1,end) 27 else: 28 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"
29 30 #选择排序O[n2] 31 def selSort(lst): 32 for i in range(len(lst)-1): 33 min=lst[i] 34 minIdx=i 35 j=i+1 36 while j<len(lst): 37 if lst[j]<min: 38 min=lst[j] 39 minIdx=j 40 j=j+1 41 temp=lst[i] 42 lst[i]=lst[minIdx] 43 lst[minIdx]=temp 44 print lst 45 46 #selSort([5,4,2,1]) 47 print "ssssssssssssssss" 48 #冒泡排序 最坏O[n2] 49 def bubbleSort(lst): 50 flag=True 51 while flag: 52 flag=False 53 for i in range(len(lst)-1): 54 if lst[i]>lst[i+1]: 55 temp=lst[i] 56 lst[i]=lst[i+1] 57 lst[i+1]=temp 58 flag=True 59 return lst 60 61 #bubbleSort([5,4,2,1]) 62 print "ssssssssssssss" 63
1 #插入排序 2 def InsertionSort(A): 3 for j in range(1,len(A)): 4 key = A[j] 5 i = j-1 6 #向前查找插入位置 7 while i>=0 and A[i]>key: 8 A[i+1] = A[i] 9 i = i-1 10 A[i+1] = key
64 #归并排序 65 66 def merge(left,right):#合并 67 res=[] 68 i,j=0,0 69 while i<len(left) and j<len(right): 70 if left[i]<=right[j]: 71 res.append(left[i]) 72 i+=1 73 else: 74 res.append(right[j]) 75 j+=1 76 77 while i<len(left): 78 res.append(left[i]) 79 i+=1 80 while j<len(right): 81 res.append(right[j]) 82 j+=1 83 return res 84 85 def mergeSort(lst): 86 # print "start",lst 87 if len(lst)<2: 88 return lst[:] 89 else: 90 mid=len(lst)/2 91 left=mergeSort(lst[:mid]) 92 # print "left",left 93 right=mergeSort(lst[mid:]) 94 # print "right",right 95 together=merge(left,right) 96 97 # print "later",together 98 return together 99 100 #mergeSort([5,4,2,1]) 101 #快排 102
该方法的基本思想是：
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。
103 def quicksort(data, low = 0, high = None): 104 if high == None: 105 high = len(data) - 1 106 if low < high: 107 s, i, j = data[low], low, high 108 while i < j: 109 while i < j and data[j] >= s: 110 j = j - 1 111 if i < j: 112 data[i] = data[j] 113 i = i + 1 114 while i < j and data[i] <= s: 115 i = i + 1 116 if i < j: 117 data[j] = data[i] 118 j = j - 1 119 data[i] = s 120 quicksort(data, low, i - 1) 121 quicksort(data, i + 1, high) 122 return data 123 124 import random,datetime 125 import copy 126 data=[random.randint(1,5) for i in range(2000)]#如果有大量重复数据，归并效率最高 127 128 def sort_perfmon(sortfunc, data): 129 sort_data = copy.deepcopy(data) 130 t1 = datetime.datetime.now() 131 sortfunc(sort_data) 132 t2 = datetime.datetime.now() 133 print sortfunc.__name__, t2 - t1 134 135 sort_perfmon(quicksort, data) 136 sort_perfmon(bubbleSort, data) 137 sort_perfmon(mergeSort, data) 138 139 140 141 142 def mean( sorted_list ): 143 if not sorted_list: 144 return (([],[])) 145 big = sorted_list[-1] 146 small = sorted_list[-2] 147 big_list, small_list = mean(sorted_list[:-2]) 148 big_list.append(small) 149 small_list.append(big) 150 big_list_sum = sum(big_list) 151 small_list_sum = sum(small_list) 152 if big_list_sum > small_list_sum: 153 return ( (big_list, small_list)) 154 else: 155 return (( small_list, big_list)) 156 157 a=[2,1,3,4] 158 b=[3,5,7,8] 159 160 #sorted=sorted((a+b)) 161 #print sorted 162 #print mean(sorted) 163 164 def fibnaci(): 165 a,b=0,1 166 while True: 167 yield b 168 a,b=b,a+b 169 170 def fib(x): 171 if x == 0 or x == 1: return 1 172 else: return fib(x-1) + fib(x-2)