数据结构

flowchart LR
    A[数据结构] --> B(线性结构)
    B --> B1(线性表)
    B --> B2(栈和队列)
    B --> B3(串)
    A --> C(数组、矩阵、广义表)
    A --> E(树)
    A --> F(图)
    A --> G(查找)
    A --> H(查找)

程序 = 数据结构 + 算法

线性结构：每个元素最多只有一个出度和一个入度,表现为一条线状。
线性表按存储方式分为：
1.顺序表
2.链表

存储结构：
顺序结构：用一组地址连续的存储单元,依次存储线性表中的数据元素,使得逻辑上相邻的元素物理上也相邻。
链式存储：存储个数据元素的结点的地址并不要求是连续的,数据元素逻辑上相邻,物理上分开

顺序存储和链式存储区别

性能类别	具体项目	顺序存储	链式存储
空间性能	存储密度	=1,最优	<1
空间性能	容量分配	事先确定	动态改变,更优
时间性能	查找运算	O(n/2)	O(n)
时间性能	读运算	O(1),更优	O(n)
时间性能	插入运算	O(n)	O(1),更优
时间性能	删除运算	O(n)	O(1),更优

在空间方面,因为链表还需要存储指针,因此有空间浪费存在,
在时间方面,当需要对元素进行破坏性能操作（插入、删除）时,链表效率更高,因为只需要修改指针指向即可。
而顺序表是因为地址是连续的,当删除或插入时,后面其他结点位置都需要变动。
而当读取,查找时,顺序表效率更高,因为物理地址是连续的,而链表需要从头结点开始,一个个的查找下去。

栈和队列

栈和队列也是线性结构。
队列是先进先出（FIFO）,分队头和对尾
栈是先进后出（FILO）只有栈顶能进出

循环队列公式
对空条件：head = tail
队满条件：(tail + 1) % size = head
优先队列：
元素被赋予优先级,当访问元素时,具有最高优先级的元素最先删除,使用堆来存储是因为其不是按照元素队列的顺序决定的

例：
某双端队列要求元素进出序列必须在同一端口,从A进从A出,从B进从B出,对于e1、e2、e3、e4,
要求e1、e2从A进,e3、e4从B进则可能得到的出队序列是：
e2 > e1 , e4 > e3

例：
从S出栈后立即进入队列Q,若出队的序列是b、d、f、e、c、a,则S中元素最多时,栈底到栈顶的元素依次为

例：3个元素依次进栈,能得到？种不同的出栈序列

ABC：A 进栈 -> A 出栈；B 进栈 -> B 出栈；C 进栈 -> C 出栈。
ACB：A 进栈 -> A 出栈；B 进栈；C 进栈 -> C 出栈；B 出栈。
BAC：A 进栈；B 进栈 -> B 出栈；A 出栈；C 进栈 -> C 出栈。
BCA：A 进栈；B 进栈 -> B 出栈；C 进栈 -> C 出栈；A 出栈。
CBA：A 进栈；B 进栈；C 进栈 -> C 出栈；B 出栈；A 出栈。

例：利用栈对算术表达式 10*(40-30/5)+20 求值时,存放操作数的栈（初始为空）的容量至少要为？

= 30 5 /
= 40 30 5 / -
= 10 40 30 5 / - *
= 10 40 30 5 / - * 20 +
这类题目可以先将算术表达式转成后缀式,然后看第一个算术符号前有多少个数字,即可得出存放操作数得容量至少为多少。

串

字符串是一种特殊的线性表,其数据元素都分字符

空串：长度为0的字符串,没有任何字符
空格串：由一个或多个空格组成的串,空格时空白字符,占一个字符长度。
字串：串中任意长度的连续字符构成序列称为子串。含有子串的串称为主串,空串是任意串的子串。

数组结构

数组是定长线性表在维度上的扩展,即线性表中又是一个线性表。
n维数组是一种同构的数据结构,其中每个数据元素类型相同,结构一致

一个m行n列的数组表示如下：

flowchart LR
    A[Am*n] --> B(a1)
    B --> B1(a2)
    B1 --> B2(a3)
    B2 --> B3(an)
    A --> C(a11)
    C --> C1(a12)
    C1 --> C2(a13)
    C2 --> C3(a1n)
    A --> D(am1)
    D --> D1(am2)
    D1 --> D2(am3)
    D2 --> D3(amn)

其可以表示为行向量形式或者列向量形式线性表,单个关系最多只有一个前驱和一个后继,本质还是线性的。
数组结构特点：数据元素数目固定；数据元素类型相同；数据元素的下表关系具有上下界的约束且下标是有序的。
数组数据元素固定,一般不做插入和删除运算,适合采用顺序结构

数组存储地址的计算,特别是二维数组,要注意理解,
假设每个数组元素占用存储长度为len,起始地址为a,存储的地址如下：
一维数组a[n],a[i]的存储地址为：a + i * len
注意：len 表示每个元素占用的字节

例：arr[4] = { 1, 2, 3, 4 }
arr = OX1000, len = 4 , i = 2时
= OX1000 + 2 * 4
= OX1008

二维数组a[m][n] ,a[i][j]的存储地址：
按行：a + (i * n + j) * len
按列：a + (j * m + i) * len
行优先时：n = 每行的列数
列优先时：m = 每列的行数
例：按行计算arr[2][3]
= OX1000 + (2 * 4 + 3) * 4
= OX1000 + 44
= OX1044

例：按列计算arr[2][3]

= OX1000 + (3 * 3 + 2) * 4
= OX1000 + 44
= OX1044

矩阵结构

特殊矩阵：
矩阵中的元素（或非0元素）的分布有一定规律,常见的特殊矩阵有对称矩阵、三角矩阵、对角矩阵
稀疏矩阵：
在一个矩阵中,若非零元素的个数远远少于零元素个数,且非零元素的分布没有规律

存储方式为三元组结构,即存储每个非零元素的（行、列、值）

例：某n阶的三对角矩阵A,按行将元素存储在一维数组中M,设a1,1
存储在M[1],那么ai,j 存储在M[2i + j -2]
取特殊值
a1,1 -> i = 1, j = 1 , = 1
a1,2 -> i = 1, j = 2 , = 2
代入答案公式

