// 冒泡排序
void BubbleSort(vector<int>& vec)
{
    int sz = vec.size();
    for (int i = 0; i < sz-1; ++i)
    {
        bool flag = true;
        for (int j = sz - 1; j > i; --j)
        {
            if (vec[j] < vec[j-1])
            {
                int temp = vec[j];
                vec[j] = vec[j-1];
                vec[j-1] = temp;
                flag = false;
            }
        }
        if (flag == true)
            break;
    }
}
// 快速排序
void quickSort(vector<int>& vec, int left, int right)
{
    if (left >= right)
        return;
    int base = vec[left];
    int _left = left, _right = right;
    while (left < right)
    {
        while (left<right && vec[right]>base) --right;
        vec[left] = vec[right];
        while (left < right && vec[left] <= base) ++left;
        vec[right] = vec[left];
    }
    vec[left] = base;
    quickSort(vec, _left, left - 1);
    quickSort(vec, left + 1, _right);
}
// 堆排序
struct heapSort
{
    heapSort(vector<int> &v):vec(v)
    {
        cout << "调用拷贝构造函数" << endl;
        buildMaxHeap();
    }

    heapSort(vector<int>&& v) :vec(move(v)) 
    { 
        cout << "调用移动构造函数" << endl;
        buildMaxHeap();
    }

    void buildMaxHeap()
    {
        int size = vec.size();
        for (int i = (size >> 1); i >= 0; --i)
            headAdjust(i, size);
    }

    void headAdjust(int i, int len)
    {
        int cur = vec[i];
        // int size = vec.size();
        for (int k = 2 * i; k < len; k *= 2)
        {
            if (k + 1 < len && vec[k] < vec[k + 1])
                k += 1;
            if (vec[k] <= cur)
                break;
            else
            {
                vec[i] = vec[k];
                i = k;
            }
        }
        vec[i] = cur;
    }

    void insert(int num)
    {
        vec.insert(vec.begin(), num);
        headAdjust(0, vec.size());
    }

    
    void print()
    {
        vector<int> temp_vec(vec);
        int size = vec.size();
        for (int i = size - 1; i > 0; --i)
        {
            swap(vec[0], vec[i]);
            headAdjust(0, i);
        }
        for (int i = 0; i < size; ++i)
            cout << vec[i] << ' ';
        cout << endl;
        vec = temp_vec;
    }

    vector<int> vec;
};

int upper_bound(vector<int>& vec, int left, int right, int target)
{
    int pose = -1;
    while (left <= right)
    {
        int mid = left + ((right - left) >> 1);
        if (vec[mid] > target)
        {
            pose = mid;
            right = mid - 1;
        }
        else
            left = mid + 1;
    }
    return pose;
}
// 插入排序
void insertSort(vector<int>& vec)
{
    for (int i = 1; i < vec.size(); ++i)
    {
        if (vec[i] < vec[i - 1])
        {
            int temp = vec[i];
            int pos = upper_bound(vec, 0, i - 1, temp);
            for (int j=i; j >pos; --j)
                vec[j] = vec[j-1];
            vec[pos] = temp;
        }
    }
}
// 希尔排序
void ShellSort(vector<int>& vec)
{
    for (int interval = 6; interval >= 1; interval /= 2)
    {
        for (int i = interval; i < vec.size(); i+=1)
        {
            if (vec[i] < vec[i - interval])
            {
                int temp = vec[i];
                int k = i - interval;
                for (; k >= 0; k -= interval)
                {
                    if (temp > vec[k])
                        break;
                    vec[k + interval] = vec[k];
                }
                vec[k += interval] = temp;
            }
        }
    }
}
// 归并排序
vector<int> v_temp;

void MergeSort(vector<int>& vec, int left, int right)
{
    if (left >= right)
        return;
    int mid = left + ((right - left) >> 1);
    MergeSort(vec, left, mid);
    MergeSort(vec, mid + 1, right);
    int p0 = left, p1 = mid + 1, i = left;
    while (p0 <= mid && p1 <= right)
    {
        if (vec[p0] < vec[p1])
            v_temp[i++] = vec[p0++];
        else
            v_temp[i++] = vec[p1++];
    }
    while (p0 <= mid)
        v_temp[i++] = vec[p0++];
    while (p1 <= right)
        v_temp[i++] = vec[p1++];
    for (int i = left; i <= right; ++i)
        vec[i] = v_temp[i];
}
复制