时间复杂度

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，进而分析f(n)随n的变 化情况并确定T(n)的数量级。这里用”O”来表示数量级，
给出算法的时间复杂度。

T(n)=O(f(n));

它表示随着问题规模的n的增大，算法的执行时间的增长率和f(n)的增长率相同，这称作算法的渐进时间复杂度，简称时间复杂度。

算法定义

快速排序采用”分而治之”的思想，通过选择基准值（pivot）将数组分为两部分，左边小于基准值，右边大于基准值，然后递归处理两个子数组。

算法步骤

先选择基准值pivot，一般情况下选择第一个或最后一个，步骤如下：

定义

线性表（Linear List）是具有相同特性的数据元素的一个有限序列。该序列中所含元素的个数叫做线性表的长度，用n表示，n>=0。当n=0时，表示线性表是一个
空表。设序列中第i个元素为a₁（1 ≤ i ≤ n），则线性表的一般表示为：

(a₁,a₂,a₃,…,a_i,…,a_n)

特性

定义

冒泡排序（Bubble Sort）是一种简单的排序算法，它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢 “浮” 到数列的顶端。
算法步骤

定义

平衡二叉树也叫自平衡二叉搜索树（Self-Balancing Binary Search Tree），所以其本质也是一颗二叉搜索树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树（旋转操作）。

最小失衡子树：在新插入的结点向上查找，以第一个平衡因子的绝对值超过1的结点为根的子树称为最小不平衡子树。也就是说，一棵失衡的树，是有可能有多棵子树同时失衡的。而这个时候，我们只要调整最小的不平衡子树，就能够将不平衡的树调整为平衡的树。Ï

平衡二叉树的失衡调整主要是通过旋转最小失衡子树来实现的。根据旋转的方向有两种处理方式，左旋与右旋。

旋转的目的就是减少高度，通过降低整棵树的高度来平衡。哪边的树高，就把那边的树向上旋转。

左旋