在本文中,我们将学习一些基础的排序和搜索算法,包括:

  • 冒泡排序(Bubble Sort)
  • 选择排序(Selection Sort)
  • 插入排序(Insertion Sort)
  • 线性搜索(Linear Search)
  • 跳跃搜索(Jump Search)
  • 二分搜索(Binary Search)

排序算法

冒泡排序(Bubble Sort)

冒泡排序是最简单的排序算法之一。它重复地遍历要排序的列表,比对每对相邻的元素,如果它们的顺序错误就交换它们。遍历列表并交换的过程会一直重复到列表已经排序完成。

在冒泡排序中,每次遍历其实都会将列表的末尾第 n 个元素排好序(n 为当前遍历的次数,因此,冒泡排序最大也只需要 n 次循环)。如果我们把一个数组“竖”过来看并把每个元素当作一个气泡,那么排序过程就像是将对应的气泡向上浮,直到它们按照大小顺序排列(因此得名冒泡排序)。

可视化示例

在下面的可视化示例中,我们将演示冒泡排序的工作原理。我们将使用一个仅仅包含 4 个元素的数组 [6, 3, 0, 5] 来演示。

第一次遍历

在第一次遍历中,我们首先比较第一个元素 6 和第二个元素 3,由于 6 > 3,我们交换它们的位置。此时,数组变为 [3, 6, 0, 5]

然后,我们比较第二个元素 6 和第三个元素 0,由于 6 > 0,我们再次交换它们的位置。此时,数组变为 [3, 0, 6, 5]

然后,我们比较第三个元素 6 和第四个元素 5,由于 6 > 5,我们再次交换它们的位置。此时,数组变为 [3, 0, 5, 6]

此时,第一次遍历结束,数组变为 [3, 0, 5, 6],同时我们会发现数组的最大元素 6 已经被排到了最后。

第二次遍历

在第二次遍历中,我们首先比较第一个元素 3 和第二个元素 0,由于 3 > 0,我们交换它们的位置。此时,数组变为 [0, 3, 5, 6]

然后,我们比较第二个元素 3 和第三个元素 5,由于 3 < 5,我们不需要交换它们的位置。此时,数组保持不变 [0, 3, 5, 6]

然后,我们比较第三个元素 5 和第四个元素 6,由于 5 < 6,我们不需要交换它们的位置。此时,数组保持不变 [0, 3, 5, 6]

此时,第二次遍历结束,数组变为 [0, 3, 5, 6],同时我们会发现数组的第二大元素 5 已经被排到了倒数第二的位置,最大的元素 6 仍然在最后。

第三次遍历

在第三次遍历中,我们首先比较第一个元素 0 和第二个元素 3,由于 0 < 3,我们不需要交换它们的位置。此时,数组保持不变 [0, 3, 5, 6]

然后,我们比较第二个元素 3 和第三个元素 5,由于 3 < 5,我们不需要交换它们的位置。此时,数组保持不变 [0, 3, 5, 6]

然后,我们比较第三个元素 5 和第四个元素 6,由于 5 < 6,我们不需要交换它们的位置。此时,数组保持不变 [0, 3, 5, 6]

此时,第三次遍历结束,数组变为 [0, 3, 5, 6],同时我们会发现数组的第三大元素 3 已经被排到了倒数第三的位置。

第四次遍历

在第四次遍历中,我们首先比较第一个元素 0 和第二个元素 3,由于 0 < 3,我们不需要交换它们的位置。此时,数组保持不变 [0, 3, 5, 6]

然后,我们比较第二个元素 3 和第三个元素 5,由于 3 < 5,我们不需要交换它们的位置。此时,数组保持不变 [0, 3, 5, 6]

然后,我们比较第三个元素 5 和第四个元素 6,由于 5 < 6,我们不需要交换它们的位置。此时,数组保持不变 [0, 3, 5, 6]

此时,第四次遍历结束,数组变为 [0, 3, 5, 6],同时我们会发现数组的第四大元素 0 已经被排到了倒数第四的位置。

因此,冒泡排序的最终结果是 [0, 3, 5, 6]

你发现了吗?

但是,其实有的时候我们并不需要真的遍历 n 遍数组。例如,在上述示例中,我们的第三次和第四次遍历都没有发生任何交换,这意味着数组已经是有序的了。因此,我们可以在每次遍历中记录是否发生了交换,如果没有发生交换,我们就可以提前结束排序。

代码示例

下面是冒泡排序的 Java 代码示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.ArrayList;

