基数排序

选一种语言就能看到代码

def radix_sort(a):
    if not a:
        return
    exp = 1
    top = max(a)
    while top // exp > 0:
        count = [0] * 10
        for value in a:
            count[value // exp % 10] += 1
        for digit in range(1, 10):
            count[digit] += count[digit - 1]
        out = [0] * len(a)
        for value in reversed(a):
            digit = value // exp % 10
            count[digit] -= 1
            out[count[digit]] = value
        a[:] = out
        exp *= 10

function radixSort(a) {
  if (a.length === 0) return;
  const top = Math.max(...a);
  for (let exp = 1; Math.floor(top / exp) > 0; exp *= 10) {
    const count = new Array(10).fill(0);
    for (const value of a) count[Math.floor(value / exp) % 10]++;
    for (let digit = 1; digit < 10; digit++) count[digit] += count[digit - 1];
    const out = new Array(a.length);
    for (let i = a.length - 1; i >= 0; i--) {
      const digit = Math.floor(a[i] / exp) % 10;
      out[--count[digit]] = a[i];
    }
    for (let i = 0; i < a.length; i++) a[i] = out[i];
  }
}

void radix_sort(int a[], int n, int top, int out[]) {
    for (int exp = 1; top / exp > 0; exp *= 10) {
        int count[10] = {0};
        for (int i = 0; i < n; i++) count[a[i] / exp % 10]++;
        for (int digit = 1; digit < 10; digit++) {
            count[digit] += count[digit - 1];
        }
        for (int i = n - 1; i >= 0; i--) {
            int digit = a[i] / exp % 10;
            out[--count[digit]] = a[i];
        }
        for (int i = 0; i < n; i++) a[i] = out[i];
    }
}

void radix_sort(std::vector<int>& a) {
    if (a.empty()) return;
    int top = *std::max_element(a.begin(), a.end());
    std::vector<int> out(a.size());
    for (int exp = 1; top / exp > 0; exp *= 10) {
        std::array<int, 10> count{};
        for (int value : a) count[value / exp % 10]++;
        for (int digit = 1; digit < 10; digit++) {
            count[digit] += count[digit - 1];
        }
        for (int i = static_cast<int>(a.size()) - 1; i >= 0; i--) {
            int digit = a[i] / exp % 10;
            out[--count[digit]] = a[i];
        }
        a = out;
    }
}

static void RadixSort(int[] a) {
    if (a.Length == 0) return;
    int top = a.Max();
    int[] out_ = new int[a.Length];
    for (int exp = 1; top / exp > 0; exp *= 10) {
        int[] count = new int[10];
        foreach (int value in a) count[value / exp % 10]++;
        for (int digit = 1; digit < 10; digit++) {
            count[digit] += count[digit - 1];
        }
        for (int i = a.Length - 1; i >= 0; i--) {
            int digit = a[i] / exp % 10;
            out_[--count[digit]] = a[i];
        }
        Array.Copy(out_, a, a.Length);
    }
}

static void radixSort(int[] a) {
    if (a.length == 0) return;
    int top = Arrays.stream(a).max().getAsInt();
    int[] out = new int[a.length];
    for (int exp = 1; top / exp > 0; exp *= 10) {
        int[] count = new int[10];
        for (int value : a) count[value / exp % 10]++;
        for (int digit = 1; digit < 10; digit++) {
            count[digit] += count[digit - 1];
        }
        for (int i = a.length - 1; i >= 0; i--) {
            int digit = a[i] / exp % 10;
            out[--count[digit]] = a[i];
        }
        System.arraycopy(out, 0, a, 0, a.length);
    }
}