八大排序算法

冒泡排序

// 一、冒泡排序 [P1177 【模板】排序——(TLE 2, 3, 4, 5)]  
// 最好时间复杂度 O(n) 平均时间复杂度 O(n^2) 最坏时间复杂度 O(n^2)
// 空间复杂度 O(1)
// 稳定  
template<typename T>  
void bubble_sort [[maybe_unused]](vector<T> &arr, const size_t &len) {  
    for (int i = 0; i < len; ++i)  
        for (int j = 1; j < len - i; ++j)  
            if (arr[j - 1] > arr[j])  
                swap(arr[j - 1], arr[j]);  
}

选择排序

// 二、选择排序 [P1177 【模板】排序——(TLE 2, 3, 4, 5)]  
// 最好时间复杂度 O(n^2) 平均时间复杂度 O(n^2) 最坏时间复杂度 O(n^2)
// 空间复杂度 O(1)
// 不稳定  
template<typename T>  
void selection_sort [[maybe_unused]](vector<T> &arr, const size_t &len) {  
    auto &&max_element_index = [&arr](const int &l, const int &r) {  
        int res = l;  
        for (int i = l; i <= r; ++i)  
            if (arr[i] > arr[res])  
                res = i;  
        return res;  
    };  
    for (int i = as<int>(len) - 1; i >= 0; --i)  
        swap(arr[max_element_index(0, i)], arr[i]);  
}

插入排序

// 三、插入排序 [P1177 【模板】排序——(AC)]  
// 最好时间复杂度 O(n) 平均时间复杂度 O(n^2) 最坏时间复杂度 O(n^2)
// 空间复杂度 O(1)
// 稳定  
template<typename T>  
void insertion_sort [[maybe_unused]](vector<T> &arr, const size_t &len) {  
    for (int i = 1; i < len; ++i) {  
        T key = arr[i]; // 接下来在已经排序的序列中二分查找插入位置，然后插入元素  
        auto key_iterator = upper_bound(arr.begin(), arr.begin() + i, key);  
        copy(key_iterator, arr.begin() + i, next(key_iterator));  
        *key_iterator = key;  
    }  
}

计数排序

普通实现

// 四、1.计数排序 [P1177 【模板】排序——(MLE 1, 2)]  
// 最好时间复杂度 O(n + m) 平均时间复杂度 O(n + m) 最坏时间复杂度 O(n + m)
// 空间复杂度 O(m)
// 稳定  
template<typename T>  
void counting_sort [[maybe_unused]](vector<T> &arr, const size_t &len) {  
    T maxn, minn;  
    maxn = minn = arr[0];  
    for (auto &&i: arr) {  
        maxn = max(maxn, i);  
        minn = min(minn, i);  
    }  
    vector<size_t> counting(maxn - minn + 1, 0);  
    for (auto &&i: arr)  
        counting[i - minn]++;  
    for (size_t idx = 0, i = 0; i < counting.size(); ++i)  
        for (; counting[i]; counting[i]--)  
            arr[idx++] = i + minn;  
}

红黑树空间优化实现

// 四、2.计数排序(map压缩空间) [P1177 【模板】排序——(AC)]  
template<typename T>  
void counting_sort_with_map [[maybe_unused]](vector<T> &arr, const size_t &len) {  
    map<int, size_t> counting;  
    for (auto &&i: arr)  
        counting[i]++;  
    size_t idx = 0;  
    for (auto &&node: counting)  
        for (; node.second; node.second--)  
            arr[idx++] = node.first;  
}

希尔排序

// 五、希尔排序 [P1177 【模板】排序——(AC)]  
// 最好时间复杂度 O(n) 平均时间复杂度 O(n^{1.3}) 最坏时间复杂度 O(n^2)
// 空间复杂度 O(1)
// 不稳定  
template<typename T>  
void shell_sort [[maybe_unused]](vector<T> &arr, const size_t &len) {  
    for (int gap = as<int>(len >> 1); gap >= 1; gap >>= 1)  
        for (int i = gap; i < len; i++)  
            for (int j = i - gap; j >= 0 and arr[j] > arr[j + gap]; j -= gap)  
                swap(arr[j], arr[j + gap]);  
}

