快速排序Python版

算法 ,
答案 # coding: utf-8 def quick_sort(arr, low, high): # 继续排序的条件是low小于high if low < high: # 将数组分成左右两个区,并返回分区的位置 part_index = partition(arr, low, high) # 递归排序左边的数组 # 这里直接在arr上原地排序,所以不占用额外空间 quick_sort(arr, low, par…

反转单向链表Python版

算法 ,
答案 链表节点定义: class Node(object): def __init__(self): self.value = None self.next = None 链表反转: def reverse_linked_list(head): if not head or not head.next: return head prev = None # 用于暂存前面的节点 next = None # 用于暂存前面的节点 while head: next = head.ne…

选择排序Python版

算法 ,
答案 首先在待排序序列中找到最小元素,存放到序列的起始位置 再从剩余未排序元素中继续寻找最小元素,放到已排序序列的末尾 以此类推,直到所有元素均排序完毕。 def selection_sort(lst): n = len(lst) for i in range(n): min_pos = i for j in range(i + 1, n): if lst[j] < lst[min_p…

归并排序Python版

算法 ,
答案 将待排序列表从中间位置拆分成2个子列表 重复1,直至将列表拆分成一个个只有1个元素的小列表 递归排序两个相邻的小列表,直至所有元素合并完成 def merge_sort(lst): if len(lst) <= 1: return lst mid = len(lst) // 2 left = lst[:mid] right = lst[mid:] left = merge_sort(left) …

插入排序Python版

算法 ,
答案 从第一个元素开始,该元素可以认为已经被排序 取出下一个元素,在已经排序的元素序列中从后向前扫描 如果该元素(已排序)大于新元素,将该元素移到下一位置 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置 将新元素插入到该位置后 重复步骤2~5 def insertion_sort(lst): for…

冒泡排序Python版

算法 ,
答案 比较相邻的元素。如果第一个比第二个大,就交换他们两个。 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。 针对所有的元素重复以上的步骤,除了最后一个。 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较…