排序

时间复杂度 最好 平均 最坏

空间复杂度 指辅助空间复杂度

还差一点 … 明天更 看英语政治计网去了 (凋谢)

#include<iostream>

using namespace std;

const int N = 1e5 + 10;

int n, q[N];

// 思想：类比扑克整牌
// 时间复杂度 O(n) O(n^2) O(n^2)
// 空间复杂度 O(1)
// 稳定
void insert_sort() {
    // 从第二个元素开始
    for (int i = 1; i < n; i++) {
        // i是待插入元素下标
        int j = i, x = q[i];
        while (j && q[j - 1] > x) {
            q[j] = q[j - 1];
            j--;
        }
        q[j] = x;
    }
}

// 思想：冒泡嘛 ... 每次把当前序列的最大元素移到最后
// 时间复杂度 O(n) O(n^2) O(n^2)
// 空间复杂度 o(1)
// 稳定
void bubble_sort() {

    for (int i = 1; i < n; i++) {

        bool swapped = false;
        for (int j = 0; j < n - i; j++) {

            if (q[j] > q[j + 1]) {
                swap(q[j], q[j + 1]);
                swapped = true;
            }
        }
        // 某一趟未交换的话，说明已有序
        if (!swapped) break;
    }
}

// 思想 选一个最小的放到乱序序列的第一个位置
// 时间复杂度 O(n^2) O(n^2) O(n^2)
// 空间复杂度 O(1)
// 不稳定
void select_sort() {

    for (int i = 0; i < n - 1; i++) {

        int t = i; // 乱序序列第一个位置
        // 找到乱序序列中最小值的下标
        for (int j = i + 1; j < n; j++)
            if (q[j] < q[t])
                t = j;

        swap(q[i], q[t]);
    }
}

// 思想 分组，组内插入排序 (部分有序对插入排序友好)
// 时间复杂度 O(n^(3/2))
// 空间复杂度 O(1)
// 不稳定
void shell_sort() {
    // d是公差，即所谓的增量 d == 2时需特判
    for (int d = n / 3; d; d = d == 2 ? 1 : d/3 ) {
        // 这层循环遍历的是每个分组
        for (int start = 0; start < d; start ++) {
            // 分组内插入排序
            for (int i = start + d; i < n; i += d) {

                int j = i, x = q[i];
                while (j > start && q[j - d] > x) {
                    q[j] = q[j - d];
                    j -= d;   
                }

                q[j] = x;
            }
        }
    }
}

// 思想 1. 找个pivot(划分点) 2. 划分成两段 左<=pivot 右>=pivot
//      3. 递归排左右两段
// 时间复杂度 O(nlogn) O(nlogn) O(n^2)
// 空间复杂度 O(n^2)
// 不稳定
void quick_sort(int l, int r) {

    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j) {

        while (q[++i] < x);
        while (q[--j] > x);

        if (i < j) swap(q[i], q[j]);
    }

    quick_sort(l, j);
    quick_sort(j + 1, r);
}

// 思想 根据堆的定义，很显然啦，这里以大顶堆为例
// 时间复杂度 O(nlogn) O(nlogn) O(nlogn)
// 空间复杂度 O(logn)
// 不稳定
int sz; // 堆大小

// 向下调整：若根不是最大的，把它调下去
void down(int u) {

    int t = u;
    if (2 * u <= sz && q[t] < q[2 * u]) t = 2 * u;
    if (2 * u + 1 <= sz && q[t] < q[2 * u + 1]) t = 2 * u + 1;
    // 此时t为 u u左子树(若存在) u右子树(若存在)中最大值

    // 若根不是最大的，交换值并递归down(t)
    if (t != u) {
        swap(q[t], q[u]);
        down(t);
    }
}

void heap_sort() {

    sz = n;

    // 将数组初始化成堆
    // 堆是完全二叉树 ... 从 n / 2 下取整开始down就好啦
    for (int i = n / 2; i; i--) down(i);

    for (int i = 0; i < n - 1; i++) {
        // 删元素：体会这里偷天换日的骚操作
        swap(q[1], q[sz]);
        sz--;
        down(1);
    }
}

int main() {

    cin >> n;
    for (int i = 1; i <= n; i++) scanf("%d", q + i);

    // insert_sort();
    // bubble_sort();
    // select_sort();
    // shell_sort();
    heap_sort();
    for (int i = 1; i <= n; i++) printf("%d ", q[i]);

}