排序算法

堆排序

第一步构建最大堆
第二部每次取出堆顶元素，然后调整余下的为最大堆

template <typename T>
void heapAdjust(std::vector<T> &v,int parent,int end)
{
    int left = 2 * parent + 1;
    int right = left + 1;
    int max_index = left;
    if(left <= end)
    {
        if(right <= end && v[right] > v[left])
            max_index = right;
        if(v[max_index] > v[parent])
        {
            std::swap(v[max_index], v[parent]);
            heapAdjust(v,max_index,end);
        }
    }
}


template <typename  T>
void HeapSort(std::vector<T> &v)
{
    //构建最大堆
    for(int parent = (v.size()-1) / 2 ; parent>=0 ;parent--)
        heapAdjust(v,parent,v.size()-1);
    //一个个的把堆顶的数放在末尾
    int end = v.size() - 1;
    while(end > 0)
    {
        std::swap(v[0],v[end]);
        end--;
        heapAdjust(v,0,end);
    }
}

归并排序

分治思想 把大数组分成两个数组 分别对俩子数组排序 然后合并成新的大数组

template <typename T>
void merge(std::vector<T> &v,int begin,int middle,int end)
{
    std::vector<T> help(static_cast<unsigned int>(end + 1 - begin));
    int i = begin;
    int j = middle+1;
    int k = 0;
    while(i <= middle && j <= end)
        if(v[i] > v[j])
            help[k++] = v[j++];
        else
            help[k++] = v[i++];
    
    while(i <= middle)
        help[k++] = v[i++];
    while(j <= end)
        help[k++] = v[j++];
    for(int m = begin;m <= end;m++)
        v[m] = help[m-begin];

}
template <typename T>
void MergeSort(std::vector<T> &v,int begin,int end)
{
    if(begin < end)
    {
        int middle = (begin + end) / 2;
        MergeSort(v,begin,middle);
        MergeSort(v,middle+1,end);
        merge(v,begin,middle,end);
    }
}
template <typename T>
void MergeSort(std::vector<T> &v)
{
    MergeSort(v,0,v.size()-1);
}

快速排序

template <typename T>
void quickSortAdjust(std::vector<T> &v,int begin,int end)
{
    if(begin >= end)
        return;
    int i = begin;
    int j = end;
    int choice = v[begin];
    while(i < j)
    {
        while(i < j && v[j] >= choice)
            j--;
        v[i] = v[j];
        while(i < j && v[i] < choice)
            i++;
        v[j] = v[i];
    }
    v[i] = choice;
    quickSortAdjust(v,begin,i-1);
    quickSortAdjust(v,i+1,end);
}

template <typename T>
void QuickSort(std::vector<T> &v)
{
    quickSortAdjust(v,0,v.size()-1);
}