Python算法(一)

1.归并排序

def merge(a, b):
    c = []
    h = j = 0
    # 依次便利，拿到兩個數組更小的元素，
    while j < len(a) and h < len(b):
        # 如果0索引位置的元素a更小，添加a[0]到c，再將a[1]與b[0]比較，依次類推，剩余最后的元素就是两个数组的最大值
        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)

if __name__ == '__main__':
    a = [4, 7, 8, 3, 5, 9,10]
    print(merge_sort(a))

2.快排

#coding:utf-8
def quicksort(list):
    if len(list)<2:
        return list
    else:
        midpivot = list[0]
        lessbeforemidpivot = [i for i in list[1:] if i<=midpivot]
        biggerafterpivot = [i for i in list[1:] if i > midpivot]
        finallylist = quicksort(lessbeforemidpivot)+[midpivot]+quicksort(biggerafterpivot)
        return finallylist

print quicksort([2,4,6,7,1,2,5])

# 使用lambda函数实现
quicksort=lambda data:data if len(data)<2 else quicksort([item for item in data[1:] if item<=data[0]])+[data[0]]+quicksort([item for item in data[1:] if item>data[0]])

print quicksort([2,4,6,7,1,2,5])

3.二分查找

#coding:utf-8
def binary_search(data, item):
    low = 0
    high = len(data) - 1
    while low <= high:
        mid = (low + high) // 2
        guess = data[mid]
        if item < guess:
            high = mid - 1
        elif item > guess:
            low = mid + 1
        elif item == guess:
            return mid
    return None
mylist = [1,3,5,7,9]
print binary_search(mylist,3)

4.质数问题

def is_prime_number(k):
    if k<2:
        return False
    for i in range(2,k):
        if k%i==0:
            return False
    return True

def get_prime_number(start,end):
    # prime_numbers = []
    for k in range(start,end+1):
        if is_prime_number(k):
            yield k
            # prime_numbers.append(k)
    # return prime_numbers

prime_numbers = get_prime_number(1,100)
# print(next(prime_numbers))
for i in prime_numbers:
    print(i)

5.日期问题

# 写一个函数，计算给定日期是该年的第几天和周数
def count(year,month,day):
    count=0
    if (year%4==0 and year%100!=0) or year%400==0:
        print('%d年是闰年，2月份有29天！'%year)
        list1=[31,29,31,30,31,30,31,31,30,31,30,31]
        for i in range(month-1):
            count=count+list1[i]
        return count+
    else:
        print('%d年是平年，2月份有29天！' % year)
        li2 = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
        for i in range(month-1):
            count +=li2[i]
        return count+day
if __name__ == "__main__":
    year = int(input('请输入年份：'))
    month = int(input('请输入月份：'))
    day = int(input('请输入日期：'))
    count = count(year,month,day)
    print('%d年%d月%d日是今年的第%d天！'%(year,month,day,count))

from functools import reduce
# 写一个函数，计算给定日期是该年的第几天和周数
class WhichDay(object):
    def __init__(self,date):
        self.year = int(date.year)
        self.month = int(date.month)
        self.day = int(date.day)
        self.run_nian= [31,29,31,30,31,30,31,31,30,31,30,31]
        self.ping_nian = [31,28,31,30,31,30,31,31,30,31,30,31]

    def count(self):
        if (self.year%4==0 and self.year%100!=0) or self.year%400==0:
            print("该年为闰年")
            print(self.run_nian[:self.month])
            count = reduce(lambda x,y:x+y,self.run_nian[:self.month-1]) + self.day
        else:
            print(self.ping_nian[:self.month])
            count = reduce(lambda x,y:x+y,self.ping_nian[:self.month-1]) + self.day
        return count

if __name__ == "__main__":

    from datetime import datetime
    # from datetime import date
    # date1 = date(2017,6,11)
    # wd = WhichDay(date(2017,6,11))

    date_str='20170611'
    date=datetime.strptime(date_str,'%Y%m%d')
    print(date.year,date.month,date.day)
    wd = WhichDay(date)
    print("{0}是当年的第{1}天".format(date_str,wd.count()))