分类：算法

快速排序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…

什么情况下快速排序最慢?

算法
答案 这个得看pivot（基准元素或枢轴）的选择策略。 如果选择最左面或最右面的元素作为基准元素，那最坏的情况就会在： 数组已经是正序排过序的。 数组已经是倒序排过序的。 所有的元素都相同（1、2的特殊情况）。 因为这些案例在用例中十分常见，所以这个问题可以通过要么选择一个随机的基准…

反转单向链表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…

反转单向链表Java版

算法 , ,
答案 public class Node { public int value; public Node next; public Node(int value) { this.value = value; } public Node reverseList(Node head) { Node prev = null; // 用于暂存前面的节点 Node next = null; // 用于暂存后面的节点 while (head != null) { next = head.next; // 把…

给定四个坐标点，判断它们能不能组成一个矩形

算法
答案 设四点(x0, y0), (x1, y1), (x2, y2), (x3, y3) 只要计算三个内角都是直角就可以推导出这四点组成一个矩形 也就是判断相邻的边正交，即相邻边的边矢量点积为0 (x3-x0)(x1-x0)+(y3-y0)(y1-y0) == 0 (以(x0, y0)为顶点的角) 且 (x0-x1)(x2-x1)+(y0-y1)(y2-y1) == 0 (以(x1, y1)为顶点的角)…

选择排序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…