快速排序

// 六、快速排序 [P1177 【模板】排序——(AC)]  
// 最好时间复杂度 O(n log_2{n}) 平均时间复杂度 O(n log_2{n}) 最坏时间复杂度 O(n^2)
// 空间复杂度 O(n log_2{n})
// 不稳定  
template<typename T>  
void quick_sort [[maybe_unused]](vector<T> &arr, const size_t &len) {  
    mt19937_64 gen(std::random_device{}()); // 采用随机基准可以减少极端数据的退化概率  
    auto &&randint = [&gen](const int minn, const int &maxn) {  
        uniform_int_distribution rand(minn, maxn);  
        return rand(gen);  
    };  
    function<void(const int &, const int &)> qsort = [&qsort, &arr, &randint](const int &l, const int &r) {  
        int i = l, j = r;  
        T mid = arr[randint(l, r)];  
        while (i < j) {  
            while (arr[j] > mid)  
                j--;  
            while (arr[i] < mid)  
                i++;  
            if (i <= j)  
                swap(arr[i++], arr[j--]);  
        }  
        if (l < j)  
            qsort(l, j);  
        if (i < r)  
            qsort(i, r);  
    };  
    qsort(0, as<int>(len) - 1);  
}

归并排序

// 七、归并排序 [P1177 【模板】排序——(AC)]  
// 最好时间复杂度 O(n log_2{n}) 平均时间复杂度 O(n log_2{n}) 最坏时间复杂度 O(n log_2{n})
// 空间复杂度 O(1)
// 不稳定  
template<typename T>  
void merge_sort [[maybe_unused]](vector<T> &arr, const size_t &len) {  
    function<void(const int &, const int &)> msort = [&arr, &msort](const int &l, const int &r) {  
        if (r - l <= 1)  
            return;  
        int mid = (l + r) >> 1;  
        msort(l, mid);  
        msort(mid, r);  
        vector<T> tmp(r - l);  
        // merge  
        int l1 = l, r1 = mid, l2 = mid, r2 = r, idx = 0;  
        while (l1 < r1 and l2 < r2) {  
            while (l1 < r1 and arr[l1] <= arr[l2])  
                tmp[idx++] = arr[l1++];  
            while (l2 < r2 and arr[l2] <= arr[l1])  
                tmp[idx++] = arr[l2++];  
        }  
        while (l1 < r1)  
            tmp[idx++] = arr[l1++];  
        while (l2 < r2)  
            tmp[idx++] = arr[l2++];  
        copy(tmp.begin(), tmp.end(), arr.begin() + l);  
    };  
    msort(0, as<int>(len));  
}

堆排序

// 八、堆排序 [P1177 【模板】排序——(AC)]  
// 最好时间复杂度 O(n log_2{n}) 平均时间复杂度 O(n log_2{n}) 最坏时间复杂度 O(n log_2{n})
// 空间复杂度 O(1)
// 不稳定  
template<typename T>  
void heap_sort [[maybe_unused]](vector<T> &arr, const size_t &len) {  
    auto &&heapify = [&arr](const int &begin, const int &end) {  
        auto root = begin;  
        auto kid = root << 1 | 1; // l_kid  
        while (kid <= end) {  
            if (kid + 1 <= end and arr[kid] <= arr[kid + 1])// 先比较两个子结点大小，选择最大的  
                kid++;  
            if (arr[root] >= arr[kid]) // 如果父结点比子结点大，代表调整完毕，直接跳出函数  
                return;  
            else {  
                swap(arr[root], arr[kid]);  
                root = kid;  
                kid = root << 1 | 1;  
            }  
        }  
    };  
    for (int i = (as<int>(len) - 2) >> 1; i >= 0; --i)  
        heapify(i, len - 1);  
    for (int i = as<int>(len) - 1; i > 0; --i) {  
        swap(arr[0], arr[i]);  
        heapify(0, i - 1);  
    }  
}