[数据结构与算法]c++实现 排序

#include <list>
#include <iostream>
#include <vector>
#include <stdio.h>
#include <climits>
using namespace std;
#include <math.h>

//最好: nlogn
// 最坏 是 : n 2
// 解释: 每次选择的 轴节点,都是 极值
//         导致,递归的一遍只有一个,另一边 却又 n-1个
//          这样下去,就是一个 等差数列 
//          所以总共的最坏事件负责度 是 pow(n,2);
//空间复杂度: 每一次递归,都需要 选择一个轴节点 ,所以递归深度 logn
//            所以就是 logn
void quick_sort(vector<int> &vec, int left, int right)
{
    if (left >= right)
        return; //只剩下一个
    int mid = left + (right - left) / 2;
    int i = left - 1;
    int j = right + 1;
    int target = vec[mid];
    while (i < j)
    {
        do
            i++;
        while (vec[i] < target);
        do
            j--;
        while (vec[j] > target);
        if (i < j)
            swap(vec[i], vec[j]);
    }
    quick_sort(vec, left, j);
    quick_sort(vec, j + 1, right);
    return;
}
// 空间复杂度: o N 他需要一个临时数组
// 时间复杂度; n log n
// 最坏: nlogn
// 均衡教派

void mearge_sort(vector<int> &vec, vector<int> &temp, int left, int right)
{

    if (left >= right)
        return;
    int mid = left + (right - left) / 2;
    mearge_sort(vec, temp, left, mid);
    mearge_sort(vec, temp, mid + 1, right);

    int i = left;
    int j = mid + 1;
    int k = left;
    while (i <= mid && j <= right)
    {
        if (vec[i] < vec[j])
        {
            temp[k] = vec[i];
            k++;
            i++;
        }
        else
        {
            temp[k] = vec[j];
            k++;
            j++;
        }
    }
    while (i <= mid)
    {
        temp[k] = vec[i];
        k++;
        i++;
    }
    while (j <= right)
    {
        temp[k] = vec[j];
        k++;
        j++;
    }
    for (int i = left, j = left; i <= right; i++, j++)
    {
        vec[i] = temp[j];
    }
    return;
}
// 均衡教派:堆排序 
// 空间 : O 1, 他就不需要而外开空间
class Heap
{
private:
    int heap_size_;

public:
    vector<int> vec;

public:
    Heap(vector<int> &nums) : vec(nums.begin(), nums.end())
    {
        heap_size_ = vec.size();
    }
    ~Heap() = default;

    void sift_up(int index)
    {
        //上滤
        int rem = vec[index];

        while (index > 0)
        {
            int p_index = (index - 1) >> 1;
            int p_val = vec[p_index];
            if (p_val >= rem)
                break;
            vec[index] = p_val;
            index = p_index;
        }
        vec[index] = rem;
        return;
    }
    void siftdown(int index)
    {
        int rem = vec[index];
        int half = heap_size_ >> 1;
        while (index < half)
        {
            int child_index = 2 * index + 1;
            int child_val = vec[child_index];
            if (child_index + 1 < heap_size_)
            {
                //说明右叶子存在
                if (child_val < vec[child_index + 1])
                {
                    child_index = child_index + 1;
                    child_val = vec[child_index];
                }
            }
            if (child_val <= rem)
                break;
            vec[index] = child_val;
            index = child_index;
        }
        vec[index] = rem;
        return;
    }
    void makeheap1()
    {
        for (int i = 1; i < heap_size_; i++)
        {
            sift_up(i);
        }
    }
    void makeheap2()
    {
        for (int i = heap_size_ >> 1 - 1; i >= 0; i--)
        {
            siftdown(i);
        }
    }
    void sortheap()
    {
        while (heap_size_ > 0)
        {
            int rem = vec[0];
            swap(vec[0], vec[heap_size_ - 1]);
            heap_size_--;
            siftdown(0);
        }
    }
};
// 时间: 最好: 已经有序, last_swap记录end 所以就是 O 1
//       最坏 pow(n,2);
void bubblesort(vector<int> &vec)
{
    for (int end = vec.size() - 1; end > 0; end--)
    {
        int last_swap = 0;
        for (int start = 1; start <= end; start++)
        {
            if (vec[start] < vec[start - 1])
            {
                swap(vec[start], vec[start - 1]);
                last_swap = start;
            }
        }
        end = last_swap;
    }
    return;
}
//空间 : O 1
//时间 : 最坏:最坏 都是 n 2
void selectsort(vector<int> vec)
{
    int max_index = 0;
    for (int end = vec.size() - 1; end > 0; end--)
    {
        for (int start = 1; start <= end; start++)
        {
            if (vec[start] > vec[max_index])
            {
                max_index = start;
            }
        }
        swap(vec[max_index], vec[end]);
    }
    return;
}
//时间复杂度: 这个要看希尔步长
// 平均: N 最坏 pow(n,1.3) ~ pow(n,2);
//空间复杂度: 希尔步长 O 1
class Shellsort
{
public:
    vector<int> vec;
    Shellsort(vector<int> nums) : vec(nums.begin(), nums.end())
    {
    }
    ~Shellsort() = default;
    vector<int> GetShellStep(int vec_length)
    {
        vector<int> step;
        int k = 0;
        int step_len;
        while (true)
        {
            if (k % 2 == 0)
            {
                int pow1 = pow(2, k >> 1);
                step_len = 9 * (pow1 * pow1 - pow1) + 1;
            }
            else
            {
                int pow2 = pow(2,(k - 1) >> 1);
                int pow3 = pow(2,(k + 1) >> 1);
                step_len = 8*(pow2 *pow3) - 6 * pow3 + 1;
            }
            if (step_len >=vec_length) break;//注意这里
            step.insert(step.begin(),step_len);
            k++;
        }
        return step;
    }

