第8章 常用学习算法数据结构3
- 堆排序（heap sort）
堆排序（heap sort）是一种基于比较的排序算法。它将数列构建成一个大顶堆（或小顶堆），然后依次将根节点与最后一个叶子节点交换，并重新调整堆结构。这样，每一次交换都会将当前最大值（或最小值）移到数列的末端，最终得到一个有序数列。
堆排序的基本步骤如下：
1 将数列构建成一个大顶堆（或小顶堆）。
2 交换根节点（最大值或最小值）与最后一个叶子节点。
3 重新调整堆结构，使其保持大顶堆（或小顶堆）特性。
4 对新的数列重复步骤2和3，直到整个数列有序。
以下是一个堆排序的示例实现（使用javascript）：
```javascript
function heapsort(arr) {
const n = arrlength;
// 构建大顶堆
for (let i = mathfloor(n / 2) - 1; i ＞= 0; i--) {
heapify(arr, n, i);
}
// 循环交换根节点和最后一个叶子节点
for (let i = n - 1; i ＞ 0; i--) {
// 将最大值移到数列的末端
[arr[0], arr[i]] = [arr[i], arr[0]];
// 重新调整堆结构
heapify(arr, i, 0);
}
return arr;
}
function heapify(arr, n, i) {
const largest = i;
const left = 2 i + 1;
const 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) {
// 交换节点
[arr[i], arr[largest]] = [arr[largest], arr[i]];
// 递归调整堆结构
heapify(arr, n, largest);
}
}
const arr = [64, 34, 25, 12, 22, 11, 90];
consolelog(heapsort(arr)); // 输出: [11, 12, 22, 25, 34, 64, 90]
```
堆排序的平均时间复杂度为o(nlogn)，在所有相同时间复杂度的排序算法中，其性能较好。堆排序在处理大数据集时具有稳定的性能，但在处理小规模数据集时，由于堆结构调整的开销，性能可能不如其他排序算法。
2 查找算法：
- 线性查找（linear search）
线性查找（linear search）是一种简单的查找算法，用于在已排序的数列中查找特定元素。线性查找的基本思想是按顺序依次比较每个元素，直到找到目标元素或遍历完整个数列。
线性查找的基本步骤如下：
1 从数列的第一个元素开始，依次比较每个元素与目标元素。
2 如果当前元素与目标元素相同，则查找成功，返回当前元素的索引。
3 如果遍历完整个数列仍未找到目标元素，则查找失败，返回-1或null（表示目标元素不存在于数列中）。
以下是一个线性查找的示例实现（使用javascript）：
```javascript
function linearsearch(arr, target) {
for (let i = 0; i ＜ arrlength; i++) {
if (arr[i] === target) {
return i;
}
}
return -1; // 目标元素不存在于数列中
}
const arr = [1, 3, 5, 7, 9];
const target = 7;
const index = linearsearch(arr, target);
if (index !== -1) {
consolelog(`目标元素 {target} 在数列中的索引为 {index}`);
} else {
consolelog(`目标元素 {target} 不存在于数列中`);
}
```
线性查找的时间复杂度为o(n)，其中n是数列的元素个数。尽管线性查找在大部分情况下性能较差，但它是一种简单且易于理解的查找算法。在实际应用中，线性查找通常仅适用于小型数据集。对于大型数据集，可以采用更高效的查找算法，如二分查找（binary search）。