JavaScript算法实现_排序与搜索算法_技术教程

冒泡排序通过相邻元素比较交换，将最大值逐步移到末尾；2. 选择排序每次从未排序区选最小值插入已排序区末尾；3. 插入排序将未排序元素插入已排序序列的正确位置；4. 快速排序以基准分治递归排序左右子数组；5. 归并排序通过二分后合并有序子数组实现整体有序。

排序与搜索是算法中最基础也最常用的部分。JavaScript 作为一门灵活的编程语言，可以轻松实现各种经典排序和搜索算法。下面介绍几种常见的排序与搜索算法及其 JavaScript 实现。

常见排序算法实现

1. 冒泡排序（Bubble Sort）

冒泡排序通过重复遍历数组，比较相邻元素并交换位置，将最大值“冒泡”到末尾。

function bubbleSort(arr) {
  const len = arr.length;
  for (let i = 0; i < len; 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;
}

2. 选择排序（Selection Sort）

每次从未排序部分找出最小元素，放到已排序序列的末尾。

function selectionSort(arr) {
  const len = arr.length;
  for (let i = 0; i < len; i++) {
    let minIndex = i;
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
  return arr;
}

3. 插入排序（Insertion Sort）

将每个元素插入到前面已排序部分的正确位置。

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

4. 快速排序（Quick Sort）

采用分治法，选择一个基准值，将数组分为小于和大于基准的两部分，递归排序。

function quickSort(arr) {
  if (arr.length <= 1) return arr;
  const pivot = arr[Math.floor(arr.length / 2)];
  const left = arr.filter(x => x < pivot);
  const middle = arr.filter(x => x === pivot);
  const right = arr.filter(x => x > pivot);
  return [...quickSort(left), ...middle, ...quickSort(right)];
}

5. 归并排序（Merge Sort）

将数组不断二分，直到单个元素，再合并有序子数组。

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, 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++]);
} else {
result.push(right[j++]);
}
}
return result.concat(left.slice(i)).concat(right.slice(j));
}

常见搜索算法实现

1. 线性搜索（Linear Search）

从头开始逐个检查元素，直到找到目标值。

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

2. 二分搜索（Binary Search）

适用于已排序数组，通过不断缩小搜索范围，提高效率。

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