闪电排序

选一种语言就能看到代码

def flash_sort(a):
    n = len(a)
    if n < 2:
        return
    lo, hi = min(a), max(a)
    if lo == hi:
        return
    m = max(2, n * 43 // 100)
    ends = [0] * m
    for value in a:
        ends[(m - 1) * (value - lo) // (hi - lo)] += 1
    for k in range(1, m):
        ends[k] += ends[k - 1]
    moved, j, k = 0, 0, m - 1
    while moved < n - 1:
        while j >= ends[k]:
            j += 1
            k = (m - 1) * (a[j] - lo) // (hi - lo)
        flash = a[j]
        while j != ends[k]:
            k = (m - 1) * (flash - lo) // (hi - lo)
            ends[k] -= 1
            a[ends[k]], flash = flash, a[ends[k]]
            moved += 1
    for i in range(1, n):
        key = a[i]
        t = i - 1
        while t >= 0 and a[t] > key:
            a[t + 1] = a[t]
            t -= 1
        a[t + 1] = key

function flashSort(a) {
  const n = a.length;
  if (n < 2) return;
  const lo = Math.min(...a);
  const hi = Math.max(...a);
  if (lo === hi) return;
  const m = Math.max(2, Math.floor((n * 43) / 100));
  const klass = (v) => Math.floor(((m - 1) * (v - lo)) / (hi - lo));
  const ends = new Array(m).fill(0);
  for (const value of a) ends[klass(value)]++;
  for (let k = 1; k < m; k++) ends[k] += ends[k - 1];
  let moved = 0;
  let j = 0;
  let k = m - 1;
  while (moved < n - 1) {
    while (j >= ends[k]) k = klass(a[++j]);
    let flash = a[j];
    while (j !== ends[k]) {
      k = klass(flash);
      const hold = a[--ends[k]];
      a[ends[k]] = flash;
      flash = hold;
      moved++;
    }
  }
  for (let i = 1; i < n; i++) {
    const key = a[i];
    let t = i - 1;
    while (t >= 0 && a[t] > key) {
      a[t + 1] = a[t];
      t--;
    }
    a[t + 1] = key;
  }
}

void flash_sort(int a[], int n) {
    if (n < 2) return;
    int lo = a[0], hi = a[0];
    for (int i = 1; i < n; i++) {
        if (a[i] < lo) lo = a[i];
        if (a[i] > hi) hi = a[i];
    }
    if (lo == hi) return;
    int m = n * 43 / 100;
    if (m < 2) m = 2;
    int* ends = calloc(m, sizeof(int));
    for (int i = 0; i < n; i++) ends[(long)(m - 1) * (a[i] - lo) / (hi - lo)]++;
    for (int k = 1; k < m; k++) ends[k] += ends[k - 1];
    int moved = 0, j = 0, k = m - 1;
    while (moved < n - 1) {
        while (j >= ends[k]) k = (long)(m - 1) * (a[++j] - lo) / (hi - lo);
        int flash = a[j];
        while (j != ends[k]) {
            k = (long)(m - 1) * (flash - lo) / (hi - lo);
            int hold = a[--ends[k]];
            a[ends[k]] = flash;
            flash = hold;
            moved++;
        }
    }
    free(ends);
    for (int i = 1; i < n; i++) {
        int key = a[i];
        int t = i - 1;
        while (t >= 0 && a[t] > key) {
            a[t + 1] = a[t];
            t--;
        }
        a[t + 1] = key;
    }
}

void flash_sort(std::vector<int>& a) {
    int n = static_cast<int>(a.size());
    if (n < 2) return;
    auto span = std::minmax_element(a.begin(), a.end());
    int lo = *span.first, hi = *span.second;
    if (lo == hi) return;
    int m = std::max(2, n * 43 / 100);
    auto klass = [&](int v) { return (m - 1) * (v - lo) / (hi - lo); };
    std::vector<int> ends(m, 0);
    for (int value : a) ends[klass(value)]++;
    for (int k = 1; k < m; k++) ends[k] += ends[k - 1];
    int moved = 0, j = 0, k = m - 1;
    while (moved < n - 1) {
        while (j >= ends[k]) k = klass(a[++j]);
        int flash = a[j];
        while (j != ends[k]) {
            k = klass(flash);
            std::swap(flash, a[--ends[k]]);
            moved++;
        }
    }
    for (int i = 1; i < n; i++) {
        int key = a[i];
        int t = i - 1;
        while (t >= 0 && a[t] > key) {
            a[t + 1] = a[t];
            t--;
        }
        a[t + 1] = key;
    }
}

static void FlashSort(int[] a) {
    int n = a.Length;
    if (n < 2) return;
    int lo = a.Min(), hi = a.Max();
    if (lo == hi) return;
    int m = Math.Max(2, n * 43 / 100);
    Func<int, int> klass = v => (m - 1) * (v - lo) / (hi - lo);
    int[] ends = new int[m];
    foreach (int value in a) ends[klass(value)]++;
    for (int k = 1; k < m; k++) ends[k] += ends[k - 1];
    int moved = 0, j = 0, at = m - 1;
    while (moved < n - 1) {
        while (j >= ends[at]) at = klass(a[++j]);
        int flash = a[j];
        while (j != ends[at]) {
            at = klass(flash);
            int hold = a[--ends[at]];
            a[ends[at]] = flash;
            flash = hold;
            moved++;
        }
    }
    for (int i = 1; i < n; i++) {
        int key = a[i];
        int t = i - 1;
        while (t >= 0 && a[t] > key) {
            a[t + 1] = a[t];
            t--;
        }
        a[t + 1] = key;
    }
}

static void flashSort(int[] a) {
    int n = a.length;
    if (n < 2) return;
    int lo = Arrays.stream(a).min().getAsInt();
    int hi = Arrays.stream(a).max().getAsInt();
    if (lo == hi) return;
    int m = Math.max(2, n * 43 / 100);
    int[] ends = new int[m];
    for (int value : a) ends[(m - 1) * (value - lo) / (hi - lo)]++;
    for (int k = 1; k < m; k++) ends[k] += ends[k - 1];
    int moved = 0, j = 0, k = m - 1;
    while (moved < n - 1) {
        while (j >= ends[k]) k = (m - 1) * (a[++j] - lo) / (hi - lo);
        int flash = a[j];
        while (j != ends[k]) {
            k = (m - 1) * (flash - lo) / (hi - lo);
            int hold = a[--ends[k]];
            a[ends[k]] = flash;
            flash = hold;
            moved++;
        }
    }
    for (int i = 1; i < n; i++) {
        int key = a[i];
        int t = i - 1;
        while (t >= 0 && a[t] > key) {
            a[t + 1] = a[t];
            t--;
        }
        a[t + 1] = key;
    }
}