class BubbleSort {
/**
* 冒泡排序
* @param list 要排序的数组
*/
public static ArrayList<Integer> sort(ArrayList<Integer> list) {
ArrayList<Integer> sorted = new ArrayList<>(list); // 复制一份原数组,不改变原数组

boolean swapped; // 是否发生过交换
do {
swapped = false; // 每次开始排序前,假设没有发生过交换
for (int i = 0; i < sorted.size() - 1; i++) { // 遍历数组,只遍历到倒数第二个元素(因为最后一个元素后面没有元素与之比较)
if (sorted.get(i) > sorted.get(i + 1)) { // 如果当前元素比后一个元素大
// 交换两个元素
int tmp = sorted.get(i);
sorted.set(i, sorted.get(i + 1));
sorted.set(i + 1, tmp);
// 交换过元素后,将swapped设为true
swapped = true;
}
}
} while (swapped); // 如果发生过交换,继续排序,否则代表排序已经完成,退出循环

return sorted;
}
}

选择排序(Selection Sort)

选择排序是另一种简单的排序算法。它的工作原理是:

  1. 我们知道数组的第一个元素是最小的。因此,我们先在数组中找到最小的元素,并将其与第一个元素交换。
  2. 然后,我们知道数组的第一个元素已经是最小的了,因此我们在剩下的元素中找到第二小的元素,并将其与第二个元素交换。
  3. 以此类推,直到所有元素都被排序。

可视化示例

在下面的可视化示例中,我们将演示选择排序的工作原理。我们仍然使用 [6, 3, 0, 5] 这个数组。

  1. 第一步,我们需要找到数组中最小的元素并将其与第一个元素交换。在这个例子中,最小的元素是 0,因此我们将 0 与第一个元素 6 交换,数组变为 [0, 3, 6, 5]
  2. 第二步,我们需要找到剩下的元素中最小的元素并将其与第二个元素交换。在这个例子中,剩下的元素是 [3, 6, 5],最小的元素是 3,因此我们将 3 与第二个元素 6 交换,数组变为 [0, 3, 6, 5]
  3. 第三步,我们需要找到剩下的元素中最小的元素并将其与第三个元素交换。在这个例子中,剩下的元素是 [6, 5],最小的元素是 5,因此我们将 5 与第三个元素 6 交换,数组变为 [0, 3, 5, 6]
  4. 第四步,我们需要找到剩下的元素中最小的元素并将其与第四个元素交换。在这个例子中,剩下的元素是 [6],最小的元素是 6,因此我们不需要交换,数组保持不变 [0, 3, 5, 6]

因此,选择排序的最终结果是 [0, 3, 5, 6]

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class SelectionSort {
/**
* 选择排序
* @param list 要排序的数组
*/
public static ArrayList<Integer> sort(ArrayList<Integer> list) {
ArrayList<Integer> sorted = new ArrayList<>(list); // 复制一份原数组,不改变原数组

int min, minIndex; // 最小值和最小值的索引

for (int i = 0; i < sorted.size() - 1; i++) { // 遍历数组,只遍历到倒数第二个元素(因为最后一个元素不需要再比较/交换了)
// i 同时代表要找到的第 i 小的元素的索引
min = sorted.get(i); // 假设当前元素是最小值
minIndex = i; // 假设当前元素的索引是最小值的索引

for (int j = i + 1; j < sorted.size(); j++) { // 遍历当前元素之后的所有元素,因为当前元素之前的元素已经是有序的而且一定比当前元素小
if (min > sorted.get(j)) { // 如果有比当前元素更小的元素
min = sorted.get(j); // 更新最小值
minIndex = j; // 更新最小值的索引
}
}

// 将最小值与当前元素交换
// (就算最小值是默认的当前元素也不会有问题,因为相当于没有交换)
int tmp = sorted.get(i);
sorted.set(i, min);
sorted.set(minIndex, tmp);
}

return sorted;
}
}

插入排序(Insertion Sort)

插入排序是一种简单的排序算法,它的工作原理是:

  1. 我们创建一个单独的数组,用于存储已经排序好的元素。
  2. 我们从原数组中取出一个元素,然后将其插入到已排序数组的正确位置。
    1. 如果已排序数组为空,我们直接将这个元素插入到已排序数组中。
    2. 如果已排序数组不为空
      1. 如果这个元素比已排序数组的第一个元素小,我们将这个元素插入到已排序数组的第一个位置。
      2. 否则,我们从已排序数组的第一个元素开始,逐个比较这个元素与已排序数组中的元素,直到找到一个比这个元素大的元素,然后将这个元素插入到这个元素的前面。

可视化示例

