关于程序员:前端需要掌握的十大排序算法

前端须要把握的十大排序算法

学习排序算法的目标

1. 解决理论问题：排序算法是计算机科学中的根底算法之一，简直在任何畛域的软件开发中都会遇到排序的需要。理解各种排序算法可能帮忙程序员解决理论问题，提供高效的数据处理和查问性能。
2. 性能优化：排序算法的抉择会对程序的性能产生间接影响。不同的排序算法在工夫复杂度和空间复杂度上有不同的特点，理解不同排序算法的性能特点能够帮忙程序员抉择最适宜的算法，优化程序的执行效率。
3. 数据结构：排序算法与数据结构密切相关。对于不同类型的数据结构，抉择适合的排序算法可能充分发挥数据结构的劣势，进步数据处理的效率。例如，对于链表构造，插入排序可能更加实用，而对于数组构造，疾速排序或堆排序可能更高效。
4. 算法设计和剖析：排序算法是算法设计和剖析的经典案例之一。通过学习排序算法，程序员能够造就良好的算法设计思维，学会剖析和评估算法的性能，进步解决问题的能力。
5. 面试筹备：排序算法是面试中常见的考点之一。许多技术面试会波及排序算法的实现和性能剖析，相熟排序算法能够帮忙程序员在面试中更好地展现本人的技术能力。

总之，学习排序算法对程序员来说是十分重要的，它不仅能晋升解决问题的能力和算法设计思维，还能优化程序性能，为面试做好筹备。

常见的排序算法

常见的排序算法有以下几种：

1. 冒泡排序（Bubble Sort）：比拟相邻元素的大小，如果逆序则替换，每一轮将最大的元素冒泡到最初。工夫复杂度为 O(n^2)。
2. 抉择排序（Selection Sort）：每次从未排序的局部抉择最小的元素，放到已排序局部的开端。工夫复杂度为 O(n^2)。
3. 插入排序（Insertion Sort）：将未排序的元素一一插入到已排序局部的适合地位，工夫复杂度为 O(n^2)。
4. 疾速排序（Quick Sort）：选取一个基准元素，将比基准小的元素放在右边，比基准大的元素放在左边，而后对左右两边递归地进行疾速排序。均匀工夫复杂度为 O(nlogn)。
5. 归并排序（Merge Sort）：将待排序数组一直二分为两个子数组，别离进行排序，而后将两个有序的子数组合并成一个有序数组。工夫复杂度为 O(nlogn)。
6. 堆排序（Heap Sort）：利用二叉堆数据结构进行排序。首先构建最大堆，而后将堆顶元素与最初一个元素替换，而后调整堆，再反复该过程，最终失去有序序列。工夫复杂度为 O(nlogn)。
7. 希尔排序（Shell Sort）：将待排序数组依照肯定增量分组，对每个分组进行插入排序，而后逐步放大增量，直到增量为 1，最初进行一次插入排序。工夫复杂度取决于增量序列的抉择。
8. 计数排序（Counting Sort）：实用于待排序元素范畴较小的状况，统计每个元素呈现的次数，而后依据统计后果进行排序。工夫复杂度为 O(n+k)，其中 k 为元素的范畴。
9. 桶排序（Bucket Sort）：将待排序元素调配到不同的桶中，对每个桶中的元素进行排序，最初按程序将桶中的元素顺次取出。工夫复杂度取决于桶的数量和元素散布的平均水平。
10. 基数排序（Radix Sort）：依照元素的位数进行排序，从低位到高位顺次进行排序，每一位应用稳固的排序算法。工夫复杂度为 O(d*(n+k))，其中 d 为最大元素的位数，k 为基数。

这些排序算法各有优劣，实用于不同的场景和数据规模。抉择适合的排序算法能够进步排序效率。

冒泡排序

冒泡排序（Bubble Sort）是一种简略的排序算法，它反复地遍历要排序的列表，顺次比拟相邻的两个元素，并依照升序或降序替换它们的地位，直到整个列表排序实现。

实现原理：

1. 从列表的第一个元素开始，将其与下一个元素比拟，如果程序谬误（升序时以后元素大于下一个元素，降序时以后元素小于下一个元素），则替换它们的地位。
2. 持续比拟下一个相邻元素，反复上述步骤，直到遍历到列表的最初一个元素。
3. 反复步骤 1 和 2，直到没有任何元素须要替换地位，即列表已排序实现。

