堆排序 与 线性时间排序

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int n, a[MAXN];

// 对以 i 为根的子树做下沉，堆的有效规模为 sz（下标 1..sz）
void siftDown(int i, int sz) {
    while (true) {
        int l = i << 1, r = l | 1, mx = i;   // 左右孩子：2i、2i+1
        if (l <= sz && a[l] > a[mx]) mx = l;     // 找三者中最大
        if (r <= sz && a[r] > a[mx]) mx = r;
        if (mx == i) break;                   // 已满足大根堆性质，停止
        swap(a[i], a[mx]);
        i = mx;                                // 继续往下检查被换下去的那个位置
    }
}

void heapSort() {
    for (int i = n >> 1; i >= 1; i--) siftDown(i, n);  // ① 建堆 O(n)，从 n/2 倒着来
    for (int i = n; i > 1; i--) {              // ② 排序 n-1 轮
        swap(a[1], a[i]);                       // 堆顶（当前最大）换到末尾，归位
        siftDown(1, i - 1);                     // 堆规模减 1，新堆顶下沉
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    heapSort();
    for (int i = 1; i <= n; i++) cout << a[i] << " \n"[i == n];
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005, MAXV = 1005;
int n, a[MAXN], out[MAXN], cnt[MAXV];

void countingSort() {
    for (int i = 1; i <= n; i++) cnt[a[i]]++;        // ① 统计每个值出现次数
    for (int v = 1; v < MAXV; v++) cnt[v] += cnt[v - 1];  // ② 前缀和 → 值 v 的结束位置
    for (int i = n; i >= 1; i--) {                    // ③ ★ 从右往左，保证稳定
        out[cnt[a[i]]] = a[i];
        cnt[a[i]]--;
    }
    for (int i = 1; i <= n; i++) a[i] = out[i];
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    countingSort();
    for (int i = 1; i <= n; i++) cout << a[i] << " \n"[i == n];
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000005, MAXV = 100005;   // 1000 * 100 = 100000
int n, key[MAXN], out[MAXN], cnt[MAXV];
double x;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lf", &x);
        key[i] = (int)(x * 100 + 0.5);   // ★ 四舍五入映射成整数，避免浮点误差
    }
    for (int i = 1; i <= n; i++) cnt[key[i]]++;
    for (int v = 1; v < MAXV; v++) cnt[v] += cnt[v - 1];
    for (int i = n; i >= 1; i--) out[cnt[key[i]]--] = key[i];
    for (int i = 1; i <= n; i++)
        printf("%.2f%s", out[i] / 100.0, i == n ? "\n" : " ");
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
int n, a[MAXN], tmp[MAXN], cnt[10];

// 按「第 exp 位」做一次稳定的计数排序（exp = 1, 10, 100, ...）
void countByDigit(int exp) {
    for (int i = 0; i < 10; i++) cnt[i] = 0;        // 只有 10 个桶！
    for (int i = 1; i <= n; i++) cnt[(a[i] / exp) % 10]++;  // ① 统计当前位
    for (int d = 1; d < 10; d++) cnt[d] += cnt[d - 1];    // ② 前缀和 → 结束位置
    for (int i = n; i >= 1; i--) {                      // ③ ★ 从右往左，保证稳定
        int d = (a[i] / exp) % 10;
        tmp[cnt[d]--] = a[i];
    }
    for (int i = 1; i <= n; i++) a[i] = tmp[i];
}

void radixSort() {
    int mx = *max_element(a + 1, a + n + 1);          // 找最大值，确定位数 d
    for (int exp = 1; mx / exp > 0; exp *= 10) countByDigit(exp);  // 从低位到高位
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    radixSort();
    for (int i = 1; i <= n; i++) printf("%d%c", a[i], i == n ? '\n' : ' ');
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000005, MAXV = 1000005;
int n, a[MAXN], tmp[MAXN], cnt[MAXV];

/* ===== 模板一：堆排序（大根堆，升序）===== */
void siftDown(int i, int sz) {
    while (true) {
        int l = i << 1, r = l | 1, mx = i;
        if (l <= sz && a[l] > a[mx]) mx = l;
        if (r <= sz && a[r] > a[mx]) mx = r;
        if (mx == i) break;
        swap(a[i], a[mx]); i = mx;
    }
}
void heapSort() {
    for (int i = n >> 1; i >= 1; i--) siftDown(i, n);
    for (int i = n; i > 1; i--) { swap(a[1], a[i]); siftDown(1, i - 1); }
}

/* ===== 模板二：计数排序（稳定，值域 1..V）===== */
void countingSort(int V) {
    for (int i = 1; i <= n; i++) cnt[a[i]]++;
    for (int v = 1; v <= V; v++) cnt[v] += cnt[v - 1];
    for (int i = n; i >= 1; i--) tmp[cnt[a[i]]--] = a[i];
    for (int i = 1; i <= n; i++) a[i] = tmp[i];
}

/* ===== 模板三：基数排序（十进制 LSD，非负整数）===== */
void countByDigit(int exp) {
    for (int i = 0; i < 10; i++) cnt[i] = 0;
    for (int i = 1; i <= n; i++) cnt[(a[i] / exp) % 10]++;
    for (int d = 1; d < 10; d++) cnt[d] += cnt[d - 1];
    for (int i = n; i >= 1; i--) tmp[cnt[(a[i] / exp) % 10]--] = a[i];
    for (int i = 1; i <= n; i++) a[i] = tmp[i];
}
void radixSort() {
    int mx = *max_element(a + 1, a + n + 1);
    for (int exp = 1; mx / exp > 0; exp *= 10) countByDigit(exp);
}

/* 选用口诀：值域小 → 计数；位少 → 基数；均匀实数 → 桶；其它 → std::sort */