广义表

是线性表的推广,是由0个或多个单元素或子表组成的有限序列。
广义表与线性表的区别：线性表的元素都是结构上不可分的单元素,而广义表的元素即可以单元素,也可以是有结构的表。
一般记为：LS = (a1,a2, .... , an)

树

双亲,孩子和兄弟：结点子树的根称为该结点的孩子,该结点称为子节点的双亲。
结点的度：一个阶段的子树的个数记为该结点的度。
叶子节点：叶子结点也称为终端结点。指度为0的结点。
内部节点：度不为0的结点,也称为分支节点或非终端结点。除根结点以外,分支结点也称为内部节点。
结点的层次：根为第一层,根的孩子为第二层,以此类推,若其结点在底层,则其孩子结点在i + 1层。
树有高度：一棵树的最大层数记为树的高度或深度。
有序（无序树）：若将树中结点的各子树看成是从左到右具有次序的,即不能交换,则称该树为有序树,否则为无序树。

树结构是一种非线性结构,树中的每一个元素可以有两个或两个以上的直接后继元素,用来描述层次结构关系
树是n个结点的有限集合 n >= 0,当n = 0时为空树,在任一颗非空树中,有且仅有一个根节点；
其余结点可分为m( m >= 0)个互不相交的有限子集T1,T1,…..,Tm,其中每一个Ti又是一棵树,并且可以成为根节点的子树。

二叉树

是n个结点的有限集合,它或者是空树,或者由一个根节点及两颗互补相交的且分别称为左、右子树的二叉树所组成。
与树的区别在于每个根节点最多只有两个孩子节点。

满二叉树：每层都是满节点的
完全二叉树：k - 1层是满结点的,第k层从左到右是满的
非完全二叉树：k - 1层是满结点的,第k层从左到右有空结点

二叉树的存储结构

顺序存储结构：
顺序存储,就是用一组连续的存储单元,存储二叉树中的结点,按照从上到下,从左到右的顺序依次存储每个结点。
链式存储结构：
一般用二叉链表来存储二叉树结点,二叉链表中除了该结点本身的数据外,还存左孩子的指针、右孩子的指针,
即一个数据 + 两个指针。每个二叉链表节点存储一个二叉树结点。
头指针则指向根节点。

二叉树的遍历

一颗非空的二叉树由根结点,左子树、右子树三部分组成。
遍历的基本顺序是先左子树后右子树

三种遍历方式：

先序（前序）遍历：根左右
中序遍历：左根右
后序遍历：左右根

层次遍历

从上到下
从左到右

例：先序 = 1 2 4 5 7 8 3 6,中序 = 4 2 7 8 5 1 3 6,后续 = ？ 4 7 8 5 2 6 3 1

例：在一颗满二叉树中,对于编号为m和n的两个结点,若n = 2m + 1,
若m = 1 , n = 2 * 1 + 1 = 3,则n是m的右孩子

例：该树的大小至少为？15
若用三叉链表来表示该二叉树,则所有结点的空指针应为？8

线索二叉树

引入线索二叉树是为了保存二叉树遍历时某节点的前驱节点和后继节点的信息,
二叉树的链式储存只能获取到某个节点的左孩节点和右孩节点,无法获取其遍历时前驱和后继节点,
因此可以在链式存储再加两个指域使其分别指向前驱和后继节点。

但这样太浪费空间,考虑到若n个节点的二叉树使用二叉链表存储,则必然有n + 1个空指针域,
利用空指针域来存放前驱和后继节点的信息。

最优二叉树

又称哈夫曼树,是一类带权路径长度最短的树

WPL = 2 * (2 + 4 + 5 + 7) = 36

WPL = ? (7 * 1) + (5 * 2) + (2+4) * 3 = 35

哈夫曼树的求法：给出一组权值将其中两个最小的权值作为叶子节点,其和作为父节点,
组成二叉树,而后删除这两个叶子节点权值并将父节点的值添加到该组权值中。

例：f:5,e:9,d:16,c:12,b:13,a:45

例：画出哈夫曼树：

例：bee的编码是？101 1101 1101

例：110001001101编码对应的字符为？face

查找二叉树

查找二叉树上的每个节点都存储一个值,且每个节点的左孩子结点值都小于父节点值,
而所有右孩子节点值都大于父节点值,是一个有规律排列的二叉树,这种数据结构可以方便查找、插入等操作。

二叉排序树的查找效率取决于二叉排序的深度,对于节点个数相同的二叉排序树,平衡二叉树的深度最小,而单枝树的深度是最大的,故效率最差。

平衡二叉树