示例代码：

// 一般实现
function bubbleSort(arr) {
  const 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]) {const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  
  return arr;
}

// 示例用法
const array = [4, 2, 2, 8, 3, 3, 10, 5, 6, 2, 3];
const sortedArray = bubbleSort(array);
console.log(sortedArray);  // 输入: [2, 2, 2, 3, 3, 3, 4, 5, 6, 8, 10]

// 优化实现，如果发现曾经实现排序，通过标记提前退出循环
function bubbleSort(arr) {
  const len = arr.length;
  let swapped;

  // 外层循环管制排序的轮数
  for (let i = 0; i < len - 1; i++) {
    swapped = false;

    // 内层循环进行相邻元素的比拟和替换
    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]];
        swapped = true;
      }
    }

    // 如果某轮循环没有进行任何替换，则阐明列表已排序实现，能够提前退出循环
    if (!swapped) {break;}
  }

  return arr;
}

// 测试
const array = [4, 2, 2, 8, 3, 3, 10, 5, 6, 2, 3];
console.log(bubbleSort(array));  // 输入: [2, 2, 2, 3, 3, 3, 4, 5, 6, 8, 10]

性能剖析：

工夫复杂度：冒泡排序的工夫复杂度为 O(n^2)，其中 n 是要排序的元素数量。最好状况下，如果列表曾经有序，冒泡排序的工夫复杂度能够优化到 O(n)，通过减少一个标记位来判断是否产生替换，提前结束循环。
空间复杂度：冒泡排序的空间复杂度为 O(1)，即不须要额定的存储空间。
稳定性：冒泡排序是一种稳固的排序算法，相等元素的绝对程序在排序前后不会扭转。

应用场景：

冒泡排序是一种简略但效率较低的排序算法，实用于小规模的列表。在大规模数据的状况下，其余高效的排序算法（如疾速排序、归并排序）更常被应用。然而，冒泡排序在某些非凡状况下可能会有其用武之地，例如当输出列表简直曾经有序时，冒泡排序可能会比其余算法更加高效。

抉择排序

抉择排序（Selection Sort）是一种简略直观的排序算法，它的原理是每一轮从待排序的元素中抉择最小（或最大）的元素，将其与序列中的第一个元素替换地位，而后再从剩下的元素中抉择最小（或最大）的元素，与序列中的第二个元素替换地位，以此类推，直到整个序列有序。

示例代码：

