Quick Sort
引例：荷兰国旗问题
Merge Sort
class Solution {
public:
ListNode* sortList(ListNode* head) {
if (head == nullptr || head->next == nullptr) { return head; }
ListNode* fast = head;
ListNode* slow = head;
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = nullptr;
return mergeTwoLists(sortList(head), sortList(fast));
}
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == nullptr && l1 ==nullptr) { return nullptr; }
if (l1 == nullptr || l2 == nullptr) { return l1 == nullptr ? l2 : l1;}
ListNode dummy(-1), *current;
current = &dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
current->next = l1;
l1 = l1->next;
}
else{
current->next = l2;
l2 = l2->next;
}
current = current->next;
}
current->next = l1 == nullptr ? l2 : l1;
return dummy.next;
}
};
Heap Sort
https://docs.python.org/3/library/heapq.html#heapq.heapify
时间复杂度O(N*logN)，额外空间复杂度O(1)。
堆结构非常重要
- 堆结构的
heapInsert和heapify - 堆结构的增大和减少
- 如果只是建堆的过程，时间复杂度为O(N)
- 优先级队列结构，就是堆结构
堆的定义：
堆结构就是一个完全二叉树，数组的结构实现，通过约定下标规则。
对于任意下标为i的结点，
- 左孩子：
2*i + 1 - 右孩子：
2*i + 2 - 父节点：
(i-1) // 2
大根堆：在一棵完全二叉树中，任何一棵子树的最大值都是这棵子树的根，所形成的结构叫大根堆。小根堆类似。
堆的特点与优势：
-
大/小根堆有一个很重要的属性：它的最大/小元素始终是根节点
heap[0]。 -
堆的调整代价只和
层数有关，所以入堆和出堆的代价只有O(lgN)。
大根堆的实现：
This implementation uses arrays for which heap[i] > heap[2*i+1] and heap[i] > heap[2*i+2] for all i, counting elements from zero.
给定数组，都可根据约定视其为堆，但其不是大根堆，如何将数组调整为大根堆？
建立大根堆：
heapInsert: 经历一个新结点加入一个已经调整好的堆中，同时往上调整的过程。调整停止条件：当加入结点值不大于其父节点时，
调整停止。
堆在数组上可伸缩
def insertHeap(arr, index):
par_i = (index - 1) // 2
while par_i >= 0 and arr[index] > arr[par_i]: # 插入结点值比父结点大时，往上调整
arr[index], arr[par_i] = arr[par_i], arr[index] # 与父结点交换
index = par_i # 插入结点来到父节点的位置
par_i = (index - 1) // 2
def createHeap(arr):
if arr == None or len(arr) < 2:
return arr
for i in range(len(arr)): # 依次将结点加入堆中， 最终将数组（堆）调整为大根堆
insertHeap(arr, i)
return arr
时间复杂度分析：O(N)
当第i个结点加入堆中时，0~i-1已经调整为大根堆，其高度为O(log(i-1))，即调整代价为O(log(i-1))。(沿其父结点依次向上>
比较调整)
所以, N个结点的调整代价为：O(lg1) + O(lg2) + ... + O(lgN)收敛于O(N)
堆化：
def heapify(arr, index, heapSize):
left = 2 * index + 1
# 左孩子未越界，在堆上，继续循环判断是否下沉
while left < heapSize:
# 1. 求左右孩子最大的下标
largest = left + 1 if (left+1) < heapSize and arr[left+1] > arr[left] else left
# 2. 最大孩子和本结点最大的下标
largest = index if arr[index] >= arr[largest] else largest
# 3. 如果最大的结点就是自身，heapify完成跳出
if largest == index:
break
# 4. 否则，交换下沉
arr[largest], arr[index] = arr[index], arr[largest]
index = largest
left = 2 * index + 1
堆排序：
堆大小：heapSize = len(arr)
数组最后一个数下标：heapSize -= 1
- 把数组
arr创建为大根堆 - 堆顶
arr[0]与数组最后一个数arr[heapSize]交换 - 将堆的大小缩小
heapSize -= 1 0~heapSize做heapify- 至
2循环，直到堆大小减到0，数组有序
def heapSort(arr):
createHeap(arr)
heapSize = len(arr)
while heapSize > 1:
heapSize -= 1
arr[0], arr[heapSize] = arr[heapSize], arr[0]
heapify(arr, 0, heapSize)
Topological Sort
# Definition for a Directed graph node
class DirectedGraphNode:
def __init__(self, x):
self.label = x
self.neighbors = []
class Solution:
"""
@param graph: A list of Directed graph node
@return: A list of integer
"""
def topSort(self, graph):
# 1. 统计结点入度
indegree = self.get_indegree(graph)
# 2. BFS
order = []
start_nodes = [n for n in graph if indegree[n] == 0] # 入度为0的所有结点
queue = collections.deque(start_nodes) # 队列中存储的是入度为0的点
while queue:
node = queue.popleft()
order.append(node)
for neighbor in node.neighbors: # 遍历该节点的所有邻居节点，第一层遍历。
indegree[neighbor] -= 1 # 将队列中输出的点的所以临界点入度减1
if indegree[neighbor] == 0: # 将入度为0的结点放入队列
queue.append(neighbor)
return order
def get_indegree(self, graph):
""" 计算每一个结点的入度数
"""
indegree = {x: 0 for x in graph} # 初始化每一个结点的入度数为0
for node in graph:
for neighbor in node.neighbors:
indegree[neighbor] += 1
return indegree