平衡二叉树就是任意左右子树层次相差不超过1
例：某二叉树的先序遍历为 c,a,b,f,e,d,g 中序遍历为 a,b,c,d,e,f,g 后续遍历是？badegfc
则二叉树是？![](https://javahna.oss-cn-shanghai.aliyuncs.com/rjsjs/14.png)

图

图也是一种非线性结构,图中任意两个节点间都可能有直接关系：相关定义如下：

无向图：图的节点之间连接线是没有箭头的,不分方向。
有向图：图的节点之间连接线是箭头,区分A到B,和B到A是两条线。
完全图：无向完全图中,节点两两之间都有连线,n个节点的连线树为（n-1）+(n-2)+…..+1 = n * (n - 1) / 2;
有向完全图中,节点两两之间都有互通的两个箭头,n个节点的连线树为n*(n-1)
度、出度、入度：顶点的度是关联与该顶点的边的数目。在有向图中,顶点的度为出度和入度之和。
出度是以该顶点为起点的有向边的数目。
入度是以该顶点为终点的有向边的数目。
路径：存在一条通路,可以从一个顶点到达另一个顶点,有向图的路径也是有方向的。
连通图和连通分量：针对无向图。若从顶点v到顶点u之间是有路径的,则说明v和u之间是连通的,若无向图中任意两个顶点之间都是连通的,则称为连通图。
强连通图的强连通分量：针对有向图。若有向图任意两个顶点间都互相存在路径,则称为强连通图。有向图中的极大联通子图称为其强连通分量。
网：边带权值的图称为网。

图的存储

邻接矩阵：使用二维数组来表示图中节点之间的连接关系

第i行和第j列的元素表示节点i和节点j之间是否有连接。
空间复杂度较高,但查找连接关系效率高。
当图比较密集时,邻接矩阵更好

邻接链表：用到了两个数据结构,先用一个一维数组将图中所有顶点存储起来,而后,对此一维数组的每个顶点元素,使用链表挂上和其有连线关系的节点的编号和权值。
空间复杂度较低,增加节点效率高,但查找连接效率低,当图较稀疏时,邻接链表更好

完全图适合采用邻接矩阵存储

图的遍历

图的遍历是指从图的任意节点除法,沿着某条搜索路径对图中所有节点进行访问且只访问一次,分为以下两种方式：

深度优先遍历：从任一顶点出发,遍历到底,直至返回,再选取任一其他节点除法,重复这个过程直至遍历完成整个图；
广度优先遍历：先访问完一个顶点的所有邻接顶点,而后再依次访问其邻接顶点的所有邻接顶点,类似于层次遍历。

图的最小生成树

假设有n个节点,那么这个图的最小生成树有n-1条边（不会形成环路,是非树图）,这n-1条边会将所有顶点都连接成一个树,并且这些边的权值之和最小,因此称为最小生成树。

普里姆算法(Prim)：从任意顶点出发,找出与其邻接的边权值最小的,此时此边的另外一个顶点自动加入树的集合中,
而后再从这个树集合的所有顶点中找出与其邻接的边权值最小的,同样此边的另外一个顶点加入树集合中,依次递归,
直至图中所有顶点都加入树集合中,此时此树就是该图的最小生成树。
克鲁斯卡尔算法(Kruscal,推荐)：这个算法是从边出发的,因为本质是选取权值最小的n-1条边,
因此,就将边按权值大小排序,依次选取权值最小的边,直至囊括所有节点,要注意,每次选边后要检查不能形成环路。

这两钟算法都是局部最优原则,所以都是贪心法算法,并没有谁的效率高谁的效率差,因为克鲁斯卡尔算法是数边的,所以边越多,它算起来越麻烦。
若网比较稠密,则Prim算法比较好

图的拓扑序列

AOV网(以顶点表示活动的网)：在有向图中,以顶点表示活动,用有向边表示活动之间的优先关系。
AOV网用来表示大的工程项目执行计划,因此不能出现有向环,若存在,则意味着某项活动必须以自身任务的完成为先决条件,
因此,若要检测一个工程是否可行,首先应检查对应的AOV网是否存在回路。检测的方法是对有向图构造其顶点的拓扑有序序列。

构造方法：将有向图的有向边作为活动开始的顺序,若图中一个节点入度为0,则应该最先执行此活动,而后删除掉此节点和其关联的有向边,
再去找图中其他没有入度的结点,执行活动,依次进行,示例如下：

例：拓扑排序是将有向图中所有顶点排成一个线性序列的过程,并且该序列满足：若在AOV网中从顶点Vi到Vj有一条路径,
则顶点Vi必然在顶点Vj之前。对于所示的有向图,其拓扑序列为：？

A：1234576 B：1235467 C：2135476 D：2134567

算法

算法基础

算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个操作。
简单的说算法就是某个问题的解题思路,算法的五个重要特性如下：

有穷性。一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束,且每一步都可在有穷时间内完成。
确定性。算法中的每一条指令必须有确切的含义,理解时不会产生二义性。
并且在任何条件下,算法只有唯一的一条执行路径,即对于相同的输入只能得出相同的输出。
可行性。一个算法是可行的,即算法中描述的操作都可以通过已经实现的基本运算执行有限次数来实现。
输入。一个算法有零个或多个输入,这些输入取自于某个特定的对象的集合。
输出。一个算法有一个或多个输出,这些输出是同输入有着某些特定关系的量。

算法的复杂度：

时间复杂度是指程序运行从开始到结束所需要的时间。
空间复杂度是指对一个算法在运行过程中临时占用存储空间大小的度量。
一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小。

常见的对算法执行所需时间的度量：O(1) < O(log 2^n) < O(n) < O(n log 2^n) < O(n^2) < O(n^3) < O(n^n) < O(n!)

上述的时间复杂度,经常考到,需要注意的是,时间复杂度是一个大概的规模表示,一般以循环次数表示,
O(n)说明执行时间是n的正比,另外,log对数的时间复杂度一般在二叉树的算法中出现。渐进符号O表示一个渐进变化程度,实际变化必须小于等于O括号内的渐进变化程度。

查找

顺序查找：将待查找的关键字为key的元素从头到尾与表中元素进行比较,如果中间存在关键字为key的元素,
则返回成功；否则,则查找失败。时间复杂度为O(n)。

折半(二分)查找：设查找表的元素存储在一堆数组r[1..n]中,在表中元素已经按照关键字递增方式排序的情况下,
进行折半查找的方法是：

首先将待查元素的关键字(key)值与表r中间位置（下表为mid）记录的关键字进行比较,若相等,则查找成功；
若key > r[mid].key,则说明待查记录只可能在后半个子表r[mid+1..n]中,下一步在后半个子表中查找；
若key < r[mid].key,说明待查记录只可能在前半个子表r[1.mid-1]中,下一步应在r的前半个子表中查找；
重复上述步骤,逐步缩小范围,直到查找成功或子表为空失败时为止。

要注意两点：中间值位置求出若为小数,应该向下取整,即4.5=4,非四舍五入；中间值已经比较过不相等,在划分下一次比较区间时,
无须将中间值位置再纳入下一次比较区间。当查找的数据越多时,二分查找的效率越高。

折半查找的时间复杂度为O(log 2^n)

前面的查找方法,由于记录在存储结构中的相对位置是随机的,所以查找时都要通过一系列与关键字的比较才能确定被查记录在表中的位置。
也就是说,这类查找都是以关键字的比较为基础的,而哈希表则通过一个以记录的关键字为自变量的函数（称为哈希函数）得到该记录的存储地址,
所以在哈希表中进行查找操作时,需要用同一哈希函数计算得到待查记录的存储地址,然后到相应的存储单元去获得有关信息再判定查找是否成功。

散列(哈希)表：根据设定得哈希函数H(key)和处理冲突的方法,将一组关键字映射到一个有限的连续的地址集上,
并以关键字在地址集中的“像”作为记录在表中的位置。

在上图中,很明显,哈希函数产生了冲突,使用的是线性探测法解决冲突,还有其他方法如下：

线性探测法：按物理地址顺序取下一个空闲的存储空间。
伪随机数法：将冲突的数据随机存入任意空闲的地址中。
再散列法：原有的散列函数冲突后,继续用此数据计算另外一个哈希函数,用以解决冲突。

例：在13个元素构成的有序表M[1..13]中进行折半查找(向下取整),若找到的元素为M[4],则被比较的元素依次为：？

(1+13) / 2 = 7, M[4] < M[7] 缩小到左半区,即M[1..6]
(1+6) / 2 = 3, 向下取整 = M[4] > M[3] 缩小到右半区,即M[4..6]
(4+6) / 2 = 5, M[5] > M[4] 查找范围缩小到M[4]
即 M[7],M[3],M[5],M[4]

例：以下关于哈希(Hash,散列)查找叙述中,正确的是构造哈希函数时应尽量使关键字的所有组成部分都能起作用

例：以下关于散列表(哈希表),即其查找特点的叙述中,正确的是用线性探测法解决冲突容易产生聚集问题

例：对某有序表进行折半查找(二分查找)时,进行比较的关键字序列不可能是?
A.42,61,90,85,77
B.42,90,85,61,77
C.90,85,61,77,42
D.90,85,77,61,42

答案：C

排序

术语说明

稳定：如果a原本在b前面,而a=b,排序之后a任然在b的前面。
不稳定：如果a原本在b前面,而a=b,排序之后a可能会出现在b的后面。
In-place：占用常数内存,不占用额外内存。
Out-place：不仅占用常数内存,还需要占用额外内存。
时间复杂度：一个算法执行所耗费的时间。
空间复杂度：运行完一个程序所需内存的大小。

排序的算法有很多,大致可以分类如下：

插入类排序：直接插入排序,希尔排序。
交换类排序：冒泡排序、快速排序。
选择类排序：简单选择排序、堆排序。
归并排序。
基数排序。

插入排序

直接插入排序是一种简单的排序方法,具体做法是：在插入第i个关键码时k1,k2,…,ki-1已经排好序,
这时将关键码ki依次与关键码ki-1,ki-2等进行比较,找到ki应该插入的位置停下来,将插入位置及其后的关键码依次向后移动,然后插入ki。

要注意的是,前提条件是前i-1个元素是有序的,第i个元素依次从第i-1个元素往前比较,直到找到一个比第i个元素值小的元素,而后插入,
插入位置及其后的元素依次向后移动,本质是插入排序。

public static void main(String[] args) {
        // 直接插入排序
        int[] arr = {20, 50, 15, 76, 46, 7, 41};

        for (int i = 1; i < arr.length; i++) {
            // 当前选择的值
            int changeValue = arr[i];
            // 待移动的位置
            int j = i - 1;

            // 将大于changeValue的所有元素向右移动一位
            while (j >= 0 && arr[j] > changeValue) {
                arr[j + 1] = arr[j];
                j--;
            }

            // 在正确的位置插入changeValue
            arr[j + 1] = changeValue;
        }

        // 打印排序后的数组
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

希尔排序

希尔排序的基本思想是：先将整个待排记录序列分割成若干子序列,然后分别进行直接插入排序,
待整个序列中的记录基本有序时,再对全体记录进行依次直接插入序列。
具体的做法是：
先取一个小于的正数d1作为第一个增量,把文件的全部记录分成d1个组,即将所有距离为d1倍数序号的记录放在同一个组中,
在各组内进行直接插入排序：然后取第二个增量d2(d2<d1),重复上述分组和排序工作,以此类推,
直到所取的增量di=1(di<di-1<….<d2<d1),即所有记录放在同一组进行直接插入排序为止。

希尔排序是对直接插入排序算法的改进,适合于大数据的排序,采用分组的方法,可以提高效率。

例：对数组 arr = {20, 54, 63, 14, 8, 48, 46, 22, 78, 47, 55, 66} 进行希尔排序

选择增量序列
初始增量 h = n / 2= 6
增量序列 6,3,1
分组排序
增量h = 6
将数组分成6个子序列,对每个子序列进行插入排序：
子序列1：20,46 –>已有序
子序列2：54,22 –>22,54
子序列3：63,78 –>已有序
子序列4：14,47 –>已有序
子序列5：8,55 –>已有序
子序列6：48,66 –>已有序
排序后的数组：20,22,63,14,8,48,46,54,78,47,55,66
分组排序
增量h = 3
将数组分成3个子序列,对每个子序列进行插入排序：
子序列1：20,14,46,47 –> 14,20,46,47
子序列2：22,8,54,55 –> 8,22,54,55
子序列3：63,48,78,66 –> 48,63,66,78
排序后的数组 14,8,48,20,22,63,48,54,66,47,55,78
分组排序
增量h = 1
对整个数组进行插入排序：
从第二个元素开始,逐个将元素插入到前面已排序的部分。
排序后的数组：
8,14,20,22,46,47,48,54,55,63,66,78

public static void main(String[] args) {
        // 希尔排序
        int[] arr = {20, 54, 63, 14, 8, 48, 46, 22, 78, 47, 55, 66};
        int n = arr.length;
        int index = 1;
        // 初始增量 h = n/2,逐步缩小增量 即6,3,1
        for (int h = n / 2; h > 0; h /= 2) {
            // 对每个子序列进行插入排序
            for (int i = h; i < n; i++) {
                int temp = arr[i]; // 当前需要插入的元素
                int j;
                // 举例 h = 6 时, i = 6 , j = 6;   arr[6 - 6] 即 arr[0]和arr[6]比较
                // 举例 h = 6 时, i = 7 , j = 7;   arr[7 - 6] 即 arr[1]和arr[7]比较
                // 举例 h = 3 时, i = 4 , j = 4;   arr[4 - 3] 即 arr[1]和arr[4]比较
                // 举例 h = 3 时, i = 8 , j = 8;   arr[8 - 3] 即 arr[5]和arr[8]比较
                // h = 1时,即全数组进行插入排序
                // 举例 h = 1 时, i = 1 , j = 1;   arr[1 - 1] 即 arr[0]和arr[1]比较
                // 举例 h = 1 时, i = 2 , j = 2;   arr[2 - 1] 即 arr[1]和arr[2]比较
                // 比 temp 大的元素向后移动,为 temp 腾出插入位置
                for (j = i; j >= h && arr[j - h] > temp; j -= h) {
                    arr[j] = arr[j - h];
                }
                // 插入 temp 到正确的位置
                arr[j] = temp;
            }
            System.out.print(index+"排序后的数组:");
            for (int i : arr) {
                System.out.print(i + " ");
            }
            System.out.println();
            index++;
        }
    }

简单选择排序

n个记录进行简单选择排序的基本方法是：通过n-1(1 <= i <= n)在次关键字之间的比较,从n-i+1个记录中选出关键字最小的记录,
选出关键字最小的记录,并和第i个记录进行交换,当i等于n时所有记录有序排列。

本质就是每次选择出最小的元素进行交换,主要是选择过程,最值的交换过程只有一次。示例如下：

例：以数组 int[] arr = {20, 54, 63, 14, 8} 为例,详细讲解简单选择排序的执行过程：

选择最小元素
- 未排序部分：20, 54, 63, 14, 8
- 找到最小元素：8,将8与未排序部分第一个元素20进行交换
- 交换完数组 8, 54, 63, 14, 20
- 已排序部分：8
- 未排序部分：54, 63, 14, 20
选择最小元素
- 未排序部分：54, 63, 14, 20
- 找到最小元素：14,将14与未排序部分第一个元素54进行交换
- 交换完数组 8, 14, 63, 54, 20
- 已排序部分：8, 14
- 未排序部分：63, 54, 20
选择最小元素
- 未排序部分：63, 54, 20,
- 找到最小元素：20,将20与未排序部分第一个元素63进行交换,
- 交换完数组 8, 14, 20, 54, 63
- 已排序部分：8, 14, 20
- 未排序部分：54, 63
选择最小元素
- 未排序部分：54, 63
- 找到最小元素54,已经是未排序部分的第一个元素,无需交换。
- 已排序部分：8, 14, 20, 54
- 未排序部分：63
选择最小元素
- 未排序部分：63
- 找到最小元素63,已经是未排序部分的第一个元素,无需交换。
- 已排序部分：8, 14, 20, 54, 63

public static void main(String[] args) {
        // 简单选择排序
        int[] arr = {20, 54, 63, 14, 8};
        int n = arr.length;
        // 遍历数组
        for (int i = 0; i < n - 1; i++) {
            // 找到未排序部分的最小元素
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j; // 更新最小元素的索引
                }
            }

            // 将最小元素与未排序部分的第一个元素交换
            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }

            // 打印每次排序后的数组状态
            System.out.print("第 " + (i + 1) + " 次排序后的数组: ");
            for (int num : arr) {
                System.out.print(num + " ");
            }
            System.out.println();
        }
    }

