Flutter搜索算法插件search_algorithms_dart的使用

search_algorithms_dart 是一个 Dart 包，提供了多种搜索算法，包括线性搜索、二分搜索和跳步搜索，并且包含了一个用于对字符串列表进行排序的快速排序工具。

安装

在 pubspec.yaml 文件中添加以下依赖：

dependencies:
  search_algorithms: ^1.0.0

然后运行 dart pub get 来安装该包。

使用

导入包

import 'package:search_algorithms/search_algorithms.dart';

快速排序扩展

这个扩展为 List<String> 类型添加了 quickSort 方法，以便使用快速排序算法对字符串列表进行排序。

extension QuickSortString on List<String> {
  List<String> quickSort() {
    if (length < 2) {
      return this; // 如果列表长度小于2，直接返回
    } else {
      String pivot = this[Random().nextInt(length)]; // 随机选择一个基准元素
      List<String> left = [
        for (String element in this)
          if (element.compareTo(pivot) < 0) element // 小于基准的元素
      ];
      List<String> equal = [
        for (String element in this)
          if (element.compareTo(pivot) == 0) element // 等于基准的元素
      ];
      List<String> right = [
        for (String element in this)
          if (element.compareTo(pivot) > 0) element // 大于基准的元素
      ];

      return left.quickSort() + equal + right.quickSort(); // 递归排序左右部分
    }
  }
}

搜索算法

线性搜索

线性搜索是按顺序遍历列表以查找目标元素的方法。

int linearSearch(List<String> list, String target) {
  for (int i = 0; i < list.length; i++) {
    if (list[i] == target) {
      return i; // 元素找到，返回其索引
    }
  }
  return -1; // 元素未找到，返回 -1
}

二分搜索

二分搜索是一种通过分治法查找元素的方法。列表必须是有序的。如果列表未排序，可以将 isSorted 设置为 false，它会先对列表进行排序。

int binarySearch({
  required List<String> list,
  required String target,
  bool isSorted = false,
}) {
  if (!isSorted) {
    list = List<String>.from(list).quickSort(); // 如果未排序，则先排序
  }

  int left = 0;
  int right = list.length - 1;

  while (left <= right) {
    int mid = left + (right - left) ~/ 2; // 计算中间索引

    if (list[mid] == target) {
      return mid; // 元素找到，返回其索引
    } else if (list[mid].compareTo(target) < 0) {
      left = mid + 1; // 在右半部分搜索
    } else {
      right = mid - 1; // 在左半部分搜索
    }
  }

  return -1; // 元素未找到，返回 -1
}

跳步搜索

跳步搜索通过固定步长在列表中跳跃来查找元素。列表必须是有序的。如果列表未排序，可以将 isSorted 设置为 false，它会先对列表进行排序。

int jumpSearch({
  required List<String> list,
  required String target,
  bool isSorted = false,
}) {
  if (!isSorted) {
    list = List<String>.from(list).quickSort(); // 如果未排序，则先排序
  }

  int n = list.length;
  int step = sqrt(n).toInt(); // 跳跃步长
  int prev = 0;

  // 跳跃搜索直到找到可能包含目标元素的块
  while (list[min(step, n) - 1].compareTo(target) < 0) {
    prev = step;
    step += sqrt(n).toInt();
    if (prev >= n) {
      return -1; // 元素未找到，返回 -1
    }
  }

  // 在识别出的块内进行线性搜索
  for (int i = prev; i < min(step, n); i++) {
    if (list[i] == target) {
      return i; // 元素找到，返回其索引
    }
  }

  return -1; // 元素未找到，返回 -1
}

示例

下面是一个如何使用 SearchAlgorithms 类的示例：

import 'package:search_algorithms/search_algorithms.dart';

void main() {
  List<String> list = ['apple', 'banana', 'cherry', 'date', 'fig', 'grape'];

  // 线性搜索
  int linearResult = SearchAlgorithms.linearSearch(list, 'cherry');
  print('线性搜索结果: $linearResult'); // 输出: 线性搜索结果: 2

  // 二分搜索
  int binaryResult = SearchAlgorithms.binarySearch(list: list, target: 'date');
  print('二分搜索结果: $binaryResult'); // 输出: 二分搜索结果: 3

  // 跳步搜索
  int jumpResult = SearchAlgorithms.jumpSearch(list: list, target: 'fig');
  print('跳步搜索结果: $jumpResult'); // 输出: 跳步搜索结果: 4
}