在下面的可视化示例中,我们将演示插入排序的工作原理。我们仍然使用 [6, 3, 0, 5] 这个数组。

  1. 第一步,我们从原数组中取出第一个元素 6。由于目前已排序数组为空,我们直接将 6 插入到已排序数组中,已排序数组变为 [6]
  2. 第二步,我们要取出的元素是 3。由于 3 比已排序数组中的 6 小,我们将 3 插入到已排序数组的第一个位置,已排序数组变为 [3, 6]
  3. 第三步,我们要取出的元素是 0。由于 0 比已排序数组中的 3 小,我们将 0 插入到已排序数组的第一个位置,已排序数组变为 [0, 3, 6]
  4. 第四步,我们要取出的元素是 5。由于 5 比已排序数组中的 3 大,但是比 6 小,我们将 5 插入到已排序数组的第二个位置,已排序数组变为 [0, 3, 5, 6]

因此,插入排序的最终结果是 [0, 3, 5, 6]

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class InsertionSort {
/**
* 插入排序
* @param list 要排序的数组
*/
public static ArrayList<Integer> sort(ArrayList<Integer> list) {
ArrayList<Integer> sorted = new ArrayList<>(); // 需要一个新的数组来存放已排序的元素

for (int i = 0; i < list.size(); i++) { // 遍历源数组
int num = list.get(i); // 取出当前元素(要向已排序数组中插入的元素)
if (i == 0) {
// 如果已排序数组为空,直接将当前元素放入已排序数组
sorted.add(num);
} else {
if (num <= sorted.get(0)) { // 如果当前元素小于等于已排序数组中的第一个元素
// 那么这个元素就是最小的
// 将已排序数组中的所有元素向后移动一个位置
sorted.add(sorted.get(sorted.size() - 1));
for (int j = sorted.size() - 2; j > 0; j--) {
sorted.set(j, sorted.get(j - 1));
}
// 将当前元素放入已排序数组的第一个位置
sorted.set(0, num);
} else if (num > sorted.get(sorted.size() - 1)) {
// 如果当前元素比已排序数组中的最后一个元素大
// 直接将当前元素放入已排序数组的最后一个位置
sorted.add(num);
} else {
// 否则,将当前元素插入到已排序数组中的合适位置
for (int j = 0; j < sorted.size() - 1; j++) { // 遍历已排序数组,找到合适的位置(搜索循环)
if (sorted.get(j) < num && num <= sorted.get(j + 1)) {
// 如果当前元素大于已排序数组中的第j个元素,且小于/等于第j+1个元素,那么当前元素应该插入到第j+1个位置
// 先将第j+1个位置以及之后的所有元素向后移动一个位置
sorted.add(sorted.get(sorted.size() - 1));
for (int k = sorted.size() - 2; k > j + 1; k--) {
sorted.set(k, sorted.get(k - 1));
}
// 将当前元素插入到第j+1个位置
sorted.set(j + 1, num);
break; // 不需要继续“搜索”循环了
}
}
}
}
}

return sorted;
}
}

搜索算法

线性搜索(Linear Search)

线性搜索是最简单的搜索算法。它的工作原理是:从数组的第一个元素开始,逐个比较每个元素,直到找到目标元素或者遍历完整个数组。

线性搜索时数组/列表可以是无序的。

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class LinearSearch {
/**
* 线性搜索
* @param list 要搜索的数组
* @param target 要搜索的目标
* @return 目标在数组中的索引,如果不存在则返回 -1
*/
public static int search(ArrayList<Integer> list, int target) {
for (int i = 0; i < list.size(); i++) { // 遍历数组
if (list.get(i) == target) { // 如果找到目标
return i; // 返回目标的索引
}
}
return -1; // 如果循环完整结束了,则代表没有找到目标,返回 -1
}
}

跳跃搜索(Jump Search)

跳跃搜索是一种更高效的搜索算法。它的工作原理是:

  1. 我们需要确定要搜索的数组是有序的。
  2. 我们首先确定一个“跳跃步长”(jump step),通常是数组长度的平方根。
  3. 然后,我们从数组的第一个元素开始,每次跳跃步长,直到找到一个元素,这个元素比目标元素大。
  4. 然后,我们知道我们要找的元素一定在本次跳跃的范围内,然后我们可以使用线性搜索来搜索这个范围。

可视化

我们在这里会使用 [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610] 这个有序数组来演示跳跃搜索的工作原理。