堆排序

堆排序(Heapsort) 是指利用堆这种数据结构所设计的一种排序算法。
堆积是一个近似完全二叉树的结构,并同时满足堆积的性质：即子节点的健值或索引总是小于(或者大于)它的父节点

堆排序的方法可分为两步:

依据给出的待排序关键字建立初始堆,如果是升序就是小顶堆,降序就是大顶堆。
把最后一个元素输入到堆顶,并调整堆。重复上述步骤。

堆排序的核心公式

父节点和子节点的关系(对于一个节点i)：
- 父节点索引：(i - 1) / 2
- 左子节点索引：2 * i + 1
- 右子节点索引：2 * i + 2
调整堆的算法(Heapify)
从当前节点i开始,找到其左右子节点中最大的节点。
如果当前节点的值小于最大节点的值,则交换。
递归调整受影响的子树。
堆排序的算法：
构建堆：从最后一个非叶子节点开始,逐步向上调整堆。
排序：将堆顶元素与堆的最后一个元素交换,并调整堆。

例：[1, 3, 4, 5, 7, 2, 6, 8, 0]

构建大顶堆
1. 找到最后一个非叶子节点：
  - 数组长度为n = 9,最后一个非叶子节点的索引为(n / 2) - 1 = 3（值为 5）。
2. 从索引3(值5)开始调整堆：
  - 左子节点索引： 2 * 3 + 1 = 7(值8)
  - 右子节点索引： 2 * 3 + 2 = 8(值0)
  - 最大子节点是8(索引7)
  - 索引3的值小于最大子节点,交换5和8(即索引3和索引7)
  - 交换后数组：[1, 3, 4, 8, 7, 2, 6, 5, 0]
  - 2 * 7 + 1 或者 2 * 7 + 2 >= 9 不再继续
