查询与排序算法和数据结构
算法和数据结构是相辅相成的，通过选择合适的数据结构，可以优化存储和访问效率，而使用恰当的算法则能在操作数据时提高效率。两者的结合能够在不同场景中提供更好的性能。例如，在搜索问题中，哈希表能使查找操作更高效，而在排序问题中，选择合适的排序算法（如快速排序或归并排序）能显著提升程序的执行速度。
算法
时间复杂度和空间复杂度：理解算法效率，如何通过大O符号衡量。 数据结构：选择合适的数据结构（如数组、链表、堆、树、图）来优化算法。 排序和查找：如快速排序、归并排序、二分查找等经典算法。 动态规划与分治法：解决优化问题和递归问题的常见方法。 图算法：包括最短路径、最小生成树、深度优先搜索（DFS）和广度优先搜索（BFS）。 贪心算法：用于选择最优解的策略。
排序
冒泡排序（Bubble Sort） 通过不断交换相邻的未排序元素，将较大的元素“冒泡”到列表末尾。 时间复杂度：O(n²)，因为每个元素都可能与其他所有元素交换。 空间复杂度：O(1)，在原地进行交换。 适用于数据量小、元素大致有序的情况。性能不佳，不推荐用于大数据。 选择排序（Selection Sort） 每次选择未排序部分的最小元素，并与当前元素交换位置。 时间复杂度：O(n²)，需要遍历所有元素找到最小值。 空间复杂度：O(1)，原地排序。 适用于内存限制较小的情况，数据量较少时可使用。 注：相比冒泡排序选择排序与其对比次数相关，不同在于冒泡排序的交换次数可能要大于选择排序 插入排序（Insertion Sort） 将未排序的元素插入到已排序部分的正确位置。 时间复杂度：O(n²)，最坏情况下每个元素都需要与已排序元素比较。 空间复杂度：O(1)，原地排序。 适合数据量小或部分有序的数据集，例如在线实时排序。 快速排序（Quick Sort） 通过选择一个基准元素，将数组分成两部分，递归排序两部分。 时间复杂度：平均O(n log n)，最坏O(n²)（当选的基准不理想时）。 空间复杂度：O(log n)，递归调用栈的空间。 常用于大规模数据集，如数据库中的排序，效率高。 注：利用空间换时间，想像一下在最理想的情况下，每次都选中中值基准值时整个数据的散落情况就像下面一样： 968745321 4321 5 9687 1 2 43 5 67 8 9 比对次数：（8）+（3+3）+（2）= 16 < 9*(9-1)/2=36（冒泡） 极端情况： 968745321 1 96874532 1 2 9687453 1 2 3 968745 1 2 3 4 96875 1 2 3 4 5 9687 1 2 3 4 5 6 987 1 2 3 4 5 6 7 98 1 2 3 4 5 6 7 8 9 比对次数：8+7+6+5+4+3+2+1=36（退化为O(n²)） 归并排序（Merge Sort） 通过将数组分成两部分，递归地排序，并将两个已排序的部分合并。 时间复杂度：O(n log n)，分治法使得每次操作缩小问题规模。 空间复杂度：O(n)，需要额外的数组存储合并结果。 适用于需要稳定排序的场景，特别是对外存数据排序。 注：归并排序与快速排序的先对比后排序相反，它是先分割再对比排序并组合。虽然它占用更多空间，速度也不如快速排序，但是直接对数据的分隔让它更适合并行化处理数据，对于大数据集（如Hadoop 和 Spark）与只能加载部分数据的大文件数据排序更有优势，同时它的排序方式也让它拥有稳定性1。
堆排序： 时间复杂度：O(n log n)。 非稳定排序，适合大数据集且需要内存占用固定的情况。 应用于需要频繁查找最大或最小元素的场景，如优先队列、任务调度、图算法中的Dijkstra算法。 希尔排序： 时间复杂度：O(n log n)（最优情况下）。 插入排序的改进版，通过分组减少交换次数，适合中等大小的数据。 适用于中等规模的数组，特别是在嵌入式系统和一些有限资源的设备中。 计数排序： 时间复杂度：O(n+k)（n为数据大小，k为数据范围）。 适用于范围较小的整数排序。 广泛用于处理小整数范围的排序问题，如计数学生成绩、字母表排序等。 基数排序： 时间复杂度：O(nk)（n为数据个数，k为数字位数）。 适合处理整数或字符串，尤其是数据范围较大的情况。 用于排序整数、字符串或IP地址等，广泛应用于大数据处理、数据库索引构建等场景。
查找
线性查找（Linear Search） 逐个检查数组中的元素，直到找到目标元素。 时间复杂度：O(n)，最坏情况下需要检查所有元素。 空间复杂度：O(1)，只需要常数空间。 适用于小数据集或数据无序的情况。 二分查找（Binary Search） 在已排序数组中通过每次将搜索范围减半来查找目标元素。 时间复杂度：O(log n)，每次将问题规模减少一半。 空间复杂度：O(1)，不需要额外空间（在非递归实现时）。 适合在已排序数据中进行查找，如二分查找树、搜索引擎中查找已排序的索引。 哈希查找（Hash Search） 使用哈希表直接查找目标元素。 时间复杂度：O(1)，哈希表允许常数时间内进行查找。 空间复杂度：O(n)，需要额外的空间来存储哈希表。 用于需要快速查找且数据无序的情况，如缓存系统、数据库索引、词典查找等。 注：哈希查找其实是利用了数据结构的特性，通过哈希函数将数据映射到表中的位置，实现高效查找，但前提是哈希函数设计良好，且没有严重的碰撞。而二分查找适用于有序数据集，可以先对无序数据集进行排序。
数据结构
线性数据结构
数组 (Array)：固定大小的顺序存储结构。 链表 (Linked List)：由一系列节点组成，每个节点包含数据和指向下一个节点的指针。 栈 (Stack)：先进后出（LIFO）的数据结构。 队列 (Queue)：先进先出（FIFO）的数据结构。
非线性数据结构
树 (Tree)： 二叉树、平衡树、红黑树等。 常用于实现优先队列（如堆）、搜索树、文件系统等。 图 (Graph)： 有向图、无向图、加权图等。 常用于表示网络拓扑、社交网络等。 堆 (Heap)： 一棵完全二叉树，满足堆的性质。 常用于实现优先队列、堆排序等。
哈希数据结构
哈希表 (Hash Table)：通过哈希函数将数据存储在数组中，查找、插入和删除操作平均时间复杂度为 O(1)。 哈希映射 (HashMap)：Java 中的具体实现，基于哈希表存储键值对， 哈希集合 (HashSet)：基于哈希表实现的集合，存储唯一元素。
问题
1.冒泡、选择、插入排序有什么不同 2.快速、归并排序的实现 3.什么时候会用到二分法
- 稳定性指的是在排序过程中，相等的元素在排序后的相对顺序保持不变。也就是说，如果两个元素值相等，它们在排序后的顺序不会改变。 ↩︎