function selectionSort(arr) {
  const 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; // 更新最小索引}
    }

    // 将最小值与以后地位替换
    if (minIndex !== i) {[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
  
  return arr;
}

// 示例用法
const array = [4, 2, 2, 8, 3, 3, 10, 5, 6, 2, 3];
const sortedArray = selectionSort(array);
console.log(sortedArray); // 输入: [2, 2, 2, 3, 3, 3, 4, 5, 6, 8, 10]

性能剖析：

• 工夫复杂度：抉择排序的工夫复杂度为 O(n^2)，其中 n 是待排序数组的长度。每一轮须要从未排序区中抉择最小元素，共须要进行 (n-1) + (n-2) + … + 1 = n*(n-1)/2 次比拟。
• 空间复杂度：抉择排序的空间复杂度为 O(1)，即不须要额定的存储空间。
• 稳定性：抉择排序是一种不稳固的排序算法，相等元素的绝对程序在排序过程中可能产生扭转。

应用场景：

因为抉择排序的工夫复杂度较高，对于大规模数据的排序效率较低，因而在理论利用中并不罕用。更适宜在小规模或局部有序的数组中应用。抉择排序的长处是实现简略、思路清晰，且对于输出数据的初始程序不敏感。然而，对于大规模的数据集，抉择排序的效率较低，因为其工夫复杂度较高。在理论利用中，更常应用疾速排序、归并排序等更高效的排序算法。

插入排序

插入排序（Insertion Sort）是一种简略直观的排序算法，它的原理是将待排序的元素一一插入到已排序序列中的适合地位，直到整个序列有序。

实现原理：

1. 遍历待排序数组，将以后元素视为待插入元素。
2. 在已排序序列中，从后往前一一比拟元素，如果以后元素大于待插入元素，则将该元素后移一位。
3. 反复上述步骤，直到找到待插入元素的正确地位。
4. 将待插入元素插入到正确地位。

示例代码：

function insertionSort(arr) {
  const len = arr.length;

  for (let i = 1; i < len; i++) {const current = arr[i]; // 以后待插入的元素
    let j = i - 1; // 已排序序列的最初一个元素的索引

    // 将比 current 大的元素向后挪动，为 current 找到适合的插入地位
    while (j >= 0 && arr[j] > current) {arr[j + 1] = arr[j]; // 元素后移
      j--;
    }

    arr[j + 1] = current; // 将 current 插入到正确的地位
  }

  return arr;
}

// 示例用法
const array = [4, 2, 2, 8, 3, 3, 10, 5, 6, 2, 3];
const sortedArray = insertionSort(array);
console.log(sortedArray); // 输入: [2, 2, 2, 3, 3, 3, 4, 5, 6, 8, 10]

性能剖析：

• 工夫复杂度：插入排序的工夫复杂度为 O(n^2)，其中 n 是待排序数组的长度。在最坏状况下，须要进行 n 次比拟和挪动操作，因而工夫复杂度是二次的。
• 空间复杂度：插入排序的空间复杂度为 O(1)，它只须要应用常数级别的额定空间进行元素的比拟和挪动。
• 稳定性：插入排序是一种稳固的排序算法，即雷同值的元素在排序过程中不会扭转绝对程序。

应用场景：

插入排序实用于小规模或局部有序的数组。当待排序数组根本有序时，插入排序的效率较高。它比冒泡排序和抉择排序的性能稍好，且实现简略，实用于对于数据量较小的排序工作。插入排序也能够用作其余高级排序算法的子过程，例如疾速排序的优化版本中的小数组排序。

疾速排序

疾速排序（Quick Sort）是一种高效的排序算法，它的原理是通过抉择一个基准元素，将数组宰割成较小和较大两个子数组，而后对子数组进行递归排序，直到整个数组有序。

实现原理：

1. 抉择一个基准元素（通常是数组中的两头元素）。
2. 将数组分成两个子数组，比基准元素小的放在右边，比基准元素大的放在左边。
3. 递归地对左右子数组进行疾速排序。
4. 合并左子数组、基准元素和右子数组，失去最终有序的数组。

示例代码：

一般实现

// 一般实现
function quickSort(arr) {if (arr.length <= 1) {return arr; // 基线条件：数组为空或只有一个元素，间接返回}

  const pivotIndex = Math.floor(arr.length / 2); // 抉择基准元素的索引
  const pivot = arr.splice(pivotIndex, 1)[0]; // 从数组中取出基准元素

  const left = [];
  const 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));
}

// 示例用法
const array = [4, 2, 2, 8, 3, 3, 10, 5, 6, 2, 3];
const sortedArray = quickSort(array);
console.log(sortedArray); // 输入: [2, 2, 2, 3, 3, 3, 4, 5, 6, 8, 10]

应用 ES6 简洁实现

// 应用 ES6 简洁实现
function quickSort (arr) {
    // 如果数组长度小于 2，则返回原数组
    if (arr && arr.length < 2) {return arr;}

    const [prev, ...rest] = arr; // 取数组的第一个元素作为比拟基准值
    return [...quickSort(rest.filter(value => value < prev)), // 筛选出比 prev 的值小的值放在 prev 的右边，而后再进行递归操作
        prev,
        ...quickSort(rest.filter(value => value >= prev)), // 筛选出比 prev 的值大的放在 prev 的左边，而后再进行递归操作
    ]
}

// 示例用法
const array = [4, 2, 2, 8, 3, 3, 10, 5, 6, 2, 3];
const sortedArray = quickSort(array);
console.log(sortedArray); // 输入: [2, 2, 2, 3, 3, 3, 4, 5, 6, 8, 10]

性能剖析：

• 工夫复杂度：疾速排序的均匀工夫复杂度为 O(nlogn)，其中 n 是待排序数组的长度。在最坏状况下，工夫复杂度为 O(n^2)，但疾速排序的均匀工夫复杂度较低，因而它通常被认为是一种高效的排序算法。
• 空间复杂度：疾速排序的空间复杂度为 O(logn)，它通过递归调用和宰割子数组的形式应用了额定的空间。空间复杂度次要取决于递归调用的深度。
• 稳定性：疾速排序是一种不稳固的排序算法，即雷同值的元素在排序过程中可能会扭转绝对程序。

