数据结构 归并和计数排序

1.2-路归并排序：先将所有的数据完全分开，然后两两合并，在合并过程中将其排好序，最终得到一个完整的有序表。
时间复杂度：O(nlogn)
是否稳定：稳定
为非就地排序
2.基于统计的排序
    1.计数排序：统计一下每个数出现的次数，然后直接按次数输出
    //以空间换时间
    时间复杂度：O(n)
    是否稳定：稳定

    缺点：
        1.无法对负整数和浮点数排序
        优化：引入偏移量便可以对负整数进行排序
        对浮点数全部乘以10^n,便可以对浮点数排序
        2.极其浪费空间内存
        
    2.桶排序:桶编号规则人为确定，可以n/10，也可以n/100,将数据放入桶后，对每个桶进行排序
    //以空间换时间
    时间复杂度：O(nlogn)
    3.基数排序：类似于将桶排序与计数排序结合，从待排序数组当中，元素的最低有效位到最⾼有效位,逐位进⾏⽐较排序；此外，基数排序使⽤计数排序作为⼀个排序的⼦过程。
    时间复杂度:O(n * log以b为底n),b为进制数
    为非就地排序


#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
using namespace std;
//将区间[left,mid][mid+1,right]数据合并
void Merge(vector<int>(&v), int left, int mid, int right)
{
    int i(left);
    int j(mid + 1);
    //临时存储
    vector<int> v2(v);
    int k(0);
    while (i <= mid && j <= right)
    {
        if (v[i] <= v[j])
        {
            v2[k] = v[i];
            ++i;
            ++k;
        }
        else
        {
            v2[k] = v[j];
            ++j;
            ++k;
        }
    }
    while (i <= mid)
    {
        v2[k] = v[i];
        ++i;
        ++k;
    }
    while (j <= right)
    {
        v2[k] = v[j];
        ++j;
        ++k;
    }
    for (int q = 0; q < k; ++q)
    {
        v[left + q] = v2[q];
    }
}
//将区间[left,right]数据二分
void Merge_Sort(vector<int>(&v),int left,int right)
{
    //元素大于等于两个
    if (left < right)
    {
        int mid((left + right) / 2);
        //left---mid
        Merge_Sort(v, left, mid);
        //mid + 1---right
        Merge_Sort(v, mid + 1, right);
        //合并函数,mid为合并的位置
        Merge(v, left, mid, right);
    }
}
void Count_Sort(vector<int>(&v))
{
    vector<int> count;
    int max(-1);
    for (auto a : v)
    {
        if (a > max)
        {
            max = a;
        }
    }
    count.resize(max + 1);
    for (int i = 0; i < v.size(); ++i)
    {
        count[v[i]]++;
    }
    for (int i = 0; i < count.size(); ++i)
    {
        while (count[i] != 0)
        {
            cout << i << ' ';
            count[i]--;
        }
    }
}
int main()
{
    vector<int> v(10);
    int n(0);
    cin >> n;
    v.resize(n);
    for (auto& a : v)
    {
        cin >> a;
    }
    //Merge_Sort(v,0,v.size()-1);
    Count_Sort(v);
    /*for (auto a : v)
    {
        cout << a << ' ';
    }*/
    return 0;
}
/*
7
5
3
6
7
1
2
4
*/