3. 调整索引2(值4)：
  - 左子节点索引： 2 * 2 + 1 = 5(值2)
  - 右子节点索引： 2 * 2 + 2 = 6(值6)
  - 最大子节点是6(索引6)
  - 索引2的值小于最大子节点,交换4和6(即索引2和索引6)
  - 交换后数组：[1, 3, 6, 8, 7, 2, 4, 5, 0]
  - 2 * 6 + 1 或者 2 * 6 + 2 >= 9 不再继续
4. 调整索引1(值3)：
  - 左子节点索引： 2 * 1 + 1 = 3(值8)
  - 右子节点索引： 2 * 1 + 2 = 4(值7)
  - 最大子节点是8(索引3)
  - 索引1的值小于最大子节点,交换3和8(即索引1和索引3)
  - 交换后数组：[1, 8, 6, 3, 7, 2, 4, 5, 0]
  - 2 * 3 + 1 或者 2 * 3 + 2 < 9 继续
  - 左子节点索引：2 * 3 + 1 = 7(值5)
  - 右子节点索引：2 * 3 + 2 = 8(值0)
  - 索引3的值小于最大子节点,交换3和5(即索引3和索引7)
  - 交换后数组：[1, 8, 6, 5, 7, 2, 4, 3, 0]
  - 2 * 7 + 1 或者 2 * 7 + 2 >= 9 不再继续