应用场景：

疾速排序实用于大规模数据的排序，它在理论利用中被宽泛应用。疾速排序的劣势在于排序速度快，尤其在大规模乱序数据的排序效率较高。它也是许多编程语言和库中的默认排序算法，如 JavaScript 中的 Array.prototype.sort() 办法就应用了疾速排序算法。

归并排序

归并排序（Merge Sort）是一种高效的排序算法，它的原理是将待排序的数组递归地分成两个子数组，别离对子数组进行排序，而后将两个排序好的子数组合并成一个有序的数组。

实现原理：

1. 将待排序数组宰割成较小的子数组，直到每个子数组只蕴含一个元素（递归基线条件）。
2. 递归地将子数组排序，直到失去排好序的子数组。
3. 合并排好序的子数组，失去最终有序的数组。

示例代码：

function mergeSort(arr) {if (arr.length <= 1) {return arr; // 基线条件：数组为空或只有一个元素，间接返回}

  const mid = Math.floor(arr.length / 2); // 找到数组的两头地位
  const left = arr.slice(0, mid); // 宰割为左子数组
  const right = arr.slice(mid); // 宰割为右子数组

  return merge(mergeSort(left), mergeSort(right)); // 递归地对左右子数组进行归并排序并合并
}

// 合并两个有序数组
function merge(left, right) {const merged = [];
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < left.length && rightIndex < right.length) {if (left[leftIndex] < right[rightIndex]) {merged.push(left[leftIndex]); // 左子数组元素较小，放入合并数组
      leftIndex++;
    } else {merged.push(right[rightIndex]); // 右子数组元素较小，放入合并数组
      rightIndex++;
    }
  }

  // 将残余的元素放入合并数组
  return merged.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

// 示例用法
const array = [4, 2, 2, 8, 3, 3, 10, 5, 6, 2, 3];
const sortedArray = mergeSort(array);
console.log(sortedArray); // 输入: [2, 2, 2, 3, 3, 3, 4, 5, 6, 8, 10]

性能剖析：

• 工夫复杂度：归并排序的工夫复杂度为 O(nlogn)，其中 n 是待排序数组的长度。归并排序是一种分治算法，通过将数组分成较小的子数组并对它们进行排序，而后再将排好序的子数组进行合并，从而实现整体的排序。
• 空间复杂度：归并排序的空间复杂度为 O(n)，它须要额定的空间来存储长期数组以及递归调用时的堆栈空间。
• 稳定性：归并排序是一种稳固的排序算法，雷同值的元素在排序过程中不会扭转绝对程序。

应用场景：

归并排序实用于大规模数据的排序，特地实用于内部排序，即排序数据量大到无奈全副加载到内存中的场景。归并排序的劣势在于排序速度较快且稳固，对于解决大规模乱序数据或须要放弃雷同元素绝对程序的排序工作十分无效。

堆排序

堆排序（Heap Sort）是一种高效的排序算法，它利用堆这种数据结构进行排序。堆是一种非凡的齐全二叉树，它满足堆的性质：对于每个节点，其值大于（或小于）其子节点的值。

实现原理：

1. 构建最大堆：从最初一个非叶子节点开始，顺次将数组转换为最大堆，保障每个节点的值大于或等于其子节点的值。
2. 顺次取出堆顶元素：将堆顶元素与最初一个元素替换，而后调整堆，将残余元素从新构建为最大堆。
3. 反复上述步骤，直到堆中的所有元素都被取出并排好序。

示例代码：

function heapSort(arr) {
  const len = arr.length;

  // 构建最大堆
  for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {heapify(arr, len, i);
  }

  // 顺次取出堆顶元素并调整堆
  for (let i = len - 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; // 以后节点索引
  const left = 2 * i + 1; // 左子节点索引
  const 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);
  }
}

// 示例用法
const array = [4, 2, 2, 8, 3, 3, 10, 5, 6, 2, 3];
const sortedArray = heapSort(array);
console.log(sortedArray); // 输入: [2, 2, 2, 3, 3, 3, 4, 5, 6, 8, 10]

性能剖析：

