第6章 常用学习算法和数据结构1
基本算法是计算机科学领域的核心内容，涉及排序、查找、图算法、动态规划等多种算法。以下是一些常见的基本算法：
1 排序算法：
- 冒泡排序（bubble sort）
冒泡排序（bubble sort）是一种简单的排序算法，它重复地遍历待排序的数列，每次遍历时比较相邻的两个元素，如果它们的顺序错误，就将它们交换。遍历数列的工作重复进行，直到没有再需要交换的元素为止，这意味着数列已经排序完成。
冒泡排序的基本步骤如下：
1 从数列的第一个元素开始，比较相邻的元素。
2 如果相邻元素的顺序错误，就将它们交换。
3 继续比较下一对相邻元素，直到最后一个元素。
4 第一轮遍历结束后，数列中最大的元素将“冒泡”到数列的末端。
5 从数列的第二个元素开始，重复步骤1~4，直到整个数列排序完成。
冒泡排序的时间复杂度为o(n2)，其中n是数列的元素个数。在最佳情况下，冒泡排序的时间复杂度为o(n)。
选择排序（selection sort）
选择排序（selection sort）是一种简单的排序算法，它的工作原理是从未排序的部分中寻找最小（或最大）的元素，并将其放置在已排序部分的末尾。重复这个过程，直到整个数列排序完成。
选择排序的基本步骤如下：
1 从数列的第一个元素开始，该元素被视为已排序部分。
2 从未排序部分的第一个元素开始，寻找最小元素的位置。
3 将找到的最小元素与未排序部分的第一个元素交换。
4 重复步骤2~3，直到整个数列排序完成。
以下是一个选择排序的示例实现（使用javascript）：
```javascript
function selectionsort(arr) {
const n = arrlength;
for (let i = 0; i ＜ n - 1; i++) {
// 寻找未排序部分中最小元素的位置
let minindex = i;
for (let j = i + 1; j ＜ n; j++) {
if (arr[j] ＜ arr[minindex]) {
minindex = j;
}
}
// 将找到的最小元素与未排序部分的第一个元素交换
const temp = arr[i];
arr[i] = arr[minindex];
arr[minindex] = temp;
}
return arr;
}
const arr = [64, 34, 25, 12, 22, 11, 90];
consolelog(selectionsort(arr)); // 输出: [11, 12, 22, 25, 34, 64, 90]
```
选择排序的时间复杂度为o(n2)，其中n是数列的元素个数。在最佳情况下，选择排序的时间复杂度为o(n2)。
- 插入排序（insertion sort）
插入排序（insertion sort）是一种简单的排序算法，它的工作原理是将一个未排序的元素插入到已排序部分的适当位置。插入排序的过程可以想象成将一个新卡片插入到已经排好序的一叠卡片中的正确位置。
-
插入排序的基本步骤如下：
1 从数列的第一个元素开始，该元素被视为已排序部分。
2 从未排序部分的第一个元素开始，与已排序部分的元素进行比较。
3 将未排序部分的元素插入到已排序部分的合适位置，使已排序部分的元素仍保持有序。
4 重复步骤2~3，直到整个数列排序完成。
- 希尔排序（shell sort）
希尔排序（shell sort）是插入排序的一种改进版本，也称为缩小增量排序（dimensionality reduction sort）。希尔排序通过使用递减的增量序列对数列进行多次预排序，使数列更快地接近有序状态，从而提高插入排序的性能。
希尔排序的基本步骤如下：
1 选择一个增量序列（通常是一个递减的整数序列）。
2 按照增量序列将数列分为若干个子序列，每个子序列分别进行插入排序。
3 重复步骤2，直到增量序列变为1，此时整个数列基本有序。
4 使用一次插入排序对整个数列进行微调，使数列完全有序。
以下是一个希尔排序的示例实现（使用javascript）：
```javascript
function shellsort(arr) {
const n = arrlength;
// 初始化增量序列
let gap = mathfloor(n / 2);
while (gap ＞ 0) {
// 按照增量序列进行插入排序
for (let i = gap; i ＜ n; i++) {
let current = arr[i];
let j = i - gap;
while (j ＞= 0 && arr[j] ＞ current) {
arr[j + gap] = arr[j];
j -= gap;
}
arr[j + gap] = current;
}
// 减小增量
gap = mathfloor(gap / 2);
}
return arr;
}
const arr = [64, 34, 25, 12, 22, 11, 90];
consolelog(shellsort(arr)); // 输出: [11, 12, 22, 25, 34, 64, 90]
```
希尔排序的时间复杂度受到增量序列的影响，通常使用hibbard增量序列或knuth增量序列。在最好、最坏和平均情况下，希尔排序的时间复杂度为o(n13)、o(n2)和o(n13)，相较于插入排序有明显改