5. 调整索引0(值1)：
  - 左子节点索引： 2 * 0 + 1 = 1(值8)
  - 右子节点索引： 2 * 0 + 2 = 2(值6)
  - 最大子节点是8(索引1)
  - 索引0的值小于最大子节点,交换1和8(即索引0和索引1)
  - 交换后数组：[8, 1, 6, 5, 7, 2, 4, 3, 0]
  - 2 * 1 + 1 或者 2 * 1 + 2 < 9 继续
  - 左子节点索引：2 * 1 + 1 = 3(值5)
  - 右子节点索引：2 * 1 + 2 = 4(值7)
  - 索引1的值小于最大子节点,交换1和7(即索引1和索引4)
  - 交换后数组：[8, 7, 6, 5, 1, 2, 4, 3, 0]
  - 2 * 4 + 1 或者 *2 * 4 + 2 >= 9 *不再继续
6. 构建完成后的大顶堆：[8, 7, 6, 5, 1, 2, 4, 3, 0]
排序：
1. 交换：
  - 交换堆顶元素8和堆的最后一个元素0.
  - 交换后数组:[0, 7, 6, 5, 1, 2, 4, 3, 8]
  - 排除8,重新调整堆：[0, 7, 6, 5, 1, 2, 4, 3]
2. 从对顶开始调整堆,索引0(值0)：
  - 左子节点索引: 2 * 0 + 1 = 1(值7)
  - 右子节点索引: 2 * 0 + 2 = 2(值6)
  - 索引0的值小于最大子节点,交换0和7(即索引0和索引1)
  - 交换后数组：[7, 0, 6, 5, 1, 2, 4, 3]
  - 2 * 1 + 1 或者 2 * 1 + 2 < 9 继续
  - 左子节点索引: 2 * 1 + 1 = 3(值5)
  - 右子节点索引: 2 * 1 + 2 = 4(值1)
  - 索引1的值小于最大子节点,交换0和5(即索引1和索引3)
  - 交换后数组：[7, 5, 6, 0, 1, 2, 4, 3]
  - 2 * 3 + 1 或者 2 * 3 + 2 < 9 继续
  - 左子节点索引: 2 * 3 + 1 = 7(值4)
  - 右子节点索引: 2 * 3 + 2 = 8(值3)
  - 索引3的值小于最大子节点,交换0和4(即索引3和索引8)
  - 交换后数组：[7, 5, 6, 3, 1, 2, 4, 0]
3. 重复上述过程,直到堆中只剩一个元素

补充说明:

调整堆的过程：在调整堆的过程中,如果某个节点的值小于其子节点的值,需要将该节点与其较大的子节点交换,
并继续向下调整,直到该节点满足大顶堆的性质。
堆排序的时间复杂度：堆排序的时间复杂度为 O(n log n),其中 n 是数组的长度,构建堆的时间复杂度为 O(n),
每次调整堆的时间复杂度为 O(log n),总共需要进行 n-1 次调整。
堆排序的空间复杂度：堆排序是原地排序算法,空间复杂度为 O(1)。

// 堆排序的实现
public static void heapSort(int[] arr) {
    int n = arr.length;

    System.out.println("初始数组:");
    printArray(arr);

    // 构建大顶堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    System.out.println("构建大顶堆的数组:");
    printArray(arr);

    int index = 1;
    // 排序
    for (int i = n - 1; i > 0; i--) {
        // 将堆顶元素与堆的最后一个元素交换
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // 重新调整堆
        heapify(arr, i, 0);

        System.out.println(index+"次排序的数组:");
        printArray(arr);
        index ++;
    }
}

// 调整堆
public static void heapify(int[] arr, int n, int i) {
    int largest = i; // 初始化最大值的索引
    int left = 2 * i + 1; // 左子节点
    int right = 2 * i + 2; // 右子节点

    // 如果左子节点大于根节点
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    // 如果右子节点大于根节点
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    // 如果最大值不是根节点
    if (largest != i) {
        int swap = arr[i];
        arr[i] = arr[largest];
        arr[largest] = swap;

        // 递归调整受影响的子树
        heapify(arr, n, largest);
    }
}

// 测试代码
public static void main(String[] args) {
    int[] arr = {1, 3, 4, 5, 7, 2, 6, 8, 0};
    heapSort(arr);
}

堆排序适合用于在多个元素中找出前几名的方案设计,因为堆排序是选择排序,而且选择出前几名的概率很高。

冒泡排序

冒泡排序（Bubble Sort）是一种简单的排序算法,它通过重复地遍历数组,
比较相邻元素并交换它们的位置来排序。每一轮遍历都会将当前未排序部分的最大值冒泡到正确的位置。

冒泡排序的步骤

比较相邻元素：从数组的第一个元素开始,依次比较相邻的两个元素。
交换位置：如果前一个元素比后一个元素大,则交换它们的位置。
重复遍历：每一轮遍历都会将当前未排序部分的最大值放到正确的位置。
终止条件：当某一轮遍历没有发生任何交换时,说明数组已经有序,排序结束。

例： int[] arr = {12, 7, 45, 64, 26} 进行冒泡排序

第一轮遍历
- 比较 12 和 7,12 > 7,交换
- [7, 12, 45, 64, 26]
- 比较 12 和 45,12 < 45,不交换。
- 比较 45 和 64,45 < 64,不交换。
- 比较 64 和 26,64 > 26,交换：
- [7, 12, 45, 26, 64]
- 第一轮结束后,最大值 64 已经放到正确的位置。
第二轮遍历
- 比较 7 和 12,7 < 12,不交换。
- 比较 12 和 45,12 < 45,不交换。
- 比较 45 和 26,45 > 26,交换：
- [7, 12, 26, 45, 64]
- 第二轮结束后,第二大的值 45 已经放到正确的位置。
第三轮遍历
- 比较 7 和 12,7 < 12,不交换。
- 比较 12 和 26,12 < 26,不交换。
- 第三轮结束后,没有发生交换,数组已经有序。
最终排序结果：[7, 12, 26, 45, 64]

冒泡排序的时间复杂度：

最好情况：数组已经有序,时间复杂度为 O(n)。
最坏情况：数组完全逆序,时间复杂度为 O(n^2)。
平均情况：时间复杂度为 O(n^2)。