• 工夫复杂度：堆排序的工夫复杂度为 O(nlogn)，其中 n 是待排序数组的长度。堆排序的构建最大堆操作和调整堆操作的工夫复杂度均为 O(logn)，须要执行 n 次，因而总体工夫复杂度为 O(nlogn)。
• 空间复杂度：堆排序的空间复杂度为 O(1)，它只须要应用常数级别的额定空间来进行元素替换，没有应用额定的数据结构。
• 稳定性：堆排序是一种不稳固的排序算法，即雷同值的元素在排序过程中可能会扭转绝对程序。

应用场景：

堆排序实用于大规模数据的排序，尤其实用于须要找出最大或最小的 K 个元素的问题。因为堆排序的构建最大堆操作具备线性工夫复杂度，因而能够在一些特定场景中提供较好的性能，如优先队列的实现、Top K 问题等。

希尔排序

希尔排序（Shell Sort），也称作放大增量排序，是插入排序的一种改良版本。它通过将待排序数组分成多个子数组，并对每个子数组进行插入排序，逐渐减小子数组的大小，最终实现整个数组的排序。

实现原理：

1. 抉择一个初始增量（通常为数组长度的一半）。
2. 将数组分成多个子数组，每个子数组相隔增量个地位。
3. 对每个子数组进行插入排序，将子数组中的元素插入到正确的地位。
4. 逐渐减小增量，反复上述步骤，直到增量为 1，实现整个数组的排序。

示例代码：

function shellSort(arr) {
  const len = arr.length;
  let gap = Math.floor(len / 2); // 初始增量

  while (gap > 0) {
    // 对每个子数组进行插入排序
    for (let i = gap; i < len; i++) {const temp = arr[i];
      let j = i;

      // 在子数组中进行插入排序
      while (j >= gap && arr[j - gap] > temp) {arr[j] = arr[j - gap];
        j -= gap;
      }

      arr[j] = temp;
    }

    gap = Math.floor(gap / 2); // 减小增量
  }

  return arr;
}

// 示例用法
const array = [4, 2, 2, 8, 3, 3, 10, 5, 6, 2, 3];
const sortedArray = shellSort(array);
console.log(sortedArray); // 输入: [2, 2, 2, 3, 3, 3, 4, 5, 6, 8, 10]

性能剖析：

• 希尔排序的工夫复杂度依赖于增量序列的抉择，均匀工夫复杂度为 O(nlogn)。最坏状况下的工夫复杂度与插入排序雷同，为 O(n^2)。
• 空间复杂度：希尔排序的空间复杂度为 O(1)，它在原地进行排序，不须要额定的空间。
• 稳定性：希尔排序是一种不稳固的排序算法，即雷同值的元素在排序过程中可能会扭转绝对程序。
• 希尔排序的性能与增量序列的抉择无关，不同的增量序列可能导致不同的性能体现。

应用场景：

希尔排序实用于中等大小的数组排序，特地实用于须要在性能和简略实现之间获得均衡的场景。它在理论利用中常用于对大型数据集进行初步排序的预处理步骤，为后续排序算法提供更好的初始状态。希尔排序绝对于其余简略的高级排序算法具备更好的性能，但依然不如疾速排序、归并排序等高级排序算法。

计数排序

计数排序（Counting Sort）是一种线性工夫复杂度的排序算法，它通过统计数组中每个元素的呈现次数，而后依据统计信息将元素排序。

实现原理：

1. 首先找出数组中的最小值（min）和最大值（max）。
2. 创立一个计数数组（countArr），长度为 max min + 1，并初始化为 0。
3. 遍历待排序数组，统计每个元素呈现的次数，并将统计后果存储在计数数组中。
4. 依据计数数组的统计后果，重构排序后的数组。

示例代码：

function countingSort(arr) {
  const len = arr.length;

  // 找出数组中的最大值和最小值
  let min = arr[0];
  let max = arr[0];
  for (let i = 1; i < len; i++) {if (arr[i] < min) {min = arr[i];
    } else if (arr[i] > max) {max = arr[i];
    }
  }

  // 创立计数数组并统计元素呈现次数
  const countArr = new Array(max - min + 1).fill(0);
  for (let i = 0; i < len; i++) {countArr[arr[i] - min]++;
  }

  // 依据计数数组重构排序后的数组
  let outputIndex = 0;
  for (let i = 0; i < countArr.length; i++) {while (countArr[i] > 0) {arr[outputIndex] = i + min;
      outputIndex++;
      countArr[i]--;
    }
  }

  return arr;
}

