基数排序（Radix Sort）‌

基数排序（Radix Sort）‌

基数排序（Radix Sort）是一种非比较型整数排序算法，它基于将整数按位数切割成不同的数字，然后按每个位数分别进行排序的思想。基数排序有两种主要的方法：最高位优先法（MSD, Most Significant Digit first）和最低位优先法（LSD, Least Significant Digit first）。

Vue 组件实现

示例

3

5

7

8

4

1

6

9

2

点我排序

<script setup lang="ts">
  import {reactive} from "vue";

  const RadixSortList = reactive({
    RadixSortList: [3, 5, 7, 8, 4, 1, 6, 9, 0] // 初始数组
  });

  const RadixSortClick = () => {
    RadixSort(RadixSortList.RadixSortList); // 点击触发排序
  };

  // 辅助函数...
  function getMax(arr) {
    let max = arr[0]; // 初始化为数组的第一个值
    for (let i = 1; i < arr.length; i++) {
      if (arr[i] > max) {
        max = arr[i]; // 更新最大值
      }
    }
    return max; // 返回最大值
  }

  function countingSort(arr, exp) {
    let n = arr.length; // 数组长度
    let output = new Array(n); // 临时数组，用于存放排序后的结果
    let count = new Array(10).fill(0); // 计数数组，用于统计每一位数字的出现次数（0-9）

    // 1. 统计该位（个位、十位等）上数字出现的次数
    for (let i = 0; i < n; i++) {
      let index = Math.floor(arr[i] / exp) % 10; // 取第 exp 位的数字
      count[index]++; // 对应计数器加一
    }

    // 2. 修改计数数组，使其表示最终输出位置
    for (let i = 1; i < 10; i++) {
      count[i] += count[i - 1];
    }

    // 3. 按当前计数数组排序，将元素放到输出数组
    for (let i = n - 1; i >= 0; i--) { // 逆序遍历，保证排序稳定性
      let index = Math.floor(arr[i] / exp) % 10; // 计算该位数字
      output[count[index] - 1] = arr[i]; // 将数字放入正确位置
      count[index]--; // 减少计数器值
    }

    // 4. 将排序结果复制到原数组
    for (let i = 0; i < n; i++) {
      arr[i] = output[i];
    }
  }

  function countingSort(arr, exp) {
    let n = arr.length; // 数组长度
    let output = new Array(n); // 临时数组，用于存放排序后的结果
    let count = new Array(10).fill(0); // 计数数组，用于统计每一位数字的出现次数（0-9）

    // 1. 统计该位（个位、十位等）上数字出现的次数
    for (let i = 0; i < n; i++) {
      let index = Math.floor(arr[i] / exp) % 10; // 取第 exp 位的数字
      count[index]++; // 对应计数器加一
    }

    // 2. 修改计数数组，使其表示最终输出位置
    for (let i = 1; i < 10; i++) {
      count[i] += count[i - 1];
    }

    // 3. 按当前计数数组排序，将元素放到输出数组
    for (let i = n - 1; i >= 0; i--) { // 逆序遍历，保证排序稳定性
      let index = Math.floor(arr[i] / exp) % 10; // 计算该位数字
      output[count[index] - 1] = arr[i]; // 将数字放入正确位置
      count[index]--; // 减少计数器值
    }

    // 4. 将排序结果复制到原数组
    for (let i = 0; i < n; i++) {
      arr[i] = output[i];
    }
  }

  function RadixSort(arr) {
    let max = getMax(arr); // 找到数组中最大值

    // 按每个位（从最低位到最高位）循环执行计数排序
    for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
      countingSort(arr, exp);
    }
  }
</script>

<template>
  <p>{{ JSON.stringify(RadixSortList.RadixSortList) }}</p> <!-- 展示数组 -->
  <h4 @click="RadixSortClick">点我排序</h4> <!-- 点击排序 -->
</template>

<style scoped lang="scss">
  /* 样式可根据需求调整 */
</style>

---

基础概念：

• 基数排序是一种非比较型排序算法，靠将整数按位数切割成不同的数字（个位、十位等），从低位到高位依次排序，即最低位优先（LSD）。也可以从高位到低位排序（MSD）。
• 该算法的核心在于按每一位的数字进行多次排序，通常使用计数排序作为子算法。

---

代码详解

getMax 函数：获取数组中的最大值

function getMax(arr) {
  let max = arr[0]; // 初始化为数组的第一个值
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i]; // 更新最大值
    }
  }
  return max; // 返回最大值
}

详解：

• 获取输入数组中的最大值，用于确定是否需要进一步进行按位排序。
• 基数排序会根据最大值的位数循环多次，逐位排序（从个位、十位到更高位）。

注意事项：

• 确保数组非空，否则会出现错误。

---

countingSort 函数：按某个位数进行计数排序

function countingSort(arr, exp) {
    let n = arr.length; // 数组长度
    let output = new Array(n); // 临时数组，用于存放排序后的结果
    let count = new Array(10).fill(0); // 计数数组，用于统计每一位数字的出现次数（0-9）

    // 1. 统计该位（个位、十位等）上数字出现的次数
    for (let i = 0; i < n; i++) {
        let index = Math.floor(arr[i] / exp) % 10; // 取第 exp 位的数字
        count[index]++; // 对应计数器加一
  }

    // 2. 修改计数数组，使其表示最终输出位置
    for (let i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    // 3. 按当前计数数组排序，将元素放到输出数组
    for (let i = n - 1; i >= 0; i--) { // 逆序遍历，保证排序稳定性
        let index = Math.floor(arr[i] / exp) % 10; // 计算该位数字
        output[count[index] - 1] = arr[i]; // 将数字放入正确位置
        count[index]--; // 减少计数器值
    }

    // 4. 将排序结果复制到原数组
    for (let i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

详解：

• 对数组的某个位数（个位、十位、百位……）进行计数排序，保持排序结果稳定。
• 稳定性意味着：如果两个值的当前位相同，排序后它们的相对顺序保持不变。

注意事项：

• 使用 Math.floor(arr[i] / exp) % 10 提取当前位上的数字，确保其为 0-9 的整数。
• 每次调用 countingSort 时，exp 参数应为 1, 10, 100...（代表个位、十位等）。

---

RadixSort 函数：主排序逻辑

function RadixSort(arr) {
    let max = getMax(arr); // 找到数组中最大值

    // 按每个位（从最低位到最高位）循环执行计数排序
    for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
        countingSort(arr, exp);
    }
}

详解：

• 首先得到最大值 max，以便知道需要排序多少位。
• 使用 exp 来表示当前的位数（1：个位，10：十位，100：百位……）。
• 每轮循环调用 countingSort 对当前位进行排序。

注意事项：

• 确保数组中的元素是 非负整数。如果有负数或小数，需要对代码进行额外处理。
• 基数排序适合整数排序，且位数不宜过长（如超大整数需要特殊优化）。

注意事项总结：

1. 非负整数数组：基数排序传统上用来排序非负整数。如果数组中包含负数或小数，需要先对数据进行转换。
2. 空间复杂度：使用了额外的计数数组 count 和临时数组 output，适合空间充裕的场景。
3. 稳定性：基数排序是一种稳定排序算法，适合有稳定性要求的场景（如按不同键值多次排序）。
4. 不适用大范围小数：如果小数范围太大，转化成本高，基数排序效率可能变低。
5. 大数支持：若支持非常大的数字（超出 JS 最大安全整数），需额外处理位数。