// 冒泡排序
public static void bubbleSort(int[] arr) {
    int n = arr.length;
    boolean swapped; // 用于优化,判断是否发生交换

    for (int i = 0; i < n - 1; i++) {
        swapped = false; // 每一轮开始时重置为 false
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换相邻元素
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true; // 发生交换
            }
        }
        // 如果某一轮没有发生交换,说明数组已经有序,提前退出
        if (!swapped) {
            break;
        }
    }
}

public static void main(String[] args) {
    int[] arr = {12, 7, 45, 64, 26};
    System.out.println("排序前的数组:");
    printArray(arr);

    bubbleSort(arr); // 调用冒泡排序

    System.out.println("排序后的数组:");
    printArray(arr);
}

// 辅助方法：打印数组
public static void printArray(int[] arr) {
    for (int num : arr) {
        System.out.print(num + " ");
    }
    System.out.println();
}

快速排序

快速排序是一种高效的排序算法,采用分治法（Divide and Conquer）策略。
它的基本思想是通过一趟排序将待排序的数据分割成独立的两部分,其中一部分的所有数据都比另一部分的所有数据小,然后再递归地对这两部分数据进行快速排序,最终完成整个序列的排序。

快速排序步骤：

选择基准值（Pivot）：从数组中选择一个元素作为基准值（通常选择第一个元素、最后一个元素或中间元素）。
分区（Partition）：将数组中的元素重新排列,使得比基准值小的元素都在基准值的左边,比基准值大的元素都在基准值的右边。基准值的位置在分区完成后确定。
递归排序：对基准值左边和右边的子数组递归地进行快速排序。

例：[20, 54, 63, 14, 8, 48, 46, 22, 78, 47, 55, 36]

选择基准值
- 选择最后一个元素36作为基准值(Pivot)
分区(Partition)
分区的目标就是将数组分为两部分：
- 左边部分:所有元素 <= 基准值(36).
- 右边部分:所有元素 >= 基准值(36).
分区过程：
- 初始化两个指针:
  - i: 指向较小元素的最后一个位置(初始为-1)。
  - j: 遍历数组的指针(从0到high - 1)
- 遍历数组:
  - 如果当前元素 arr[j] <= 36 , 则将i右移,并交换 arr[i] 和 arr[j].
  - 否则,继续遍历。
- 遍历完成后,将基准值36放到正确的位置(即i+1).

具体步骤：

初始状态：

[20, 54, 63, 14, 8, 48, 46, 22, 78, 47, 55, 36]
i = -1, j = 0

遍历过程：
- j = 0：20 <= 36,i = 0,交换 arr[0] 和 arr[0]（无变化）。
- j = 1：54 > 36,跳过。
- j = 2：63 > 36,跳过。
- j = 3：14 <= 36,i = 1,交换 arr[1] 和 arr[3]。
  [20, 14, 63, 54, 8, 48, 46, 22, 78, 47, 55, 36]
- j = 4：8 <= 36,i = 2,交换 arr[2] 和 arr[4]。
  [20, 14, 8, 54, 63, 48, 46, 22, 78, 47, 55, 36]
- j = 5：48 > 36,跳过。
- j = 6：46 > 36,跳过。
- j = 7：22 <= 36,i = 3,交换 arr[3] 和 arr[7]。
  [20, 14, 8, 22, 63, 48, 46, 54, 78, 47, 55, 36]
- j = 8：78 > 36,跳过。
- j = 9：47 > 36,跳过。
- j = 10：55 > 36,跳过。
遍历完成后,将基准值 36 放到 i+1 的位置（即 4）：
[20, 14, 8, 22, 36, 48, 46, 54, 78, 47, 55, 63]

递归排序
现在数组被分为两部分:

左子数组：[20, 14, 8, 22]（所有元素 <= 36）。
右子数组：[48, 46, 54, 78, 47, 55, 63]（所有元素 > 36）。
对左右子数组分别递归调用快速排序。

左子数组 [20, 14, 8, 22]：
- 选择基准值：22（最后一个元素）。
- 分区： [8, 14, 20, 22]
- 递归排序：左子数组 [8, 14, 20],右子数组 []（空数组）。
右子数组 [48, 46, 54, 78, 47, 55, 63]：
- 选择基准值：63（最后一个元素）。
- 分区：[48, 46, 54, 47, 55, 63, 78]
- 递归排序：左子数组 [48, 46, 54, 47, 55],右子数组 [78]。

总结：
快速排序的核心是分区操作,通过递归将数组不断划分为更小的子数组, 直到每个子数组只有一个元素或为空。最终,所有子数组合并成一个有序数组。

public class QuickSort {

    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // 找到分区点
            int pi = partition(arr, low, high);

            // 递归排序左子数组
            quickSort(arr, low, pi - 1);

            // 递归排序右子数组
            quickSort(arr, pi + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high]; // 选择最后一个元素作为基准值
        int i = (low - 1); // 较小元素的索引

        for (int j = low; j < high; j++) {
            // 如果当前元素小于或等于基准值
            if (arr[j] <= pivot) {
                i++;

                // 交换arr[i]和arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // 交换arr[i+1]和基准值arr[high]
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }

    public static void main(String[] args) {
        int[] arr = {20, 54, 63, 14, 8, 48, 46, 22, 78, 47, 55, 36};
        int n = arr.length;

        System.out.println("排序前的数组:");
        printArray(arr);

        quickSort(arr, 0, n - 1);

        System.out.println("排序后的数组:");
        printArray(arr);
    }

    private static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}

归并排序

归并排序是一种基于分治法（Divide and Conquer）的排序算法。
它的核心思想是将数组分成两个子数组,分别对子数组进行排序,然后将排序后的子数组合并成一个有序数组。
归并排序的时间复杂度为 O(n log n),是一种非常高效的排序算法。

归并排序的步骤：

分割（Divide）：
- 将数组从中间分成两个子数组。
- 递归地对子数组进行分割,直到每个子数组只有一个元素。
合并（Merge）：
- 将两个有序的子数组合并成一个有序数组。

public class MergeSort {

    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            // 找到中间点
            int mid = (left + right) / 2;

