Python 算法讲解

def hanoi(n, a, b, c):
    if n>0:
        hanoi(n-1, a, c, b)
        print("moving from %s to %s" % (a, c))
        hanoi(n-1, b, a, c)

def linear_search(li, val):
    for ind, v in enumerate(li):
        if v==val:
            return ind
    else:
        return None

# 二分查找
def binary_search(li, val):
    left = 0
    right = len(li)-1
    while left <= right:
        mid = (left+right)//2
        if li[mid] == val:
            return mid
        elif li[mid] > val:
            left = mid - 1
        else:
            right = mid + 1
    else:
        return  None

li = [1, 3, 5, 6, 7, 9]
print(binary_search(li, 5)

# 冒泡排序
def bubble_sort(li):
    for i in range(len(li)-1):
        exchange = False
        for j in range(len(li)-1-i):
            if li[j] > li[j+1]:
                li[j], li[j+1] = li[j+1], li[j]
                exchange = True
        if not exchange:
            return li
    return li

li = [9, 1, 5, 6, 8, 4, 2]
print(li)
print(bubble_sort(li)

# 选择排序
def select_sort(li):
    for i in range(len(li)-1):
        min_loc = i
        for j in range(i+1, len(li)):
            if  li[j] < li[min_loc]:
                min_loc =j
        li[i], li[min_loc] = li[min_loc], li[i]
    return li

# 插入排序
def insert_sort(li):
    for i in range(1, len(li)):
        tmp = li[i] # 选择的要插入的牌
        j = i-1 # 手里已经排好序的牌的前一张
        while j>=0 and tmp<li[j]:
            li[j+1] = li[j]
            j -= 1
        li[j+1] = tmp
        print(li)
    return li

li = [4, 8, 0, 1, 5, 7]
print(li)
print(insert_sort(li)

# 快排的归为操作
def partition(li, left, right):
    print('kaishi')
    tmp = li[left]
    while left<right:
        # 先从右边开始找
        while li[right] >= tmp and left<right:
            right -= 1
        li[left] = li[right]
        # 再从左边开始找
        while left<right and li[left] <= tmp:
            left += 1
        li[right] = li[left]
    li[left] = tmp
    print(li)
 
print(li)
partition(li, 0, len(li)-1

def partition(li, left, right):
    tmp = li[left]
    while left < right:
        while left < right and li[right] >= tmp: #从右面找比tmp小的数
            right -= 1      # 往左走一步
        li[left] = li[right] #把右边的值写到左边空位上
        # print(li, 'right')
        while left < right and li[left] <= tmp:
            left += 1
        li[right] = li[left] #把左边的值写到右边空位上
        # print(li, 'left')
    li[left] = tmp      # 把tmp归位
    return left


def _quick_sort(li, left, right):
    if left<right:  # 至少两个元素
        mid = partition(li, left, right)
        _quick_sort(li, left, mid-1)
        _quick_sort(li, mid+1, right)

@cal_time
def quick_sort(li):
    _quick_sort(li, 0, len(li)-1)

li = list(range(10000, 0, -1))
# random.shuffle(li)
#
# li1 = copy.deepcopy(li)
# li2 = copy.deepcopy(li)
#
quick_sort(li)
# bubble_sort(li2)
#
# print(li1)
# print(li2)

# li = [9,8,7,6,5,4,3,2,1]
# partition(li, 0, len(li)-1)
# print(li

def sift(li, low, high):
    """
    :param li: 列表
    :param low: 堆的根节点位置
    :param high: 堆的最后一个元素的位置
    :return: 
    """
    i = low # i最开始指向根节点
    j = 2 * i + 1 # j开始是左孩子
    tmp = li[low] # 把堆顶存起来
    while j <= high: # 只要j位置有数
        if j + 1 <= high and li[j+1] > li[j]: # 如果右孩子有并且比较大
            j = j + 1  # j指向右孩子
        if li[j] > tmp:
            li[i] = li[j]
            i = j           # 往下看一层
            j = 2 * i + 1
        else:       # tmp更大，把tmp放到i的位置上
            li[i] = tmp     # 把tmp放到某一级领导位置上
            break
    else:
        li[i] = tmp  # 把tmp放到叶子节点

def heap_sort(li):
    n = len(li)
    for i in range((n-2)//2, -1, -1):
        # i表示建堆的时候调整的部分的根的下标
        sift(li, i, n-1)
    # 建堆完成了
    for i in range(n-1, -1, -1):
        # i 指向当前堆的最后一个元素
        li[0], li[i] = li[i], li[0]
        sift(li, 0, i - 1) #i-1是新的high


li = [i for i in range(100)]
import random
random.shuffle(li)
print(li)

heap_sort(li)
print(li

def topk(li, k):
    heap = li[0:k]
    for i in range((k-2)//2, -1, -1):
        sift(heap, i, k-1)
    # 1.建堆
    for i in range(k, len(li)-1):
        if li[i] > heap[0]:
            heap[0] = li[i]
            sift(heap, 0, k-1)

    # 2.遍历
    for i in range(k-1, -1, -1):
        heap[0], heap[i] = heap[i], heap[0]
        sift(heap, 0, i - 1)
    # 3.出数
    return heap

import random
li = list(range(1000))
random.shuffle(li)

print(topk(li, 10)

class Node:
   def __init__(self, item):
      self.item = item
      self.next = None

def create_linklist_tail(li):
   head = Node(li[0])
   tail = head
   for element in li[1:]:
      node = Node(element)
      tail.next = node
      tail = node
   return head

def print_linklist(lk):
   while lk:
      print(lk.item, end=",")
      lk = lk.next

li = [1, 2, 3, 4, 6]
lk = create_linklist_tail(li)
print_linklist(lk)

# 数字拼接问题
from functools import cmp_to_key

li = [32, 94, 128, 1286, 6, 71]

def xy_cmp(x, y):
   if x+y < y+x:
      return 1
   elif x+y > y+x:
      return -1
   else:
      return 0
   
def number_join(li):
   li = list(map(str, li))
   print(li)
   li.sort(key=cmp_to_key(xy_cmp))
   return "".join(li)

print(number_join(li)