☺ 选择排序

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

template <typename T>
void printVec(const T &t)
{
    for (size_t i = 0; i < t.size(); i++)
    {
        cout << t[i] << " ";
    }
    cout << endl;
}

template <typename T>
void SimpleSelectSort(vector<T> &vec)
{
    size_t i, j, k;
    T temp;
    for (i = 0; i < vec.size(); i++)
    {
        k = i; //初始化最小值所在位置
        // find min
        for (j = i + 1; j < vec.size(); j++)
        {
            if (vec[j] < vec[k])
            {
                k = j;
            }
        }
        if (k != i)
        {
            std::swap(vec[k], vec[i]);
        }
    }
}

int main(int argc, char **argv)
{
    vector<int> vec = {6, 5, 4, 3, 2, 5, 6, 2, 5};
    SimpleSelectSort<int>(vec);
    printVec<vector<int>>(vec);
    // 2 2 3 4 5 5 5 6 6
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

template <typename T>
void printVec(const T& t)
{
    for (size_t i = 0; i < t.size(); i++)
    {
        cout << t[i] << " ";
    }
    cout << endl;
}

//下沉操作
void Sink(vector<int>& vec, size_t now,size_t size)
{
    //如果vec[i]有孩子，则左孩子为2k+1(root下标1则2k),右孩子为2k+2(root下标1则2k)
    while (2 * now + 1 < size) //有左孩子
    {
        size_t left = 2 * now + 1;                              //左孩子下标
        if (left + 1 < size && vec[left] < vec[left + 1]) //有右孩子且左孩子小于右孩子
        {
            left++;
        }
        //现在left指向了左右孩子中比较值较大的那一个
        if (vec[now] > vec[left]) //满足堆条件
        {
            break;
        }
        else //下沉到left位置
        {
            std::swap(vec[now], vec[left]);
        }
        //更新此时的位置
        now = left;
    }
}

//初始化堆
void CreateHeap(vector<int>& vec)
{
    //完全二叉树从最后一个有孩子的节点进行调整
    int mid = vec.size()+1 / 2;
    mid = mid - 1;
    for (int i = mid; i >= 0; i--)
    {
        Sink(vec, i,vec.size()); //下沉vec[i]
    }
}

void HeapSort(vector<int>& vec,vector<int>&sortedVec)
{
    cout <<"size of vec "<< vec.size() << endl;
    CreateHeap(vec); //构建初始堆
    cout << "init tree" << endl;
    printVec(vec);
    int n = vec.size()-1;//最后一个节点
    while (n >= 0) // n-1 twice
    {
        sortedVec.push_back(vec[0]);
        std::swap(vec[0], vec[n]);//将最后一个节点移动到根节点
        --n;//堆中剩余节点
        Sink(vec, 0,n+1); //堆下沉 root节点
    }

}

int main(int argc, char** argv)
{
    vector<int> vec = { 12, 16, 2, 30, 28, 20, 16, 6, 10, 18 };
    vector<int> sortedVec;
    HeapSort(vec,sortedVec);
    cout << "sorted Vec" << endl;
    printVec<vector<int>>(sortedVec);
    /*
    size of vec 10
    init tree
    30 28 20 16 18 2 16 6 10 12
    sorted Vec
    30 28 20 18 16 16 12 10 6 2
    */
    return 0;
}