插入排序 与 计数排序

#include <iostream>
using namespace std;
int main() {
    int n; cin >> n;
    int a[1005];
    for(int i=0;i<n;i++) cin >> a[i];
    for(int i=1;i<n;i++){
        int key=a[i], j=i-1;
        while(j>=0 && a[j]>key){
            a[j+1]=a[j]; j--;
        }
        a[j+1]=key;
    }
    for(int i=0;i<n;i++) cout<<a[i]<< " ";
    return 0;
}

#include <iostream>
using namespace std;
int main() {
    int n; cin >> n;
    int count[101] = {};
    for(int i=0;i<n;i++){
        int x; cin >> x;
        count[x]++;
    }
    // 统计分数段
    int fail=0, pass=0, excellent=0;
    for(int v=0;v<=59;v++) fail+=count[v];
    for(int v=60;v<=79;v++) pass+=count[v];
    for(int v=80;v<=100;v++) excellent+=count[v];
    cout << "不及格: " << fail << endl;
    cout << "及格: " << pass << endl;
    cout << "优秀: " << excellent << endl;
    // 输出排序结果
    for(int v=0;v<=100;v++)
        while(count[v]-- > 0) cout << v << " ";
    return 0;
}

#include <iostream>
#include <algorithm>
#include <chrono>
using namespace std;
void binaryInsertionSort(int a[], int n) {
    for(int i=1;i<n;i++){
        int key=a[i];
        int lo=0, hi=i;
        while(lo<hi){
            int mid=(lo+hi)/2;
            if(a[mid]<=key) lo=mid+1;
            else hi=mid;
        }
        for(int j=i;j>lo;j--) a[j]=a[j-1];
        a[lo]=key;
    }
}
int main() {
    int n=10000;
    int a[10005];
    for(int i=0;i<n;i++) a[i]=rand()%10000;
    auto t1=chrono::high_resolution_clock::now();
    binaryInsertionSort(a,n);
    auto t2=chrono::high_resolution_clock::now();
    cout << chrono::duration_cast<chrono::milliseconds>(t2-t1).count() << " ms" << endl;
    return 0;
}

#include <iostream>
#include <cstring>
using namespace std;
struct Student {
    char name[20];
    int score;
};
void stableCountSort(Student a[], int n, int maxScore) {
    int count[101] = {};
    Student output[1005];
    for(int i=0;i<n;i++) count[a[i].score]++;
    for(int i=1;i<=maxScore;i++) count[i]+=count[i-1];
    for(int i=n-1;i>=0;i--){  // 从后往前！
        output[count[a[i].score]-1]=a[i];
        count[a[i].score]--;
    }
    for(int i=0;i<n;i++) a[i]=output[i];
}
int main() {
    Student a[]={
        {"Alice",85},{"Bob",92},{"Carol",85},
        {"Dave",78},{"Eve",92}
    };
    stableCountSort(a, 5, 100);
    for(int i=0;i<5;i++)
        cout << a[i].name << " " << a[i].score << endl;
    return 0;
}

#include <iostream>
using namespace std;

void shellSort(int a[], int n) {
    // 计算初始间距（Knuth序列: 1, 4, 13, 40, 121, ...）
    int gap = 1;
    while (gap < n / 3) gap = gap * 3 + 1;

while (gap >= 1) {
        // 对每个间距执行插入排序
        for (int i = gap; i < n; i++) {
            int key = a[i];
            int j = i - gap;
            while (j >= 0 && a[j] > key) {
                a[j + gap] = a[j];
                j -= gap;
            }
            a[j + gap] = key;
        }
        gap /= 3;  // 缩小间距
    }
}

int main() {
    int n = 100000;
    int a[100005];
    for (int i = 0; i < n; i++) a[i] = rand() % 100000;
    shellSort(a, n);
    // 验证有序
    bool ok = true;
    for (int i = 1; i < n; i++)
        if (a[i] < a[i-1]) { ok = false; break; }
    cout << (ok ? "排序正确" : "排序错误") << endl;
    return 0;
}

#include <iostream>
using namespace std;

void radixSort(int a[], int n) {
    // 找最大值确定最大位数
    int maxVal = a[0];
    for (int i = 1; i < n; i++)
        if (a[i] > maxVal) maxVal = a[i];

int output[100005];

// 从个位到最高位，逐位计数排序
    for (long long exp = 1; maxVal / exp > 0; exp *= 10) {
        int count[10] = {};  // 0~9 十个数字

// 统计当前位的频数
        for (int i = 0; i < n; i++)
            count[(a[i] / exp) % 10]++;

// 前缀和
        for (int i = 1; i < 10; i++)
            count[i] += count[i - 1];

// 从后往前放置（保证稳定）
        for (int i = n - 1; i >= 0; i--) {
            int digit = (a[i] / exp) % 10;
            output[count[digit] - 1] = a[i];
            count[digit]--;
        }

// 复制回原数组
        for (int i = 0; i < n; i++)
            a[i] = output[i];
    }
}

int main() {
    int a[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = 8;
    radixSort(a, n);
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
    return 0;
}