JavaScript算法与数据结构：排序和搜索算法介绍

在计算机科学中，算法和数据结构是非常重要的基础知识。它们可以帮助我们解决各种计算问题，并提高代码的性能。

本文将介绍几种常见的排序和搜索算法，并使用JavaScript语言进行演示和实现。

排序算法

排序算法是将一组元素按照特定的顺序重新排列的算法。常见的排序算法有冒泡排序、选择排序、插入排序、快速排序、归并排序等。

冒泡排序

冒泡排序是一种简单直观的比较排序算法。它重复地遍历要排序的列表，比较每对相邻的元素，并根据需要交换它们的位置，直到整个列表排序完成。

function bubbleSort(arr) {
  let len = arr.length;
  for (let i = 0; i < len - 1; i++) {
    for (let j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        // 交换位置
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

let arr = [5, 3, 8, 4, 2];
console.log(bubbleSort(arr)); // 输出 [2, 3, 4, 5, 8]

选择排序

选择排序是一种简单直观的排序算法。它每次从未排序区间选择最小（或最大）的元素放入已排序的区间的末尾，直到全部元素排序完成。

function selectionSort(arr) {
  let len = arr.length;
  for (let i = 0; i < len - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    // 交换位置
    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
  }
  return arr;
}

let arr = [5, 3, 8, 4, 2];
console.log(selectionSort(arr)); // 输出 [2, 3, 4, 5, 8]

插入排序

插入排序是一种简单直观的排序算法。它将待排序的序列分成已排序和未排序区间，每次从未排序区间选择第一个元素插入到已排序区间的合适位置，直到全部元素排序完成。

function insertionSort(arr) {
  let len = arr.length;
  for (let i = 1; i < len; i++) {
    let temp = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > temp) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = temp;
  }
  return arr;
}

let arr = [5, 3, 8, 4, 2];
console.log(insertionSort(arr)); // 输出 [2, 3, 4, 5, 8]

快速排序

快速排序是一种常用的排序算法，它使用分治的思想将问题拆分成小问题。通过一趟排序将待排序的记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分小，然后递归地对两部分记录进行排序。

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  let pivotIndex = Math.floor(arr.length / 2);
  let pivot = arr.splice(pivotIndex, 1)[0];
  let left = [];
  let right = [];
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat([pivot], quickSort(right));
}

let arr = [5, 3, 8, 4, 2];
console.log(quickSort(arr)); // 输出 [2, 3, 4, 5, 8]

归并排序

归并排序是一种稳定的排序算法，它使用分治的思想将问题拆分成小问题，然后将小问题的解合并成原问题的解。归并排序通过递归地将数组拆分为只有一个元素的子数组，然后再将其合并，最终得到排序后的数组。

function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  let mid = Math.floor(arr.length / 2);
  let left = arr.slice(0, mid);
  let right = arr.slice(mid);
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  let result = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }
  while (i < left.length) {
    result.push(left[i]);
    i++;
  }
  while (j < right.length) {
    result.push(right[j]);
    j++;
  }
  return result;
}

let arr = [5, 3, 8, 4, 2];
console.log(mergeSort(arr)); // 输出 [2, 3, 4, 5, 8]

搜索算法

搜索算法是在一个给定的数据集中寻找特定元素的算法。常见的搜索算法有线性搜索、二分搜索等。

线性搜索

线性搜索是一种直观的搜索算法，它从数据集的开头开始遍历每个元素，直到找到目标元素或遍历完整个数据集。

function linearSearch(arr, target) {
  let len = arr.length;
  for (let i = 0; i < len; i++) {
    if (arr[i] === target) {
      return i;
    }
  }
  return -1;
}

let arr = [5, 3, 8, 4, 2];
console.log(linearSearch(arr, 4)); // 输出 3

二分搜索

二分搜索是一种高效的搜索算法，它要求数据集必须有序。它通过将数据集分成两半，然后判断目标元素在哪一半中，再继续在该半部分中进行二分搜索，直到找到目标元素或确定目标元素不存在于数据集中。

function binarySearch(arr, target) {
  let low = 0, high = arr.length - 1;
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return -1;
}

let arr = [2, 3, 4, 5, 8];
console.log(binarySearch(arr, 4)); // 输出 2

总结

本文介绍了几种常见的排序和搜索算法，并给出了使用JavaScript语言实现的示例代码。这些算法和数据结构对于解决计算问题、提高代码性能非常重要，希望读者能够在实际开发中灵活运用。如果想要深入学习和掌握更多算法和数据结构，请参考相关的教材和资料。

本文来自极简博客，作者：天使之翼，转载请注明原文链接：JavaScript算法与数据结构：排序和搜索算法介绍