            // 递归排序左子数组
            mergeSort(arr, left, mid);

            // 递归排序右子数组
            mergeSort(arr, mid + 1, right);

            // 合并两个子数组
            merge(arr, left, mid, right);
        }
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        // 计算两个子数组的大小
        int n1 = mid - left + 1;
        int n2 = right - mid;

        // 创建临时数组
        int[] L = new int[n1];
        int[] R = new int[n2];

        // 拷贝数据到临时数组
        for (int i = 0; i < n1; i++) {
            L[i] = arr[left + i];
        }
        for (int j = 0; j < n2; j++) {
            R[j] = arr[mid + 1 + j];
        }

        // 合并临时数组
        int i = 0, j = 0;
        int k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        // 拷贝剩余的元素
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    public static void main(String[] args) {
        int[] arr = {20, 54, 63, 14, 8, 48, 46, 22, 78, 47, 55, 36};
        int n = arr.length;

        System.out.println("排序前的数组:");
        printArray(arr);

        mergeSort(arr, 0, n - 1);

        System.out.println("排序后的数组:");
        printArray(arr);
    }

    private static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}

基数排序

基数排序是一种非比较型整数排序算法, 它通过将整数按位数切割成不同的数字,然后按每个位数分别进行比较和排序。
基数排序的核心思想是从最低位到最高位依次排序,最终得到有序数组。
基数排序的步骤：

找到最大值：确定数组中最大值的位数,决定需要排序的轮数。
按位排序：从最低位（个位）到最高位,依次对每一位进行计数排序（或桶排序）。
合并结果：每一轮排序后,更新数组的顺序,直到所有位数排序完成。

示例数组：

int[] arr = {20, 54, 63, 14, 8, 48, 46, 22, 78, 47, 55, 36};

基数排序的具体步骤：
第一步：找到最大值

数组中的最大值是 78,它有 2 位,因此需要进行 2 轮排序（个位和十位）。

第二步：按个位排序

创建 10 个桶（0-9）,用于存放个位数字对应的元素。
将数组中的元素按个位数字分配到对应的桶中：
- 个位为 0：20
- 个位为 1：无
- 个位为 2：22
- 个位为 3：63
- 个位为 4：54, 14
- 个位为 5：55
- 个位为 6：46, 36
- 个位为 7：无
- 个位为 8：8, 48, 78
- 个位为 9：无
按桶的顺序将元素重新放回数组：
[20, 22, 63, 54, 14, 55, 46, 36, 8, 48, 78]

第三步：按十位排序

再次创建 10 个桶（0-9）,用于存放十位数字对应的元素。
将数组中的元素按十位数字分配到对应的桶中：
- 十位为 0：8
- 十位为 1：14
- 十位为 2：20, 22
- 十位为 3：36
- 十位为 4：46, 48
- 十位为 5：54, 55
- 十位为 6：63
- 十位为 7：78
- 十位为 8：无
- 十位为 9：无
按桶的顺序将元素重新放回数组：
[8, 14, 20, 22, 36, 46, 48, 54, 55, 63, 78]

import java.util.Arrays;

public class RadixSort {

    // 获取数组中的最大值
    private static int getMax(int[] arr) {
        int max = arr[0];
        for (int num : arr) {
            if (num > max) {
                max = num;
            }
        }
        return max;
    }

    // 基数排序的核心方法
    private static void countingSort(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n]; // 存储排序结果的数组
        int[] count = new int[10]; // 计数数组

        // 初始化计数数组
        Arrays.fill(count, 0);

        // 统计每个桶中的元素个数
        for (int num : arr) {
            int digit = (num / exp) % 10;
            count[digit]++;
        }

        // 计算累加次数,确定每个元素的最终位置
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        // 将元素放入输出数组
        for (int i = n - 1; i >= 0; i--) {
            int digit = (arr[i] / exp) % 10;
            output[count[digit] - 1] = arr[i];
            count[digit]--;
        }

        // 将排序结果拷贝回原数组
        System.arraycopy(output, 0, arr, 0, n);
    }

    // 基数排序主方法
    public static void radixSort(int[] arr) {
        int max = getMax(arr); // 找到最大值

        // 从个位到最高位依次排序
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSort(arr, exp);
        }
    }

    public static void main(String[] args) {
        int[] arr = {20, 54, 63, 14, 8, 48, 46, 22, 78, 47, 55, 36};
        System.out.println("排序前的数组:");
        printArray(arr);

        radixSort(arr);

        System.out.println("排序后的数组:");
        printArray(arr);
    }

    // 打印数组
    private static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

排序总结

排序算法	平均时间复杂度	最好时间复杂度	最坏时间复杂度	空间复杂度	是否占用额外空间	稳定性
基数排序	O(nk)	O(nk)	O(nk)	O(n + k)	是	是
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	是	是
希尔排序	O(n log n)	O(n log n)	O(n log n)	O(1)	否	否
快速排序	O(n log n)	O(n log n)	O(n²)	O(log n)	否	否
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	否	否
冒泡排序	O(n²)	O(n)	O(n²)	O(1)	否	是
选择排序	O(n²)	O(n²)	O(n²)	O(1)	否	否
插入排序	O(n²)	O(n)	O(n²)	O(1)	否	是

记忆技巧

冒泡排序、选择排序、插入排序：
- 都是简单排序算法，适合小规模数据。
- 冒泡和插入是稳定的，选择排序是不稳定的。
- 插入排序对基本有序的数据效率高（O(n)）。
希尔排序：
- 是插入排序的改进版，效率更高，但不稳定。
归并排序：
- 稳定且时间复杂度稳定（O(n log n)），但需要额外空间。
快速排序：
- 平均性能最优，但不稳定，且最坏情况下退化为 O(n²)。
堆排序：
- 时间复杂度稳定（O(n log n)），但不稳定，实现较复杂。
基数排序：
- 适合整数或字符串排序，但需要额外空间，且对数据类型有限制。

总结

小规模数据：选择插入排序或冒泡排序。
大规模数据：优先选择快速排序或归并排序。
整数排序：基数排序是最优选择。
稳定性要求：选择归并排序、冒泡排序或插入排序。