    void sort()
    {
        vector<int> step = GetShellStep(this->vec.size());
        
        for (auto step_len : step) {
            for (int col = 0; col < step_len;col ++) {
                for (int down_col = col + step_len;down_col < vec.size();down_col +=step_len)
                {
                    int cur = down_col;
                    while (vec[cur -step_len] > vec[cur]){
                        swap(vec[cur-step_len],vec[cur]);
                        cur -=step_len;
                    }
                }
            }
        }
        return ;

    }
};
// 时间复杂度: O(n) + O(k)
// 空间同上 : k是整数的取值范围
void countingsort(vector<int> &vec)
{
    //计数排序
    int m_max =INT_MIN;
    int m_min =INT_MAX;
    //获取最大值 和最小值
    //利用最大值 - 最小值 得到 需要统计的元素的个数
    for (auto x : vec) {
        m_min =min(x,m_min);
        m_max =max(m_max,x);
    }
    int bucket_size = m_max -m_min + 1;
    vector<int> bucket(bucket_size,0);
    //现在在开始扫一遍 数
    // 数组 元素 vec[x] - m_min: 就是他的下标
    // 统计每一个元素出现的次数
    for(auto x :vec) {
        bucket[x - m_min] ++;
    }
    //现在 对 bucket数组求前缀和
    // 前缀和 表示 这个数字 最后一次出现 是地第几个位置
    for(int i = 1 ; i <bucket_size; i ++) {
        bucket[i] +=bucket[i-1];
    }
    //ok 现在都统计好了
    vector<int> res (vec.size(),0);
    // 现在要从后往前, 遍历这个vec
    // 然后在 bucket 里面 找 vec[i]出现的次数
    // 这个对应这1他 最后一次出现位置的下标
    for (int i = vec.size() - 1 ;i >= 0; i --) {
        int index = bucket[vec[i] - m_min] - 1;//代表这最后一次出现 ,是第几个,
        bucket[vec[i] - m_min] -= 1;
        res[index] = vec[i];
    }
    for (auto x : res) {
        cout << x << " ";
    }
    cout << endl;
    return ;
}
//基数排序 不能排负数
// 时间复杂度:(注意 : 10机制数字) 就是 d*n
// O(d ? (n + k)) ，d 是最大值的位数，k 是进制。属于稳定排序
void radissort(vector<int> & vec)
{
    //基数排序
    //从第位 到高位,每一次按照当前选择的位数来排序
    vector<list<int>*>bucket(10,nullptr);
    int m_max= INT_MIN;
    for (auto x : vec) {
        m_max =max(m_max,x);
    }
    //需要一个res, 因为每一次 基数排序完,都需要把他们规整到一个vect里面去

    vector<int> res (vec.begin(),vec.end());
    int k = 1;
    for (;k <= m_max; k =k*10) {
        //利用这个k来控制趟数
        for (auto x : res) {
           int index = x / k %10;
           if (bucket[index] == nullptr) 
              bucket[index] = new list<int>();
            bucket[index]->push_back(x);
        }
        //现在都加入完成饿了
        //需要从里面一个一个的取出来
        int insert_index = 0;
        for (auto y : bucket) {
            if (y == nullptr)continue;
            while (!y->empty()) {
                int rem = y->front();
                y->pop_front();
                res[insert_index] = rem;
                insert_index ++;
            }
        }
        // 现在bucket里面又全部拿出来了
        // 你只需要 观看下一位就可以啦
    }
    cout<< endl<<endl<<endl;
    for (auto x : res) 
        cout << x << " ";
    return ;
}
int main()
{
    vector<int> vec = {1, 2, 3, 4, 5, -1, -2, -3, -4, -5, -6, 11, 21, 2123, 43251, 4352, 456, 65, 23, 67, 3456, -542};
    // quick_sort(vec, 0, vec.size() - 1);
    vector<int> temp(vec.size(), 0);

    for (auto x : vec)
        cout << x << " ";
    cout << endl;
    // Heap a(vec);
    // a.makeheap1();
    // a.sortheap();
    // mearge_sort(vec,temp,0,vec.size() - 1);
    //bubblesort(vec);
    //Shellsort a(vec);
    //a.sort();
    countingsort(vec);
    radissort(vec);
    // for (auto x : a.vec)
    //     cout << x << " ";

    return 0;
}

《新程序员》：云原生和全面数字化实践

50位技术专家共同创作，文字、视频、音频交互阅读