数据结构与算法学习笔记
数据结构与算法思维导图
数据结构指的是“一组数据的存储结构”，算法指的是“操作数据的一组方法”。
数据结构是为算法服务的，算法是要作用再特定的数据结构上的。
最常用的数据结构预算法:
- 数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Tire树
- 算法： 递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
算法的复杂度
大O复杂度表示法
公式:
我们通常用 T(n)来表示代码执行的时间，其中 n代表数据规模的大小。而 f(n)则表示所有代码执行次数的总和，它是一个关于 n的函数。
大O表示法的公式 T(n) = O(f(n))意在说明，代码的执行时间 T(n)与执行次数总和 f(n)成正比关系。
例如，假设某段代码的 f(n) = 2n + 2，那么它的 T(n)就可以表示为 O(2n+2)。另一段代码的 f(n)可能是 2n² + 2n + 3，其 T(n)则可表示为 O(2n²+2n+3)。
大O时间复杂度表示法并不精确计算代码真正的执行时间，而是形象地描绘出代码执行时间随数据规模 n增大而变化的速度趋势
。因此，它也被称为渐进时间复杂度（asymptotic time complexity）。
当数据规模 n变得非常大时（例如想象 n是 10000 甚至 100000），公式中的低阶项（如 +2n、+3）、常数项（如 2n中的 2）以及系数都对整个增长趋势的影响变得微乎其微，可以忽略不计
。我们只需要关注最高阶项，因为它主导了增长的趋势。
所以，上面两个例子用大O表示法简化记作：
T(n) = O(n)T(n) = O(n²)
简单来说，大O表示法抓大放小，只关注最影响效率的主要矛盾。
时间复杂度分析法则
1. 基本原则
- 关注最高频操作：复杂度主要由循环、递归等高频执行的语句决定。
- 忽略常数、低阶项：分析时只保留增长速度最快的部分。
2. 常见法则
- 单段代码取高频
-
- 例如循环，复杂度由循环次数决定。
for (int i = 0; i < n; i++)→ O(n)
- 多段代码取最大（加法法则）
-
- 如果一段代码包含多种复杂度，最终复杂度取其中量级最大的。
O(n) + O(n²)→ O(n²)
- 嵌套代码取乘积（乘法法则）
-
- 循环/递归嵌套时，复杂度是内外层复杂度的乘积。
for (i=0; i<n; i++) for (j=0; j<n; j++)→ O(n²)
- 多个规模取加法
-
- 当多个循环由不同变量控制时，复杂度相加。
for (i=0; i<n; i++)+for (j=0; j<m; j++)→ O(n + m)
单段看循环，多段取最大，嵌套算乘积，不同规模相加。
几种常见时间复杂度实例分析
1. 多项式阶（常见、可接受）
- O(1)：常数阶，不随数据规模变化。
- O(log n)：对数阶，常见于二分查找。
- O(n)：线性阶，最常见的复杂度。
- O(n log n)：线性对数阶，常见于高效排序算法（归并、快排）。
- O(n²)、O(n³)：平方、立方阶，常见于多重循环。
2. 非多项式阶（性能极差）
- O(2ⁿ)：指数阶，常见于递归穷举。
- O(n!)：阶乘阶，常见于全排列问题。
时间复杂度示例
O(1)
执行次数与 n 无关：
int a = 1, b = 2;
int c = a + b; // O(1)O(log n)
指数增长的循环：
int i = 1;
while (i <= n) {
i = i * 2; // log₂n 次
}→ 复杂度 O(log n)
O(n log n)
外层 O(n)，内层 O(log n)：
for (int i = 0; i < n; i++) {
int j = 1;
while (j <= n) {
j = j * 2;
}
}→ 复杂度 O(n log n)
O(m + n)
两个规模独立的循环：
int cal(int m, int n) {
int sum1 = 0, sum2 = 0;
for (int i = 1; i < m; i++) sum1 += i; // O(m)
for (int j = 1; j < n; j++) sum2 += j; // O(n)
return sum1 + sum2;
}→ 复杂度 O(m + n)
⚠️ 这里不能简单省略，因为 m 和 n 规模不确定。
O(m * n)
双重嵌套：
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// O(1)
}
}→ 复杂度 O(m * n)
空间复杂度分析
空间复杂度表示算法运行过程中额外需要的存储空间与数据规模 n 的关系。
示例：
void print(int n) {
int i = 0; // O(1)
int[] a = new int[n]; // O(n)
for (i = 0; i < n; i++) {
a[i] = i * i;
}
for (i = n - 1; i >= 0; i--) {
System.out.println(a[i]);
}
}int i：常量空间 O(1)int[] a：需要 n 个空间 O(n)- 其余语句不占用额外空间
→ 总空间复杂度：O(n)
常见空间复杂度
- O(1)：常量空间（变量、计数器）。
- O(n)：线性空间（数组、链表）。
- O(n²)：二维数组。
- （对数阶空间 O(log n)、O(n log n) 实际应用中很少见）。
总结：关注额外数据结构大小，常见 O(1)、O(n)、O(n²)。
时间复杂度 & 空间复杂度对照表
|
复杂度 |
时间复杂度示例代码 |
场景 |
空间复杂度示例代码 |
场景 |
|
O(1) |
|
常量时间，不随 n 增长 |
|
只使用常量存储 |
|
O(log n) |
|
二分查找、平衡树操作 |
少见，一般递归调用栈会近似 O(log n)，如二分查找 |
递归深度 log n |
|
O(n) |
|
遍历数组/链表 |
|
存储一维数组 |
|
O(n log n) |
|
高效排序（快排、归并排序） |
少见，如分治需要额外数组 |
归并排序辅助数组 |
|
O(n²) |
|
嵌套循环（冒泡、选择、插入排序） |
|
存储二维矩阵 |
|
O(n³) |
|
三重嵌套循环 |
很少见，三维数组存储 |
三维表格/立体数据 |
|
O(m+n) |
|
两个规模独立循环 |
|
同时存储 m 和 n |
|
O(m*n) |
|
双重循环 |
|
m×n 矩阵 |
|
O(2ⁿ) |
|
递归穷举（子集、背包） |
|
回溯 |
|
O(n!) |
|
全排列问题 |
|
全排列存储 |
复杂度增长趋势
复杂度分析的四个概念
- 最坏时间复杂度：代码在最糟糕情况下的复杂度。
- 最好时间复杂度：代码在最理想情况下的复杂度。
- 平均时间复杂度：所有情况加权平均后的复杂度。
- 均摊时间复杂度：大多数操作是低复杂度，少数高复杂度操作有时序规律，可均摊为低复杂度。
常见数据结构
1、 线性表
线性表: 线性表就是数据排成像一条线一样的结构，每个线性表上的数据最多只有前和后两个方向，常见的线性表结构：数组，链表、队列、栈等。
数组
数组（Array）是一种线性表数据结构，使用一块连续的内存空间存储一组相同类型的数据。
特点：
- 连续的内存空间：数组需要一块连续的内存空间来存储数据。
- 相同类型的数据：数组中的所有元素必须是相同的数据类型。
- 优点：支持随机访问，访问效率高。
- 缺点：插入和删除操作效率较低，对内存空间要求较高。
随机访问的原理：
数组可以通过下标快速访问元素，其寻址公式为：
a[i]_address = base_address + i * data_type_sizebase_address：数组首元素的内存地址。i：数组下标。data_type_size：数组中每个元素的大小。
插入和删除操作效率低的原因：
- 插入：在数组的第
k个位置插入数据时，需要将k到n的元素依次向后移动，最坏情况下时间复杂度为O(n)，最好情况下为O(1)。 - 删除：删除某个元素后，需要将其后续元素依次向前移动，时间复杂度同样为
O(n)。
最好时间复杂度O(1)
最坏情况复杂度为O(n)
数组插入和删除的复杂度分析
插入操作：
- 复杂度：
-
- 最好情况：
O(1)（直接在数组末尾插入，无需移动元素）。 - 最坏情况：
O(n)（在数组开头插入，需要移动所有元素）。 - 平均情况：
O(n)。
- 最好情况：
- 优化方式（无序数组）：
-
- 如果数组无序，可以将第
k个位置的元素移动到数组末尾，然后将新元素插入到第k个位置。 - 此时插入操作的复杂度为
O(1)。
- 如果数组无序，可以将第
删除操作：
- 复杂度：
-
- 最好情况：
O(1)（删除末尾元素，无需移动其他元素）。 - 最坏情况：
O(n)（删除开头元素，需要移动所有后续元素）。 - 平均情况：
O(n)。
- 最好情况：
- 优化方式（批量删除）：
-
- 记录已删除的数据，每次删除操作仅标记数据为“已删除”，而不立即移动数据。
- 当数组存储空间不足时，触发一次真正的删除操作，清理标记为“已删除”的数据。
- 这种方式类似于 JVM 的标记-清除垃圾回收算法，能够提高多次删除操作的效率。
链表（Linked List）
- 定义：链表是一种线性表数据结构，与数组类似，但其内存分布不要求连续。
- 内存结构：链表使用一组不连续的内存块，通过指针将这些内存块串联起来。
- 节点（Node）：
-
- 每个节点包含两部分：
-
-
- 数据域：存储数据。
- 指针域：存储指向下一个节点的地址（后继指针
next）。
-
- 特点：
-
- 插入和删除操作效率高，不需要移动其他元素。
- 随机访问效率低，需要从头节点开始遍历。
内存消耗：与数组相比，链表的内存消耗更大，因为每个节点除了存储数据外，还需要额外的空间来存储后继指针。
操作效率：
- 插入、删除：效率较高，时间复杂度为
O(1)，只需修改指针指向即可完成操作。 - 随机访问：效率较低，时间复杂度为
O(n)，需要从链表头部开始逐个遍历，直到找到目标节点。
单链表
- 节点结构：每个节点仅包含一个后继指针，用于指向链表中的下一个节点。
- 特殊节点：
-
- 首节点：首节点的地址表示整条链表的起点。
- 尾节点：尾节点的后继指针指向空地址（
null），表示链表的终点。
- 性能特点：
-
- 插入和删除：时间复杂度为
O(1)，只需修改指针指向即可完成操作。 - 查找：时间复杂度为
O(n)，需要从首节点开始逐个遍历，直到找到目标节点。
- 插入和删除：时间复杂度为
循环链表
- 循环链表：与单链表的区别在于尾节点的后继指针指向首节点的地址，从而形成一个环状结构。
- 应用场景：适合处理具有循环特性的问题，例如约瑟夫问题、循环队列等。
双向链表
- 节点结构：双向链表的每个节点包含三个部分：数据域、前驱指针（
prev）和后继指针（next）。
-
- 前驱指针指向前一个节点的地址。
- 后继指针指向下一个节点的地址。
- 首节点的前驱指针和尾节点的后继指针均指向空地址（
null）。
- 性能特点：
-
- 存储空间：相比单链表，双向链表需要额外的存储空间来存储前驱指针。
- 插入和删除：
-
-
- 给定数据值删除节点：时间复杂度为
O(n)，需要遍历链表找到目标节点。 - 给定节点地址删除节点：时间复杂度为
O(1)，直接通过前驱指针找到前驱节点并修改指针即可。
- 给定数据值删除节点：时间复杂度为
-
-
- 查询效率：
-
-
- 对于有序链表，双向链表可以通过记录上次查找的位置，根据大小关系决定查找方向，从而提高查询效率，平均只需查找一半的数据。
-
4.双向循环链表：
首节点的前驱指针指向尾节点，尾节点的后继指针指向首节点。
链表于数组比较
1.插入、删除和随机访问的时间复杂度
数组：插入、删除的时间复杂度是O(n)，随机访问的时间复杂度是O(1)。
链表：插入、删除的时间复杂度是O(1)，随机访问的时间复杂端是O(n)。
- 内存分配：
-
- 数组：静态分配内存，内存连续，元素存储在栈区。
- 链表：动态分配内存，内存不连续，元素存储在堆区。
- 长度：
-
- 数组：长度固定，无法动态扩展，数据增加可能超出容量，减少会浪费内存。
- 链表：动态分配内存，适应数据动态增减。
- 访问效率：
-
- 数组：支持随机访问，时间复杂度为
O(1)。 - 链表：不支持随机访问，时间复杂度为
O(n)。
- 数组：支持随机访问，时间复杂度为
- 插入和删除效率：
-
- 数组：插入、删除需要移动元素，时间复杂度为
O(n)。 - 链表：插入、删除只需修改指针，时间复杂度为
O(1)。
- 数组：插入、删除需要移动元素，时间复杂度为
- CPU缓存友好性：
-
- 数组：内存连续，CPU缓存友好，访问效率高。
- 链表：内存不连续，CPU缓存不友好。
- 可能导致堆内存溢出，因为无法找到足够大的连续内存空间。
- 频繁的内存申请和释放会导致内存碎片，在 Java 中可能引发频繁的GC（垃圾回收）。
选择建议
- 优先选择数组：如果数据量固定、需要高效随机访问、对内存使用不苛刻。
- 选择链表：如果数据量动态变化、需要频繁插入和删除操作。
队列
队列是一种先进先出（FIFO, First In First Out）的线性表数据结构，支持以下两种基本操作：
特点：
- 抽象数据结构：队列是一种逻辑结构，具体实现可以基于数组或链表。
- 操作受限：
-
- 入队（enqueue）：在队尾插入元素。
- 出队（dequeue）：从队头删除元素。
- 先进先出：最早进入队列的元素最先被处理。
实现方式：
- 顺序队列（基于数组实现）：
-
- 优点：实现简单，访问效率高。
- 缺点：数组长度固定，可能导致内存浪费或需要扩容。
- 链式队列（基于链表实现）：
-
- 优点：动态分配内存，适合数据动态变化的场景。
- 缺点：需要额外的存储空间存储指针。
实现队列
队列可以用数组来实现,也可以用链表来实现。
用数组实现的队列叫作顺序队列,用链表实现的队列叫作链式队列。
基于数组的队列:
实现思路:
实现队列需要两个指针:一个是head指针,指向队头;一个是tail指针,指向队尾。你可以结合下面这幅图来理解。当a,b,c,d依次入队之后,队列中的head指针指向下标为0的位置, tail指针指向下标为4的位置。
当我们调用两次出队操作之后,队列中head指针指向下标为2的位置, tail指针仍然指向下标为4的位置.
随着不停地进行入队、出队操作, head和tail都会持续往后移动。当tail移 . ,动到最右边,即使数组中还有空闲空间,也无法继续往队列中添加数据了。这个问题该如何解决呢?
在出队时可以不用搬移数据。如果没有空闲空间了,我们只需要在入队时,再集中触 ,发一次数据的搬移操作。
当队列的tail指针移动到数组的最右边后,如果有新的数据入队,我们可以将 head到tail之间的数据,整体搬移到数组中0到tail-head的位置。
public class ArrayQueue {
private int[] data; // 存储队列数据的数组
private int head; // 指向队头的指针
private int tail; // 指向队尾的指针
private int size; // 队列的当前大小
public ArrayQueue(int capacity) {
data = new int[capacity];
head = 0;
tail = 0;
size = 0;
}
// 入队操作
public boolean enqueue(int value) {
if (size == data.length) {
// 如果队列已满，触发数据搬移操作
if (head == 0) {
return false; // 队列已满且无法搬移
}
// 搬移数据
for (int i = head; i < tail; i++) {
data[i - head] = data[i];
}
tail -= head; // 更新tail指针
head = 0; // 重置head指针
}
// 插入新数据
data[tail] = value;
tail++;
size++;
return true;
}
// 出队操作
public Integer dequeue() {
if (size == 0) {
return null; // 队列为空
}
int value = data[head];
head++;
size--;
return value;
}
// 获取队列当前大小
public int getSize() {
return size;
}
// 判断队列是否为空
public boolean isEmpty() {
return size == 0;
}
}基于链表的实现:
需要两个指针: head指针和tail指针,它们分别指向链表的第一个结,点和最后一个结点。
如图所示,入队时, tail->next= new node, tail = tail->next:出队时, head = head->next.
public class LinkedQueue {
private static class Node {
int value;
Node next;
Node(int value) {
this.value = value;
this.next = null;
}
}
private Node head; // 指向队头
private Node tail; // 指向队尾
public LinkedQueue() {
head = null;
tail = null;
}
// 入队操作
public void enqueue(int value) {
Node newNode = new Node(value);
if (tail != null) {
tail.next = newNode; // 将新节点连接到队尾
}
tail = newNode; // 更新队尾指针
if (head == null) {
head = tail; // 如果队列为空，更新队头指针
}
}
// 出队操作
public Integer dequeue() {
if (head == null) {
return null; // 队列为空
}
int value = head.value;
head = head.next; // 更新队头指针
if (head == null) {
tail = null; // 如果队列为空，重置队尾指针
}
return value;
}
// 判断队列是否为空
public boolean isEmpty() {
return head == null;
}
}循环队列
我们刚才用数组来实现队列的时候,在tail==n时,会有数据搬移操作,这样入队操作性能就会受到影响。那有没有办法能够避免数据搬移呢?我们来看看循环队列的解决思路。循环队列,顾名思义,它长得像一个环。原本数组是有头有尾的,是一条直线。现在我们把首尾相,连,板成了一个环。我画了一张图,你可以直观地感受一下。
我们可以看到,图中这个队列的大小为8,当前head-4, tail-7,当有一个新的元素a入队时, .我们放入下标为7的位置。但这个时候,我们并不把tail更新为8,而是将其在环中后移一位,到下标为0的位置。当再有一个元素b入队时,我们将b放入下标为0的位置,然后tail加1更新为1,所以,在a, b依次入队之后,循环队列中的元素就变成了下面的样子:
队列为空的判断条件是head == tail,但队列满的判断条件就稍微有点复杂了。我画了一张队列满的图,你可以看一下,试着总结一下规律,
就像我图中画的队满的情况, tail=3, head-4, n=8,所以总结一下规律就是: (3+1)%8-4,多画几张队满的图,你就会发现,当队满时, (tail+1)%n=head..你有没有发现,当队列满时,图中的tail指向的位置实际上是没有存储数据的。所以,循环队列会浪费一个数组的存储空间。
解决浪费一个存储空间的思路:定义一个记录队列大小的值size，当这个值与数组大小相等时，表示队列已满，当tail达到最底时，size不等于数组大小时，tail就指向数组第一个位置。当出队时，size—，入队时size++
阻塞队列
阻塞队列和并发队列(应用比较广泛)
阻塞队列其实就是在队列基础上增加了阻塞操作。
简单来说,就是在队列为空的时候,从队头取数 , 据会被阻塞。因为此时还没有数据可取,直到队列中有了数据才能返回;如果队列已经满了,那么插入数据的操作就会被阻塞,直到队列中有空闲位置后再插入数据,然后再返回。
你应该已经发现了,上述的定义就是一个"生产者-消费者模型" !是的,我们可以使用阻塞队列,轻松实现一个"生产者-消费者模型" !这种基于阻塞队列实现的"生产者-消费者模型" ,可以有效地协调生产和消费的速度。当"生产 , 者"生产数据的速度过快, "消费者"来不及消费时,存储数据的队列很快就会满了。这个时候,生产者就阻塞等待,直到"消费者"消费了数据, "生产者"才会被唤醒继续"生产而且不仅如此,基于阻塞队列,我们还可以通过协调"生产者"和"消费者"的个数,来提高数据,的处理效率。比如前面的例子,我们可以多配置几个"消费者" ,来应对一个"生产者"
小结
队列最大的特点就是先进先出,主要的两个操作是入队和出队。
它既可以用数组来实现,也可以用链表来实现。用数组实现的叫顺序队列,用链表实现的叫链式队列。
长在数组实现队列的时候,会有数据搬移操作,要想解决数据搬移的问题,我们就,需要像环一样的循环队列。要想写出没有bug的循环队列实现代码,关键要确定好队空和队满的,判定条件。
阻塞队列、并发队列,底层都还是队列这种数据结构,只不过在之上附加了很多其他功能。阻塞队列就是入队、出队操作可以阻塞并发队列就是队列的操作多线程安全。
4、散列表
什么是散列表:
散列表用的是数组支持按照下标随机访问数据的特性,所以散列表其实就是数组的一种扩展,由数组演化而来。可以说,如果没有数组,就没有散列表。
原理:
散列表用的就是数组支持按照下标随机访问的时候,时间复杂度是0(1)的特性。我们通过散列函数把元素的键值映射为下标,然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时,我们用同样的散列函数,将键值转化数组标标,从对应的数组下标的位置取数据。
散列函数的设计要求:
- 散列函数计算得到的散列值是一个非负整数;.
- 如果key1 = key2,那hash(key1) == hash(key2);
- 如果key1 != key2,那hash(key1) != hash(key2),
散列函数的设计不能太复杂,散列函数生成值要尽可能随机并且均匀分布
如果不符合3 那么就出现了散列冲突,散列冲突是无法避免的
解决散列冲突的方法有两种:
开放寻址法(open addressing)和链表法(chaining)
开放寻址法:如果出现了散列冲突,我们就重新探测一个空闲位置,将其插入。
装在因子: 散列表中一定比例的空闲槽位。公式: 散列表的装载因子 = 填入表中的元素个数 / 散列表的长度
装载因子越大,说明空闲位置越少,冲突越多,散列表的性能会下降。
链表法:
链表法是一种更加常用的散列冲突解决办法,相比开放寻址法,它要简单很多。我们来看这个图,在散列表中,每个"桶(bucket) "或者"槽(slot) "会对应一条链表,所有散列值相同的元素我们都放到相同槽位对应的链表中。
常见算法
1、递归算法
一、什么是递归？
1.递归是一种非常高效、简洁的编码技巧，一种应用非常广泛的算法，比如DFS深度优先搜索、前中后序二叉树遍历等都是使用递归。
2.方法或函数调用自身的方式称为递归调用，调用称为递，返回称为归。
3.基本上，所有的递归问题都可以用递推公式来表示，比如
f(n) = f(n-1) + 1;
f(n) = f(n-1) + f(n-2);
f(n)=n*f(n-1);
二、为什么使用递归？递归的优缺点？
1.优点：代码的表达力很强，写起来简洁。
2.缺点：空间复杂度高、有堆栈溢出风险、存在重复计算、过多的函数调用会耗时较多等问题。
三、什么样的问题可以用递归解决呢？
一个问题只要同时满足以下3个条件，就可以用递归来解决：
1.问题的解可以分解为几个子问题的解。何为子问题？就是数据规模更小的问题。
2.问题与子问题，除了数据规模不同，求解思路完全一样
3.存在递归终止条件
四、如何实现递归？
1.递归代码编写
写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。
2.递归代码理解
对于递归代码，若试图想清楚整个递和归的过程，实际上是进入了一个思维误区。
那该如何理解递归代码呢？如果一个问题A可以分解为若干个子问题B、C、D，你可以假设子问题B、C、D已经解决。而且，你只需要思考问题A与子问题B、C、D两层之间的关系即可，不需要一层层往下思考子问题与子子问题，子子问题与子子子问题之间的关系。屏蔽掉递归细节，这样子理解起来就简单多了。
因此，理解递归代码，就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。
递归的关键是终止条件
五、递归常见问题及解决方案
1.警惕堆栈溢出：可以声明一个全局变量来控制递归的深度，从而避免堆栈溢出。
2.警惕重复计算：通过某种数据结构来保存已经求解过的值，从而避免重复计算。
六、如何将递归改写为非递归代码？
笼统的讲，所有的递归代码都可以改写为迭代循环的非递归写法。如何做？抽象出递推公式、初始值和边界条件，然后用迭代循环实现。
2、排序
一、排序方法与复杂度归类
（1）几种最经典、最常用的排序方法：冒泡排序、插入排序、选择排序、快速排序、归并排序、计数排序、基数排序、桶排序。
（2）复杂度归类
冒泡排序、插入排序、选择排序 O(n^2)
快速排序、归并排序 O(nlogn)
计数排序、基数排序、桶排序 O(n)
二、如何分析一个“排序算法”？
<1>算法的执行效率
1. 最好、最坏、平均情况时间复杂度。
2. 时间复杂度的系数、常数和低阶。
3. 比较次数，交换（或移动）次数。
<2>排序算法的稳定性
1. 稳定性概念：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。
2. 稳定性重要性：可针对对象的多种属性进行有优先级的排序。
3. 举例：给电商交易系统中的“订单”排序，按照金额大小对订单数据排序，对于相同金额的订单以下单时间早晚排序。用稳定排序算法可简洁地解决。先按照下单时间给订单排序，排序完成后用稳定排序算法按照订单金额重新排序。
<3>排序算法的内存损耗
原地排序算法：特指空间复杂度是O(1)的排序算法。
常见的排序算法:
冒泡排序
冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求，如果不满足就让它俩互换。
代码:
public int[] bubbleSort(int[] a) {
int n = a.length;
if (n<=1) {
return a;
}
for (int i = 0; i < n; i++) {
//提前退出冒泡循环的标志
boolean flag = false;
for (int j = 0; j < n-i-1; j++) {
if (a[j]>a[j+1]) {//
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
flag = true;//表示有数据交换
}
if (!flag) {
break; //没有数据交换(说明已排好序无需再进行冒泡),提前退出
}
}
}
return a;
}
四、插入排序
插入排序将数组数据分成已排序区间和未排序区间。初始已排序区间只有一个元素，即数组第一个元素。在未排序区间取出一个元素插入到已排序区间的合适位置，直到未排序区间为空。
代码:
public int[] insertionSort(int[] a) {
int n = a.length;
if (n<=1) return a;
for (int i = 1; i < n; i++) {
int value = a[i];
int j = i-1;
for (; j >=0; j--) {
if (a[j] > value) {
a[j+1] = a[j];//移动数据
}else {
break;
}
}
a[j+1] = value;//插入数据
}
return a;
}
五、选择排序
选择排序将数组分成已排序区间和未排序区间。初始已排序区间为空。每次从未排序区间中选出最小的元素插入已排序区间的末尾，直到未排序区间为空。
代码:
public int[] selectionSort(int[] a) {
int n = a.length;
for (int i = 0; i < a.length - 1; i++) {
for (int j = i+1; j < a.length; j++) {
//交换
if (a[i] > a[j]) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
return a;
}六、归并排序
如果要排序一个数组,我们先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就都有序了。
实现思路:
merge-sort(p...r)表示,给下标从p到r之间的数组排序。我们将这个排序问题转化为了两个子问 ,题, merge_sort(p...q)和merge-sort(q+1..r),其中下标q等于p和r的中间位置,也就是, (p+r)/2,当下标从p到q和从q+1到r这两个子数组都排好序之后,我们再将两个有序的子数组合并在一起,这样下标从p到r之间的数据就也排好序了。
代码:
// 归并排序算法, a是数组，n表示数组大小
public static void mergeSort(int[] a, int n) {
mergeSortInternally(a, 0, n-1);
}
// 递归调用函数
private static void mergeSortInternally(int[] a, int p, int r) {
// 递归终止条件
if (p >= r) return;
// 取p到r之间的中间位置q
int q = (p+r)/2;
// 分治递归
mergeSortInternally(a, p, q);
mergeSortInternally(a, q+1, r);
// 将A[p...q]和A[q+1...r]合并为A[p...r]
merge(a, p, q, r);
}
private static void merge(int[] a, int p, int q, int r) {
int i = p;
int j = q+1;
int k = 0; // 初始化变量i, j, k
int[] tmp = new int[r-p+1]; // 申请一个大小跟a[p...r]一样的临时数组
// 1 排序
while (i<=q && j<=r) {
if (a[i] <= a[j]) {
tmp[k++] = a[i++]; // i++等于i:=i+1
} else {
tmp[k++] = a[j++];
}
}
// 2 判断哪个子数组中有剩余的数据
int start = i;
int end = q;
if (j <= r) {
start = j;
end = r;
}
// 3 将剩余的数据拷贝到临时数组tmp
while (start <= end) {
tmp[k++] = a[start++];
}
// 4 将tmp中的数组拷贝回a[p...r]
for (i = 0; i <= r-p; ++i) {
a[p+i] = tmp[i];
}
}
merge是这样执行的:
代码分析:
七、快速排序
快排的思想: 如果要排序数组中下标从p到r之间的一组数据,我们选择p到r之间的任意一个数据作为pivot (分区点) 。我们遍历p到r之间的数据,将小于pivot的放到左边,将大于pivot的放到右边,将pivot放到中间。经过这一步骤之后,数组p到r之间的数据就被分成了三个部分,前面p到q-1之间都是小于pivot的,中间是pivot,后面的q+1到r之间是大于pivot的。
快排利用的分而治之的思想
八、线性排序:
时间复杂度O(n)
我们把时间复杂度是线性的排序算法叫作线性排序(Linear sort)常见的线性算法有: 桶排序、计数排序、基数排序
特点:
非基于比较的排序算法
桶排序
桶排序,顾名思义,会用到“桶" ,核心思想是将要排序的数据分到几个有序的桶里,每个桶里的数据再单独进行排序。桶内排完序之后,再把每个桶里的数据按照顺序依次取出,组成的序列就是有序的了。
对排序的数据要求苛刻:
1, 要排序的数据需要很容易就能划分成m个桶,并且,桶与桶之间有着天然的大小顺序。
2 ,数据在各个桶之间的分布是比较均匀的。
3 ,桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中,数据量比较大,内存有限，无法将数据全部加载到内存中。
计数排序
计数排序只能用在数据范围不大的场景中,如果数据范围k比要排序的数据n大很多,就不适合用计数排序了。
计数排序只能给非负整数排序,如果要排序的数据是其他类型的,要将其在不改变相对大小的情况下,转化为非负整数。
代码:
// 计数排序，a是数组，n是数组大小。假设数组中存储的都是非负整数。
public static void countingSort(int[] a) {
int n = a.length;
if (n <= 1) return;
// 查找数组中数据的范围
int max = a[0];
for (int i = 1; i < n; ++i) {
if (max < a[i]) {
max = a[i];
}
}
// 申请一个计数数组c，下标大小[0,max]
int[] c = new int[max + 1];
for (int i = 0; i < max + 1; ++i) {
c[i] = 0;
}
// 计算每个元素的个数，放入c中
for (int i = 0; i < n; ++i) {
c[a[i]]++;
}
// 依次累加
for (int i = 1; i < max + 1; ++i) {
c[i] = c[i-1] + c[i];
}
// 临时数组r，存储排序之后的结果
int[] r = new int[n];
// 计算排序的关键步骤了，有点难理解
for (int i = n - 1; i >= 0; --i) {
int index = c[a[i]]-1;
r[index] = a[i];
c[a[i]]--;
}
// 将结果拷贝会a数组
for (int i = 0; i < n; ++i) {
a[i] = r[i];
}
}
新一代开源开发者平台 GitCode，通过集成代码托管服务、代码仓库以及可信赖的开源组件库，让开发者可以在云端进行代码托管和开发。旨在为数千万中国开发者提供一个无缝且高效的云端环境，以支持学习、使用和贡献开源项目。
更多推荐
2587
0- 0
已为社区贡献2条内容
所有评论(0)