我们要搜索的目标是 55

  1. 首先,我们确定跳跃步长为 4(改数组长度为 16,平方根为 4)。
  2. 我们从数组的第一个元素 0 开始,每次跳跃 4 个元素,直到找到一个元素比目标元素 55 大。
    1. 我们首先检查第一个元素 0。由于 0 < 55,我们继续跳跃。
    2. 然后,我们跳跃到了下标为 0 + 4 = 4 的元素 3。由于 3 < 55,我们继续跳跃。
    3. 然后,我们跳跃到了下标为 4 + 4 = 8 的元素 21。由于 21 < 55,我们继续跳跃。
    4. 然后,我们跳跃到了下标为 8 + 4 = 12 的元素 144。由于 144 > 55,我们停止跳跃。
  3. 此时,我们知道目标元素 55 一定在下标 812 之间,然后我们使用线性搜索在这个范围内搜索目标元素。
  4. 我们找到了目标元素 55,并返回它的索引 10

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class JumpSearch {
/**
* 跳跃搜索
* @param list 要搜索的数组
* @param target 要搜索的目标
* @return 目标在数组中的索引,如果不存在则返回 -1
*/
public static int search(ArrayList<Integer> list, int target) {
int step = (int) Math.sqrt(list.size()); // 获取步长

int idx; // 索引
for (idx = 0; idx < list.size(); idx += step) { // 以步长为单位遍历数组
if (list.get(idx) == target) { // 如果找到目标
return idx; // 返回目标的索引
}
if (list.get(idx) > target) { // 如果当前元素大于目标,则目标在当前元素之前,上次检查的元素之后
break; // 结束以步长为单位的遍历
}
}

// 回退一个步长,回到上次检查的元素,遍历这个步长内的元素(或者直到数组末尾)
for (int i = idx - step; i < idx && i < list.size(); i++) {
if (list.get(i) == target) { // 如果找到目标
return i; // 返回目标的索引
}
}

return -1; // 如果循环完整结束了,则代表没有找到目标,返回 -1
}
}

二分搜索(Binary Search)

二分搜索是一种更高效的搜索算法。它的工作原理是:

  1. 我们需要确定要搜索的数组是有序的。
  2. 我们首先确定数组的中间元素。
  3. 如果目标元素等于中间元素,我们找到了目标。
  4. 如果目标元素小于中间元素,由于数组是有序的,我们知道目标元素一定在中间元素的左侧。
  5. 如果目标元素大于中间元素,目标元素一定在中间元素的右侧。
  6. 然后我们减少搜索范围到左侧到中间或者中间到右侧,重复上述步骤,直到找到目标元素或者搜索范围为空(如果搜索范围为空,说明目标元素不存在)。

可视化

我们这里仍然使用 [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610] 这个有序数组来演示二分搜索的工作原理。

我们要搜索的目标是 89

  1. 首先,我们确定数组的中间元素是 21(数组长度为 16,中间元素是下标为 8 的元素)。
  2. 由于 21 < 89,我们知道目标元素一定在中间元素的右侧。
  3. 此时,我们减少搜索范围到 [34, 55, 89, 144, 233, 377, 610]
  4. 我们再次确定中间元素是 144(数组现在长度为 7,中间元素是下标为 3 的元素)。
  5. 由于 144 > 89,我们知道目标元素一定在中间元素的左侧。
  6. 此时,我们减少搜索范围到 [34, 55, 89]
  7. 我们再次确定中间元素是 55(数组现在长度为 3,中间元素是下标为 1 的元素)。
  8. 由于 55 < 89,我们知道目标元素一定在中间元素的右侧。
  9. 此时,我们减少搜索范围到 [89]
  10. 我们找到了目标元素 89,并返回它的索引。不过索引需要考虑到原始数组以及我们减少的搜索范围,所以最终的索引是 11

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class BinarySearch {
/**
* 二分搜索
* @param list 要搜索的数组
* @param target 要搜索的目标
* @return 目标在数组中的索引,如果不存在则返回 -1
*/
public static int search(ArrayList<Integer> list, int target) {
int low = 0; // 低位索引
int high = list.size() - 1; // 高位索引

while (low <= high) { // 当低位索引小于等于高位索引时,才有元素可以搜索
int mid = (low + high) / 2; // 计算中间索引
if (list.get(mid) == target) { // 如果找到目标
return mid; // 返回目标的索引
} else if (list.get(mid) < target) { // 如果中间元素小于目标,则目标在中间元素之后
low = mid + 1; // 低位索引更新为中间索引加一,在中间元素之后的元素中搜索
} else { // 如果中间元素大于目标,则目标在中间元素之前
high = mid - 1; // 高位索引更新为中间索引减一,在中间元素之前的元素中搜索
}
}

return -1; // 如果循环完整结束了,则代表没有找到目标,返回 -1
}
}

GL & HF!