// 示例用法
const array = [4, 2, 2, 8, 3, 3, 10, 5, 6, 2, 3];
const sortedArray = countingSort(array);
console.log(sortedArray); // 输入: [2, 2, 2, 3, 3, 3, 4, 5, 6, 8, 10]

性能剖析：

• 工夫复杂度：计数排序的工夫复杂度为 O(n+k)，其中 n 是待排序数组的长度，k 是计数范畴。计数排序的工夫复杂度较低，但要求待排序的元素必须是整数且范畴不宜过大。
• 空间复杂度：计数排序的空间复杂度为 O(k)，其中 k 是计数范畴。计数排序须要额定的计数数组来存储每个元素呈现的次数。
• 稳定性：计数排序是一种稳固的排序算法，即雷同值的元素在排序过程中不会扭转绝对程序。

应用场景：

计数排序实用于排序范畴较小的整数数组，且待排序数组的元素取值较集中的状况。计数排序的劣势在于排序速度快且稳固，特地实用于解决大量反复元素的排序工作，例如对年龄、问题、身高等离散数据进行排序。

桶排序

桶排序（Bucket Sort）是一种通过将待排序元素调配到不同的桶（容器）中，对每个桶中的元素进行排序，最初将各个桶中的元素合并失去有序后果的排序算法。

实现原理：

1. 找出待排序数组的最小值和最大值，确定桶的范畴。
2. 依据桶的大小，计算须要的桶的数量，并创立对应数量的桶。
3. 将待排序数组中的元素依据取值范畴调配到不同的桶中。
4. 对每个桶中的元素进行排序，能够抉择不同的排序算法（如插入排序、疾速排序）或递归应用桶排序。
5. 将各个桶中的有序元素合并失去最终的有序后果。

示例代码：

function bucketSort(arr, bucketSize = 5) {
  const len = arr.length;

  // 找出数组的最大值和最小值
  let min = arr[0];
  let max = arr[0];
  for (let i = 1; i < len; i++) {if (arr[i] < min) {min = arr[i];
    }
    if (arr[i] > max) {max = arr[i];
    }
  }

  // 计算桶的数量
  const bucketCount = Math.floor((max - min) / bucketSize) + 1;
  const buckets = new Array(bucketCount);

  // 初始化桶
  for (let i = 0; i < bucketCount; i++) {buckets[i] = [];}

  // 将元素调配到不同的桶中
  for (let i = 0; i < len; i++) {const bucketIndex = Math.floor((arr[i] - min) / bucketSize);
    buckets[bucketIndex].push(arr[i]);
  }

  // 对每个桶中的元素进行排序
  const sortedArray = [];
  for (let i = 0; i < bucketCount; i++) {
    // 提醒：这里能够对每个桶中的元素进行插入排序或疾速排序等
    // if (buckets[i]) {//   insertionSort(buckets[i]); // 应用插入排序对每个桶中的元素进行排序
    //   sortedArray.push(...buckets[i]); // 将排序后的桶合并到有序序列中
    // }

    if (bucketSize === 1) {
      // 桶大小为 1 时，间接将桶中的元素退出有序数组
      sortedArray.push(...buckets[i]);
    } else {
      // 桶大小大于 1 时，递归应用桶排序并将后果合并到有序数组
      const bucket = bucketSort(buckets[i], bucketSize - 1);
      sortedArray.push(...bucket);
    }
  }

  return sortedArray;
}

// 示例用法
const array = [4, 2, 2, 8, 3, 3, 10, 5, 6, 2, 3];
const sortedArray = bucketSort(array);
console.log(sortedArray); // 输入: [2, 2, 2, 3, 3, 3, 4, 5, 6, 8, 10]

性能剖析：

• 工夫复杂度：桶排序的工夫复杂度取决于桶的数量和桶中元素的排序算法。在现实状况下，桶的数量越大，桶内元素越均匀分布，桶排序的工夫复杂度越靠近 O(n)。但在最坏状况下，桶内元素都被调配到一个桶中，工夫复杂度进化为 O(n^2)。因而，抉择适合的桶大小和排序算法对性能很重要。
• 空间复杂度：桶排序的空间复杂度为 O(n+k)，其中 n 是待排序数组的长度，k 是桶的数量。须要额定的空间来存储桶和合并有序后果。
• 稳定性：桶排序能够是稳固的，但要求在桶内进行排序时应用稳固的排序算法。

