现在的位置: 首页 > 综合 > 正文

堆排序复习

2013年07月01日 ⁄ 综合 ⁄ 共 497字 ⁄ 字号 评论关闭

堆排序是一种常见的复杂度为log复杂度的算法,具体实现如下:

void adjust_element(vector<int>& data, int i)
{
    if (2 * i + 1 >= data.size())
        return ;
    int index = 2 * i + 1;
    int min = data[index];
    if (2 * i + 2 < data.size() && data[2 * i + 2] < min)
    {
        min = data[2 * i + 2];
        index = 2 * i + 2;
    }
    if (data[i] > min)
    {
        int x = data[i];
        data[i] = min;
        data[index] = x;
        adjust_element(data, index);
    }
}
void heap_sort(vector<int>& data)
{
    for (int i = data.size() / 2 - 1; i >= 0; --i)
        adjust_element(data, i);
    for (int i = data.size() - 1; i >= 0; --i)
    {
        cout << data[0] << ",";
        data[0] = data[i];
        data.resize(data.size() - 1);
        adjust_element(data, 0);
    }
}

 

抱歉!评论已关闭.