二叉树和 Huffman 编码有了解，然后后面那个是 quicksort with 3-way partitioning 的性质。它使用 \sim (2 ln 2) NH 次比较，当没有重复键时， H = lg N 此时复杂度为 \sim N lg N 当重复键非常多时， H 接近常数值。
2023-11-09T09:00:00Z
非常好 heap 数据结构和 heapsort 算法，使我的时间复杂度 \sim N log N ，空间复杂度 1 。Priority queue 用处多多，非常好。
知道了这么多种排序方法，综合来说最好用的是 quicksort，但是当 stability 比较重要而 extra space 不太重要的时候最好用的还是 mergesort。
在 Java 中有非常好库方法 java.util.Arrays.sort()，但是在 Java 中要注意维护 immutability。
-
Fundamentals
-
Sorting
-
Searching
- Symbol tables ←
- Binary search trees
- Balanced search trees
- Hash tables
- Applications
-
Graphs
-
Strings
-
Context
2023-11-09T14:10:00Z
已完成 cs61b hw1: Packages, Interfaces, Generics, Exceptions, Iteration。
我也能在这里打卡吗，我懒得开贴了（x
好哇好哇 
2023-11-09T19:02:00Z
你已经掌握了排序算法的奥秘了，那么就来一场试炼罢。
LeetCode 148. Sort List
1 Selection sort
创建一个 sentinel node，每次选出最大的 node，append 到 sentinel 后面。
class Solution {
public ListNode sortList(ListNode head) {
return selectionSort(head);
}
private static ListNode selectionSort(ListNode head) {
ListNode sentinel = new ListNode(0, null);
while (head != null) {
ListNode largestPrev = findLargestPrev(head);
ListNode largest = largestPrev.next;
if (largest == head) {
head = head.next;
}
largestPrev.next = largest.next;
largest.next = sentinel.next;
sentinel.next = largest;
}
return sentinel.next;
}
/** return the previous node of the largest node */
private static ListNode findLargestPrev(ListNode head) {
ListNode largestPrev = new ListNode(0, head);
ListNode currentPrev = largestPrev;
while (currentPrev.next != null) {
if (currentPrev.next.val > largestPrev.next.val) {
largestPrev = currentPrev;
}
currentPrev = currentPrev.next;
}
return largestPrev;
}
}
时间复杂度 O(N^{2}) ，空间复杂度 O(1) ，不出意外的 TLE。
2 Insertion sort
数组的 insertion sort 是从头开始遍历，如果比左边小就向左交换位置。对于 SLList，依然是创建一个 sentinel node，从 head 节点开始一个一个插入 sentinel 之后，若比后面节点大则向右交换。
class Solution {
public ListNode sortList(ListNode head) {
return insertionSort(head);
}
private static ListNode insertionSort(ListNode head) {
ListNode sentinel = new ListNode(0, null);
while (head != null) {
ListNode temp = head;
head = head.next;
temp.next = sentinel.next;
sentinel.next = temp;
swapHelper(sentinel);
}
return sentinel.next;
}
/** swap first node of sorted list rightwards while larger than right */
private static void swapHelper(ListNode sentinel) {
ListNode prev = sentinel;
ListNode newly = sentinel.next;
while (newly.next != null && newly.val > newly.next.val) {
prev.next = newly.next;
newly.next = newly.next.next;
prev.next.next = newly;
prev = prev.next;
}
}
}
时间复杂度 O(N^{2}) ，空间复杂度 O(1) ，又是令人欣慰的 TLE。但是这个指针操作比上一个要优雅多了。
3 Mergesort
Divide and conquer. Use top-down mergesort.
class Solution {
public ListNode sortList(ListNode head) {
if (head == null) return null;
return mergesort(head);
}
/** recursively split and merge */
private static ListNode mergesort(ListNode head) {
if (head.next == null) return head;
ListNode mid = split(head);
ListNode leftSorted = mergesort(head);
ListNode rightSorted = mergesort(mid);
return merge(leftSorted, rightSorted);
}
/** split the given list into two and return the pointer to the second half */
private static ListNode split(ListNode head) {
ListNode fast = head.next;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
ListNode mid = slow.next;
slow.next = null;
return mid;
}
/** merge left list and right list */
private static ListNode merge(ListNode left, ListNode right) {
ListNode sentinel = new ListNode(0, null);
ListNode rear = sentinel;
while (left != null && right != null) {
if (left.val <= right.val) {
ListNode temp = left;
left = left.next;
temp.next = null;
rear.next = temp;
} else {
ListNode temp = right;
right = right.next;
temp.next = null;
rear.next = temp;
}
rear = rear.next;
}
if (left == null) {
while (right != null) {
ListNode temp = right;
right = right.next;
temp.next = null;
rear.next = temp;
rear = rear.next;
}
} else { // right == null
while (left != null) {
ListNode temp = left;
left = left.next;
temp.next = null;
rear.next = temp;
rear = rear.next;
}
}
return sentinel.next;
}
}
时间复杂度 O(NlogN) ，空间复杂度 O(1) ，顺利 AC。
对 SLList 进行 quicksort 用 Java 太难实现了，遂放弃。（因为 Java 方法只能返回一个值，并且不能像 C/C++ 一样传递指针的指针来实现多返回值。）
SLList 的节点只有一个指针空间，故也不能实现 Heapsort。所以 mergesort 事坠吼的。
但是有一点小问题：为了避免 mergesort 的 worst case，在数组版本中首先对待排序数组进行 shuffle，链表好像不是很好进行 shuffle。第二个就是为了方便在 SLList 中进行节点插入删除，我使用了 currentPrev.next == current。但感觉这样很不优雅，不知道有没有什么修改方法。
Insertion sort 中我函数抽象的层次不对，应该把可复用的 swap() 抽象出来，而不是依赖于调用函数的 swapHelper()。
今天刷了 2 节 c s61b，复习了下 BST 和 AVL 树，学到了 B 树 和 红黑树
学 B 树 使我水元素充盈，太牛逼了
但是像 AVL 树，B 树，红黑树 这些都是平衡二叉搜索树的实现方法，结果都是一样的？都是为了 O(\log N) 的搜索时间复杂度
1 Like
哦，b 树可以做操作系统的文件索引和数据库索引，酷
渐进时间复杂度一样，但实际应用的时候并不是只看大 O 复杂度的。比如说
- 红黑树不是严格平衡，这会导致它每次操作的时间不完全稳定（虽然这个影响比较小），极少数情况下会被人挑毛病
- AVL 实现起来一般比较麻烦，导致大多数 AVL 实现的时间常数都比较大。以至于虽然理论上它是严格平衡（稳定）的，但实际上大家经常嫌麻烦（不想写）或者嫌常数太大（慢好多）
更不严格的平衡二叉搜索树 Splay 甚至是均摊 O(log N) 复杂度的，也就是可能出现有的操作非常慢而有的非常快这种现象。感觉公司里搞开发的时候就不喜欢用 Splay，只是竞赛选手刷题的时候还比较常见。
3 Likes
21sp 的 lab2 有几个 hidden test 过不了，如果我写的测试用例都能通过，我要怎么找 bug 呢
hidden test 就是考验你自己找问题的时候了（
test case 可能不够全面，可能有些 marginal case 没有照顾到
找到几个 bug 了，现在正在被 Velocity Limiting 折磨
两月之期已到，然而才学到二叉树和搜索，后面还有图与字符串。这几天光看人类简史和微软 semantic kernel 的文档了。
把 B 树的视频投了，做这个太麻烦了，我在思考自动化生产视频
今天在 ISO C++ 群看到 B 树视频了
恭喜，本站第一个用户网红
我就是因为 CS61abc 的群里有个位置陕西西安 19 岁的二次元头像用户转发了你的新 B 站视频，所以导致我开盒失败