Udemy——Python数据结构与算法（11）

 课程：【Udemy高分付费课程】Python数据结构与算法 - 终极 Python 编码面试和计算机科学训练营（中英文字幕）_哔哩哔哩_bilibili

算法

归并排序

基本思想

归并排序是一种基于分治思想的排序算法。它的核心思想是将待排序序列不断分成两半，直到每一部分只有一个元素（此时认为是有序的），然后将这些有序的小序列两两合并，得到新的有序序列，如此反复，直到整个序列有序。

def merge(list1,list2):
    combined=[]
    i=0
    j=0
    while i < len(list1) and j < len(list2):
        if list1[i] < list2[j]:
            combined.append(list1[i])
            i+=1
        else:
            combined.append(list2[j])
            j+=1
    while i < len(list1):
        combined.append(list1[i])
        i+=1
    while j < len(list2):
        combined.append(list2[j])
        j+=1
    return combined


def merge_sort(my_lists):
    if len(my_lists)==1:
        return my_lists
    mid =int(len(my_lists)/2)
    left=my_lists[:mid]
    right=my_lists[mid:]
    return merge(merge_sort(left),merge_sort(right))

print(merge_sort([3,5,2,6,8,2,6,3,5,34,156]))

快速排序

• 选择基准（Pivot）： 从待排序的序列中选择一个元素作为基准。
• 分区（Partition）： 将序列中所有比基准小的元素移动到基准的左边，所有比基准大的元素移动到基准的右边。此时，基准元素就位于其最终的排序位置上。
• 递归排序： 对基准左右两个子序列分别递归地执行步骤 1 和 2，直到每个子序列只有一个元素或为空，排序完成。

def swap(my_list,index1,index2):
    temp=my_list[index1]
    my_list[index1]=my_list[index2]
    my_list[index2]=temp
def pivot(my_list,pivot_index,end_index):
    swap_index=pivot_index
    for i in range(pivot_index+1,end_index+1):
        if my_list[i]<my_list[pivot_index]:
            swap_index+=1
            swap(my_list,i,swap_index)
    swap(my_list,pivot_index,swap_index)
    return swap_index
def quick_sort_helper(my_list,left,right):
    if left<right:
        pivot_index=pivot(my_list,left,right)
        quick_sort_helper(my_list,left,pivot_index-1)
        quick_sort_helper(my_list,pivot_index+1,right)
    return my_list
def quick_sort(my_list):
    return quick_sort_helper(my_list,0,len(my_list)-1)


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

树遍历 Tree Traversal

基础代码——二叉树

class Node:
    def __init__(self,value):
        self.value=value
        self.left=None
        self.right=None
class BinarySearchTree:
    def __init__(self,value):
        self.root=Node(value)

广度搜索 Breadth First Search

def BFS(self):
    current_node=self.root
    queue=[]
    results=[]
    queue.append(current_node)
    while len(queue)>0:
        current_node=queue.pop(0)
        results.append(current_node.value)
        if current_node.left is not Node:
            queue.append(current_node.left)
        if current_node.right is not Node:
            queue.append(current_node.right)
    return results

深度搜索 Depth First Search

def dfs_pre_order(self):
    results=[]
    def traverse(current_node):
        results.append(current_node.value)
        if current_node.left is not None:
            traverse(current_node.left)
        if current_node.right is not None:
            traverse(current_node.right)
    traverse(self.root)
    return results

def dfs_post_order(self):
    results=[]
    def traverse(current_node):
        results.append(current_node.value)
        if current_node.left is not None:
            traverse(current_node.left)
            traverse(current_node.right)
        if current_node.right is not None:
            traverse(current_node.right)
            traverse(current_node.left)
def dfs_in_order(self):
    results=[]
    def traverse(current_node):
        if current_node.left is not None:
            traverse(current_node.left)
        results.append(current_node.value)
        if current_node.right is not None:
            traverse(current_node.right)
    traverse(self.root)
    return results