JavaScript 排序算法详解：从冒泡到基数排序

本文将详细介绍 10 种常见的 JavaScript 排序算法，并提供相应的示例代码，帮助您更好地理解和应用这些算法。

1. 冒泡排序（Bubble Sort）

冒泡排序是一种简单的排序算法，它重复地遍历要排序的列表，比较相邻的两个元素，如果它们顺序错误就交换它们。

function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - i - 1; 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) {
  for (let i = 0; i < arr.length - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    [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 key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
}

4. 希尔排序（Shell Sort）

希尔排序是一种改进的插入排序算法，它通过将列表分成多个子列表，然后分别对子列表进行插入排序，最后将所有子列表合并，来提高排序效率。

function shellSort(arr) {
  let n = arr.length;
  for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {
    for (let i = gap; i < n; i++) {
      let key = arr[i];
      let j = i;
      while (j >= gap && arr[j - gap] > key) {
        arr[j] = arr[j - gap];
        j -= gap;
      }
      arr[j] = key;
    }
  }
  return arr;
}

5. 归并排序（Merge Sort）

归并排序是一种基于分治思想的排序算法，它将列表递归地分成两个子列表，然后分别对子列表进行排序，最后将两个已排序的子列表合并成一个有序的列表。

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

function merge(left, right) {
  let result = [];
  let i = 0;
  let 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;
}

6. 快速排序（Quick Sort）

快速排序也是一种基于分治思想的排序算法，它选择一个元素作为枢纽元素，将列表分成两个子列表：小于枢纽元素的元素和大于枢纽元素的元素。然后递归地对两个子列表进行排序。

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

7. 堆排序（Heap Sort）

堆排序是一种基于堆数据结构的排序算法，它首先将列表构建成一个最大堆，然后重复地将堆顶元素（最大元素）与列表的最后一个元素交换，并调整堆，直到所有元素都被排序。

function heapSort(arr) {
  let n = arr.length;
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }
  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    heapify(arr, i, 0);
  }
  return arr;
}

function heapify(arr, n, i) {
  let largest = i;
  let left = 2 * i + 1;
  let right = 2 * i + 2;
  if (left < n && arr[left] > arr[largest]) {
    largest = left;
  }
  if (right < n && arr[right] > arr[largest]) {
    largest = right;
  }
  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, n, largest);
  }
}

8. 计数排序（Counting Sort）

计数排序是一种线性时间排序算法，它适用于元素值在一定范围内的列表。它通过创建一个计数数组来统计每个元素出现的次数，然后根据计数数组来排序列表。

function countingSort(arr) {
  let max = Math.max(...arr);
  let count = new Array(max + 1).fill(0);
  for (let i = 0; i < arr.length; i++) {
    count[arr[i]]++;
  }
  let sortedArr = [];
  for (let i = 0; i < count.length; i++) {
    while (count[i] > 0) {
      sortedArr.push(i);
      count[i]--;
    }
  }
  return sortedArr;
}

9. 桶排序（Bucket Sort）

桶排序是一种将列表分成多个桶，然后分别对每个桶进行排序，最后将所有桶合并的排序算法。它适用于元素值均匀分布的列表。

function bucketSort(arr) {
  let buckets = [];
  let min = Math.min(...arr);
  let max = Math.max(...arr);
  let bucketSize = Math.ceil((max - min + 1) / arr.length);
  for (let i = 0; i < arr.length; i++) {
    let bucketIndex = Math.floor((arr[i] - min) / bucketSize);
    if (!buckets[bucketIndex]) {
      buckets[bucketIndex] = [];
    }
    buckets[bucketIndex].push(arr[i]);
  }
  let sortedArr = [];
  for (let i = 0; i < buckets.length; i++) {
    if (buckets[i]) {
      buckets[i].sort((a, b) => a - b);
      sortedArr.push(...buckets[i]);
    }
  }
  return sortedArr;
}

10. 基数排序（Radix Sort）

基数排序是一种非比较排序算法，它通过将列表按每个数字位的数值进行排序来完成排序。它适用于元素值是整数的列表。

function radixSort(arr) {
  let max = Math.max(...arr);
  let maxLength = Math.floor(Math.log10(max)) + 1;
  for (let i = 0; i < maxLength; i++) {
    arr = countingSortForRadix(arr, i);
  }
  return arr;
}

function countingSortForRadix(arr, exp) {
  let n = arr.length;
  let output = new Array(n).fill(0);
  let count = new Array(10).fill(0);
  for (let i = 0; i < n; i++) {
    count[Math.floor((arr[i] / Math.pow(10, exp)) % 10)]++;
  }
  for (let i = 1; i < 10; i++) {
    count[i] += count[i - 1];
  }
  for (let i = n - 1; i >= 0; i--) {
    output[count[Math.floor((arr[i] / Math.pow(10, exp)) % 10)] - 1] = arr[i];
    count[Math.floor((arr[i] / Math.pow(10, exp)) % 10)]--;
  }
  return output;
}

总结

本文介绍了 10 种常见的 JavaScript 排序算法，并提供相应的示例代码。您可以根据实际需求选择合适的算法。

注意： 这些算法的效率取决于列表的规模和元素的分布。在实际应用中，建议根据具体情况选择最优的算法。