应用场景：

桶排序实用于待排序数组散布较平均、取值范畴较小的状况。它对于大量数据的排序成果较好，并且实用于内部排序（须要将数据存储在磁盘或其余内部存储介质上进行排序）的场景。桶排序罕用于对年龄、问题、价格等离散数据进行排序，特地是当数据分布较为间断时，桶排序的性能劣势更加显著。

基数排序

基数排序（Radix Sort）是一种非比拟排序算法，它依据元素的每个位上的值进行排序。基数排序能够依照个位、十位、百位等位数顺次进行排序，直到最高位，从而失去有序序列。

实现原理：

1. 找出数组中的最大值，确定排序的轮数。最大值的位数决定了须要进行多少轮排序。
2. 从最低位开始，依照个位、十位、百位等位数顺次进行排序。
3. 创立 10 个桶，别离示意 0 -9。将待排序数组中的元素依据以后位上的值调配到对应的桶中。
4. 依照桶的程序将元素顺次合并为一个数组。
5. 反复上述过程，直到实现所有位的排序，失去有序序列。

示例代码：

function radixSort(arr) {const max = Math.max(...arr); // 找出数组中的最大值
  const maxDigitCount = countDigits(max); // 计算最大值的位数

  // 依照位数顺次进行排序
  for (let i = 0; i < maxDigitCount; i++) {const buckets = Array.from({ length: 10}, () => []); // 创立 10 个桶，别离示意 0 -9

    // 将元素调配到对应的桶中
    for (let j = 0; j < arr.length; j++) {const digit = getDigit(arr[j], i); // 获取以后位上的数字
      buckets[digit].push(arr[j]);
    }

    // 将桶中的元素按程序合并为一个数组
    arr = [].concat(...buckets);
  }

  return arr;
}

// 计算数字的位数
function countDigits(num) {if (num === 0) return 1;
  return Math.floor(Math.log10(num)) + 1;
}

// 获取数字指定位上的值
function getDigit(num, place) {return Math.floor(Math.abs(num) / Math.pow(10, place)) % 10;
}

// 示例用法
const array = [4, 2, 2, 8, 3, 3, 10, 5, 6, 2, 3];
const sortedArray = radixSort(array);
console.log(sortedArray); // 输入: [2, 2, 2, 3, 3, 3, 4, 5, 6, 8, 10]

性能剖析：

• 工夫复杂度：基数排序的工夫复杂度为 O(d*(n+k))，其中 n 是待排序数组的长度，d 是最大值的位数，k 是基数（例如十进制中的 10）。
• 空间复杂度：基数排序的空间复杂度为 O(n+k)，其中 n 是待排序数组的长度，k 是基数。
• 稳定性：基数排序是一种稳固的排序算法，雷同值的元素在排序过程中不会扭转绝对程序。

应用场景：

基数排序实用于待排序元素是非负整数的状况。
它对于位数较小的整数排序成果较好，尤其在位数相差不大的状况下。基数排序在理论利用中常用于整数排序、字符串排序和日期排序等场景。

总结

常见的十大排序算法的均匀、最好和最差状况下的工夫复杂度、空间复杂度和稳定性，汇总如下：

其中，n 示意数组的长度，k 示意待排序元素的取值范畴大小。

须要留神的是，表中的工夫复杂度和空间复杂度仅代表了排序算法的大抵性能，具体的实现形式和优化办法可能会对理论性能产生影响。此外，稳定性指的是排序算法在排序过程中是否放弃雷同元素的绝对程序不变。

抉择适宜的排序算法取决于具体的利用场景和对性能要求的思考。例如，对于大规模数据的排序，疾速排序和归并排序通常是较好的抉择；对于须要稳固排序的状况，能够思考插入排序、归并排序或计数排序等。在理论利用中，也能够依据数据规模、元素散布特点等因素进行综合思考，抉择最合适的排序算法。

引申

咱们平时工作当中排序应用的最多的应该是数组的 sort 办法，那么 sort 办法具体的实现原理大家有理解过嘛？

sort办法具体用法参考 mdn 文档：https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Refer…

本文由 mdnice 多平台公布