10-Day3.md

第三次课程小结

1. 经典排序算法

• 快速排序：不稳定，一般情况下复杂度为O(nlogn)。

• 桶排序：复杂度可以达到O(n)，但较差情况下退化到O(nlogn)。

• 基排序：原理是基于桶排序的改进。

2. 数据结构

• 二叉搜索树：主要讲了对数据的搜索、插入和删除操作。但当树不平衡时会导致复杂度恶化。

• 2-3-4树：平衡树结构，效率较高属于多叉树，因此一个节点的子树和键值存在多个。

• 红黑树：属于二叉搜索树，但节点具有颜色；主要特点是对任意节点，其到叶子节点树尾端的每一条路径都有相同数目的黑色节点。主要介绍了对红黑树的旋转、插入和删除操作。