排序算法——堆排序

前言

对于推排序它像合并排序而不像插入排序，堆排序的运行时间为O(nlogn)。像插入排序而不像合并排序，它是一种原地排序算法：在任何时候，数组中只有常数和元素存储在输入数组以外。这样堆排序就拥有了两种排序算法的优点。

堆算法中涉及到的主要算法有：维持最大堆（Max_Heapify）和建立堆（Build_Max_Heap）。

1. 编码实现

这里为了使得数组的下标是从1开始计算的，在数组的首部插入了元素-1 。

1.1 维护最大堆

//维持堆性质
int heap_size = 0;  //堆中元素
void Max_Heapify(std::vector<int>& vec, int pos)    //pos为当前操作的根位置
{
    int left(pos*2);
    int right(pos*2+1);

    //求出最大的根节点
    int root_pos(-1);
    if(left<=heap_size && vec[pos]<vec[left])
    {
        root_pos = left;
    }
    else
    {
        root_pos = pos;
    }
    if(right<=heap_size && vec[root_pos]<vec[right])
    {
        root_pos = right;
    }

    //不满足最大堆的性质了，因为比较之后求出来的根节点和输入的节点不一样
    if(root_pos != pos)
    {
        std::swap(vec[root_pos], vec[pos]);
        Max_Heapify(vec, root_pos);
    }
}

1.2 创建最大堆

//创建堆
void Build_Max_Heap(std::vector<int>& vec)
{
    //由于堆中有heap_size/2~heap_size 的元素为叶子节点，因而只需要迭代heap_size/2次
    for(int i=(heap_size/2); i>=1; --i)
    {
        Max_Heapify(vec, i);
    }
}

1.3 堆排序

//堆算法
void HeapSort(std::vector<int>& vec)
{
    int len(vec.size());
    if(len == 0) return;
    cout << "display origin array:" << endl;
    for_each(vec.begin(), vec.end(), Disp<int>());  //打印原始的数据

    std::vector<int> temp = vec;
    heap_size = vec.size();
    temp.insert(temp.begin(), -1);
    Build_Max_Heap(temp);
    int loop = heap_size;
    for(int i=heap_size; i>=1; --i)
    {
        vec[i-1] = temp[1];
        std::swap(temp[1], temp[i]);
        temp.pop_back();
        --heap_size;
        Max_Heapify(temp, 1);
    }

    cout << "\narray sorted:" << endl;
    for_each(vec.begin(), vec.end(), Disp<int>());
}