【利用AI让知识体系化】3万多字让你&我快速入门数据结构与算法（一）https://developer.aliyun.com/article/1426051
7.2 冒泡排序
冒泡排序是一种简单直观的排序算法，它重复地遍历数列，一次比较两个元素，如果它们的顺序错误就交换过来，直到没有相邻元素需要交换。因为在数列中较大的元素会逐渐向右边移动，像气泡一样冒泡到数列的右端，因此得名冒泡排序。
冒泡排序的具体实现如下：
- 从数列的第一个元素开始，对每一对相邻元素进行比较，如果顺序不正确则进行交换，这样最后的元素就是数列中的最大值。
- 对除了最后一个元素的所有元素进行相同的操作，直到没有任何一对数字需要比较，此时可得到一个有序数列。
冒泡排序算法的时间复杂度为O(n^2)。在实际应用中，尽管冒泡排序算法的时间复杂度较高，其实现简单，所以在一些简单的场景中，冒泡排序仍然被广泛使用。可以通过优化冒泡排序算法来提高其效率，例如加入一个标志位来记录是否发生过交换，如果没有交换说明数列已经有序，则可以提前结束算法。
下面是使用JavaScript实现冒泡排序算法的代码：
function bubbleSort(arr){ var len = arr.length; for(var i = 0; i < len - 1; i++){ for(var j = 0; j < len - 1 - i; j++){ if(arr[j] > arr[j+1]){ var temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } return arr; }
代码解析：
- 首先定义一个 bubbleSort 函数来实现冒泡排序算法；
- 获取数组 arr 的长度 len；
- 利用两层循环，外层循环控制循环的次数，内层循环进行相邻两个元素的比较；
- 如果相邻的两个元素顺序错误，则交换它们的位置；
- 每一轮内层循环结束后，最大的元素就会被放到了最后面；
- 当外层循环结束后，整个数组就被排序好了；
- 返回排序好的数组。
这段代码实现了冒泡排序算法，并对数组进行了升序排序。
7.3 选择排序
选择排序是一种简单直观的排序算法，它的基本思路是每次从待排序的数据元素中选出最小（或最大）的一个元素，存放在已排好序的数列的起始位置，直到全部待排序的数据元素排完。
选择排序的具体实现如下：
- 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
- 从剩余未排序元素中继续寻找最小（大）元素，重复步骤1，直到全部元素排序完成。
选择排序算法的时间复杂度为O(n^2)。在实际应用中，虽然选择排序算法的时间复杂度相对较高，但其实现简单，所以在一些大小规模较小的数据集上可以获得比较好的性能表现，同时它也是一种稳定的排序算法。但是在解决大规模问题时，排序效率会受到影响，所以需要选择其他更优化的排序算法来处理这类问题。
以下是选择排序的JS代码实现：
function selectionSort(arr) { var len = arr.length; for (var i = 0; i < len - 1; i++) { var minIndex = i; for (var j = i + 1; j < len; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } if (minIndex !== i) { var temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } } return arr; }
在这里，我们首先定义len为数组的长度，然后开始两个循环遍历数组。在外部循环中，我们定义一个minIndex，并将其设置为i，表示我们正在寻找最小值的位置。在内部循环中，我们检查minIndex所在的值是否比当前值更大。如果是，我们将minIndex设置为当前值的位置，以便在完成遍历后知道数组中最小值的位置。在内部循环结束后，我们检查minIndex是否等于i，如果不是，则交换arr[i]和arr[minIndex]的值。最终，我们返回排序后的arr数组。
选择排序算法的时间复杂度为O(n²)，这意味着对于大型数组，它的运行时间可能较长。
7.4 快速排序
快速排序是一种高效的排序算法，它的基本思路是通过分治法将数据序列拆分成两个子序列来排序。具体来说，选择一个基准元素，将序列中比基准元素小的所有元素放到基准元素的左边，将比基准元素大的所有元素放到基准元素的右边，再对左右子序列重复这个过程，直到每个子序列只有一个元素时排序完成。
快速排序的具体实现如下：
- 选取一个基准元素，一般为序列的第一个元素。
- 从序列左侧开始向右搜索，直到找到一个大于或等于基准元素的元素，记录该位置为左侧指针。
- 从序列右侧开始向左搜索，直到找到一个小于或等于基准元素的元素，记录该位置为右侧指针。
- 如果左侧指针位置小于右侧指针位置，交换左右指针位置对应的元素。
- 重复步骤2~4，直到左侧指针位置大于等于右侧指针位置，此时将基准元素放到左右指针交汇处，并返回该位置下标（作为子序列的分隔点）。
- 将整个排序序列被分隔点拆分成两个子序列，分别对两个子序列进行递归排序，直到整个序列有序。
快速排序算法的时间复杂度为O(nlogn)。在实际应用中，快速排序由于实现简易、效率高，成为了各类编程语言中的常用排序算法，但是它对于存在重复元素的数据集会导致频繁的递归以及不平衡的分布，因此会造成快排的性能下降，需要注意。
以下是快速排序的JS代码实现：
function quickSort(arr) { if (arr.length <= 1) { return arr; } var pivotIndex = Math.floor(arr.length / 2); var pivot = arr[pivotIndex]; var left = []; var right = []; for (var i = 0; i < arr.length; i++) { if (i === pivotIndex) { continue; } if (arr[i] < pivot) { left.push(arr[i]); } else { right.push(arr[i]); } } return quickSort(left).concat([pivot], quickSort(right)); }
在这里，我们首先处理基本情况，当输入数组数量为1或更少时，我们只需返回原始数组。在这种情况下，基线条件旨在确保我们不会无限递归下去。
我们通过将数组的大小分成两半来找到一个中心点。中心点通常被称为“主元素”或“主元”，并用以划分数组。
在我们的实现中，我们采用数组的中心作为中心点，并将其存储在变量pivot中。我们创建两个数组，left和right，用于存储pivot左侧和右侧的元素。我们之后通过循环迭代整个数组，将小于pivot的元素放入left，否则将它们放入right。
最后，我们通过递归对left和right子数组进行排序并将它们与pivot一起串联起来从而得到一个完整的排序数组。
快速排序算法的时间复杂度为O(n log n)，效率比选择排序高。但是，在某些情况下，例如数组的大小非常小，或者数组已经几乎排序完成时，所选的主元素可能会导致算法的效率变为O(n²)。
7.5 归并排序
归并排序是一种基于分治思想的排序算法。它的基本思路是将待排序的序列分成若干个子序列，分别进行排序，最后将子序列合并成一个大的有序序列。
具体的实现过程如下：
- 将待排序的序列不断分成两个子序列，直到不能再分为止；
- 对分出的左右两个子序列进行归并排序，递归地使其有序；
- 对排好序的两个子序列合并成一个有序序列。
时间复杂度为O(nlogn)，空间复杂度为O(n)。归并排序是稳定的排序算法，适用于大数据量的排序。
以下是归并排序的JS代码实现：
function merge(left, right) { var result = []; while (left.length && right.length) { if (left[0] <= right[0]) { result.push(left.shift()); } else { result.push(right.shift()); } } while (left.length) { result.push(left.shift()); } while (right.length) { result.push(right.shift()); } return result; } function mergeSort(arr) { if (arr.length <= 1) { return arr; } var middle = Math.floor(arr.length / 2); var left = arr.slice(0, middle); var right = arr.slice(middle); return merge(mergeSort(left), mergeSort(right)); }
在这里，我们首先定义了一个名为merge的函数，用于将两个已排序的数组合并为一个已排序的数组。我们在merge函数中创建一个result数组，并使用while循环迭代两个已排序数组中的元素。如果左侧数组的第一个元素小于或等于右侧数组的第一个元素，则将左侧数组的第一个元素移除并推入result数组中。否则，如果右侧数组的元素更小，则将其移除并推入result数组中。最后，我们返回已排序的result数组。
在我们的归并排序实现中，我们定义一个名为mergeSort的函数，该函数使用递归将输入数组拆分为单个元素数组。使用slice方法和Math.floor计算中心索引点，我们创建left和right子数组。由于我们需要确保我们在拆分子数组之前对其进行排序，因此我们对两个子数组进行递归调用并使用merge函数合并结果。最终，我们返回排序后的result数组。
归并排序算法的时间复杂度为O(n log n)，因此与快速排序算法类似，其效率比选择排序高。归并排序算法在处理大型数据集时更有效，并且不会像快速排序算法那样变得不稳定。
7.6 堆排序
堆排序是一种基于完全二叉树的排序算法。它的基本思路是将待排序的序列转换成一个大根堆（或小根堆），然后将堆顶元素与末尾元素交换，再重新调整堆结构，不断进行这个过程直到整个序列有序为止。
具体的实现过程如下：
- 将待排序的序列构建成一个大根堆（或小根堆）；
- 将堆顶元素与末尾元素交换，然后再调整堆结构，使其满足堆的性质；
- 重复步骤2，直到整个序列有序为止。
时间复杂度为O(nlogn)，空间复杂度为O(1)。堆排序是一种不稳定的排序算法，适用于大数据量的排序。
以下是堆排序的JS代码实现：
function heapSort(arr) { var len = arr.length; for (var i = Math.floor(len / 2); i >= 0; i--) { heapify(arr, len, i); } for (var i = len - 1; i > 0; i--) { swap(arr, 0, i); len--; heapify(arr, len, 0); } return arr; } function heapify(arr, len, i) { var left = 2 * i + 1; var right = 2 * i + 2; var largest = i; if (left < len && arr[left] > arr[largest]) { largest = left; } if (right < len && arr[right] > arr[largest]) { largest = right; } if (largest !== i) { swap(arr, i, largest); heapify(arr, len, largest); } } function swap(arr, i, j) { var temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }
在堆排序算法中，我们首先定义一个名为heapify的函数，该函数在堆中“下沉”一个节点，以便在创建排序堆时保持其最大堆性质。我们在函数中定义left、right和largest变量，用于将节点的两个子节点和最大值进行比较。如果left或right的引用超出堆结构的边界，则不会进行比较。如果arr[left]或arr[right]大于arr[largest]，则将largest更新为left或right的值。最后，如果最大值是left或right而不是i本身，则我们要调用swap函数交换这2个位置的值，并递归调用heapify函数以确保此次修改后子堆仍然满足最大堆性质。
在我们的堆排序实现中，我们首先针对数组的前一半元素调用heapify函数，以便在初始堆中满足最大堆性质。之后执行第二个for循环，该循环遍历数组中每个元素。该循环中，我们首先使用swap函数将堆的根节点移动到当前数组的末尾，然后通过减少堆的长度和调用heapify函数将根节点下沉，以保持最大堆的性质。通过此逐步减小堆大小的过程来创建排好序的数组。
堆排序算法的时间复杂度为O(n log n)，因此与快速排序算法和归并排序算法类似，其效率比选择排序高。但是，堆排序算法需要对输入数组本身进行就地修改，而不是返回新的排序数组。
7.7 排序算法的比较
常见的排序算法包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序等。
以下是各种排序算法的比较表：
| 算法名称 | 时间复杂度（平均情况下） | 时间复杂度（最坏情况下） | 时间复杂度（最好情况下） | 空间复杂度 | 稳定性 |
| 冒泡排序（Bubble Sort） | O(n²) | O(n²) | O(n) | O(1) | 稳定 |
| 选择排序（Selection Sort） | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 |
| 插入排序（Insertion Sort） | O(n²) | O(n²) | O(n) | O(1) | 稳定 |
| 快速排序（Quick Sort） | O(n log n) | O(n²) | O(n log n) | O(log n) | 不稳定 |
| 归并排序（Merge Sort） | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 |
| 堆排序（Heap Sort） | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 |
在以上表中，每个算法的时间复杂度在不同情况下的表现可能不尽相同。
对于每个算法，最好情况下的时间复杂度是指通过输入数据充分利用算法的优化方法时的时间。而最坏情况下的时间复杂度则表示无论输入数据如何都会得到糟糕的性能。平均情况下的时间复杂度代表在输入数据样本上运行时所需的平均时间成本。
“稳定性”指算法能否保持排序前由相等值组成元素之间的相对顺序。如果相等的元素在排序过程中始终保持在出现的顺序，则该算法被认为是稳定的。
需要注意的是，对于大多数排序算法，其空间复杂度都不依赖于输入数据的大小。而堆排序算法对于大型数据集而言具有空间优势，因为它能够就地排序而不需要额外的空间。
它们在数据结构、时间复杂度和空间复杂度等方面各有优缺点。
数据结构：
冒泡排序、选择排序、插入排序、希尔排序都是基于比较的排序算法，它们不需要额外的数据结构支持。
归并排序和堆排序是基于分治思想的排序算法，需要使用额外的数据结构（如归并排序中需要使用额外的空间存储临时排好序的序列，堆排序需要使用堆）。
快速排序是一种既基于比较又基于分治思想的排序算法，不需要额外的数据结构支持。
时间复杂度：
冒泡排序、选择排序、插入排序的时间复杂度都是O(n^2)，不适用于大数据量的排序。
希尔排序的时间复杂度在最坏情况下是O(n^2)，但在平均情况下，它比较快，时间复杂度为O(nlogn)。
归并排序、堆排序、快速排序的时间复杂度都是O(nlogn)。
空间复杂度：
冒泡排序、选择排序、插入排序、希尔排序的空间复杂度都是O(1)，不需要额外的空间支持。
归并排序的空间复杂度为O(n)，需要使用额外的空间存储临时排好序的序列。
堆排序的空间复杂度为O(1)，但是堆的实现需要使用数组存储，会占用额外的空间。
快速排序的空间复杂度最坏情况下为O(n)，平均情况下为O(logn)。
总体来说，对于小数据量的排序，可以使用冒泡排序、选择排序、插入排序。对于中等规模的数据量，可以使用希尔排序、快速排序、堆排序。对于大规模数据的排序，可以使用归并排序。不同的排序算法在不同情况下各有优劣，需要根据具体情况选择合适的排序算法。
第八章：搜索算法
8.1 顺序搜索
顺序搜索，也称线性搜索，是一种简单的查找算法，它逐个对待搜索表中的记录进行比较，直到找到目标记录或搜索完整个表为止。
算法步骤如下：
- 从待搜索的序列的第一个记录开始，依次遍历每个记录，直到找到目标记录或者搜索完整个序列为止；
- 如果找到目标记录，则返回该记录在序列中的下标；
- 如果搜索完整个序列都没有找到目标记录，则返回“未找到”。
顺序搜索的时间复杂度为O(n)，空间复杂度为O(1)。对于小规模的数据集，顺序搜索是一种比较简单有效的查找算法，但是对于大规模的数据集，它的时间复杂度过高，效率不高，此时应当选择更高效的查找算法，如二分查找。
8.2 二分搜索
二分搜索，也称折半搜索，是一种高效的查找算法，用于在有序数组中查找目标元素。
算法步骤如下：
- 确定待搜索数列的中间位置mid；
- 判断mid处的元素与目标元素的大小关系，并根据大小关系缩小搜索范围；
- 如果找到目标元素，则返回该元素在数列中的下标；
- 如果未找到目标元素，则重复步骤1~3。
代码实现（Python）如下：
def binary_search(nums, target): left, right = 0, len(nums) - 1 while left <= right: mid = left + (right - left) // 2 if nums[mid] == target: return mid elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return -1 # 未找到 # 测试 nums = [1, 2, 3, 4, 5, 6, 7, 8, 9] target = 5 print(binary_search(nums, target)) # 4
二分搜索的时间复杂度为O(log n)，空间复杂度为O(1)，它的效率比顺序搜索要高得多，因此适用于大规模数据的查找。但是，需要注意的是，二分搜索仅适用于有序数据集。如果数据集没有排序，则需要先进行排序操作，这可能会带来额外的时间复杂度。
8.3 哈希表
哈希表是一种基于散列表实现的数据结构，它通过哈希函数将每个键映射到一个索引（桶）上，并将对应的值存储在该桶中。通过哈希函数的快速定位，哈希表可以在O(1)的时间复杂度内进行查找、插入和删除等操作。
具体的实现过程如下：
- 定义一个哈希函数，将键映射到桶索引上；
- 初始化一个数组（哈希表），将每个桶初始化为空；
- 对于每个键值对，根据哈希函数得到对应的桶索引，然后将值存储在对应桶中；
- 对于查找操作，根据哈希函数得到键对应的桶索引，然后在对应桶中查找是否存在该键；
- 对于插入操作，根据哈希函数得到键对应的桶索引，然后插入键值对到对应桶中；
- 对于删除操作，根据哈希函数得到键对应的桶索引，然后在对应桶中删除该键值对。
哈希表的实现可以采用开放地址法和链表法两种方式。开放地址法通过线性探测、二次探测、双重散列等技术解决哈希冲突；链表法使用链表将哈希表中的每个桶组织成一个链表。
哈希表在空间利用率、平均时间复杂度和数据的动态性等方面都具有优点，因此被广泛应用于检索系统、缓存系统、数据库索引等。但是哈希表也存在一些缺点，例如哈希冲突、哈希函数的设计等方面需要考虑，否则会影响哈希表的性能。
8.4 搜索算法的比较
搜索算法有许多种，下面是几种常见的搜索算法的比较：
- 线性搜索算法（Sequential Search Algorithm）：适用于小数据量的搜索，其时间复杂度为O(n)。每次从待搜索的列表中逐个比较元素，直到找到目标元素或者搜索列表已全部搜索完。
- 二分搜索算法（Binary Search Algorithm）：适用于大数据量有序列表的搜索，其时间复杂度为O(log n)。每次从搜索列表的中间元素开始比较，如果中间元素不是目标元素，则根据大小关系选择左半部分或右半部分进行搜索，重复这个过程直到找到目标元素或者搜索区间为空。
- 广度优先搜索算法（Breadth-First Search Algorithm）：适用于有向无环图的搜索，其时间复杂度为O(n+m)，其中n为节点数，m为边数。从起始节点出发，通过广度优先依次遍历所有节点，直到找到目标节点或者搜索完成整个图。
- 深度优先搜索算法（Depth-First Search Algorithm）：适用于有向无环图的搜索，其时间复杂度为O(n+m)，其中n为节点数，m为边数。从起始节点出发，通过深度优先遍历所有可达节点，直到找到目标节点或者搜索完成整个图。
- A搜索算法（A*Search Algorithm）：适用于带权有向图的搜索，可以找到最短路径。其时间复杂度与具体实现有关，最坏情况下为O(b^d)，其中b为分支因子，d为最短路径长度。通过综合考虑实际代价和启发函数的估计代价，将搜索方向引向最有可能是最短路径的方向，从而提高搜索效率。
不同的搜索算法适用于不同的场景和问题，需要根据具体的需求选择合适的搜索算法。
【利用AI让知识体系化】3万多字让你&我快速入门数据结构与算法（三）https://developer.aliyun.com/article/1426053
