排序算法@c++描述-堆排序

3.堆排序

#include <iostream>
#include <vector>

using namespace std;

inline int leftChild(int i)
{
    return 2 * i + 1;
}

template <typename T>
void percDown(vector<T> &a, int i, int n)
{
    int child;
    T tmp;
    for (tmp = a[i]; leftChild(i) < n; i = child) {
        child = leftChild(i);
        if (child != n - 1 && a[child] < a[child + 1])
            child++;
        if (tmp < a[child])
            a[i] = a [child];
        else
            break;
    }
    a[i] = tmp;
}

template <typename T>
void heapSort(vector<T> &a)
{
    /*build heap*/
    for (int i = a.size() / 2 - 1; i >= 0; i--)
        percDown(a, i, a.size());
    /*delete max*/
    for (int j = a.size() - 1; j > 0; j--) {
        swap(a[0], a[j]);
        percDown(a, 0, j);
    }
}

int main()
{
    vector<int> test = {190, 435, 834, 8954, 923, 56, 20 ,1, 934, 5465, 504, 23054, 430};
    heapSort(test);
    for (auto i : test)
        cout << i << " ";
    cout << endl;
    return 0;
}
  • 運(yùn)行結(jié)果:
$ ./a.out
1 20 56 190 430 435 504 834 923 934 5465 8954 23054

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市搭幻,隨后出現(xiàn)的幾起案子咧擂,更是在濱河造成了極大的恐慌,老刑警劉巖檀蹋,帶你破解...
    沈念sama閱讀 217,907評(píng)論 6 506
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件屋确,死亡現(xiàn)場離奇詭異,居然都是意外死亡续扔,警方通過查閱死者的電腦和手機(jī)攻臀,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,987評(píng)論 3 395
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來纱昧,“玉大人刨啸,你說我怎么就攤上這事∈洞啵” “怎么了设联?”我有些...
    開封第一講書人閱讀 164,298評(píng)論 0 354
  • 文/不壞的土叔 我叫張陵,是天一觀的道長灼捂。 經(jīng)常有香客問我离例,道長,這世上最難降的妖魔是什么悉稠? 我笑而不...
    開封第一講書人閱讀 58,586評(píng)論 1 293
  • 正文 為了忘掉前任宫蛆,我火速辦了婚禮,結(jié)果婚禮上的猛,老公的妹妹穿的比我還像新娘耀盗。我一直安慰自己想虎,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,633評(píng)論 6 392
  • 文/花漫 我一把揭開白布叛拷。 她就那樣靜靜地躺著舌厨,像睡著了一般。 火紅的嫁衣襯著肌膚如雪忿薇。 梳的紋絲不亂的頭發(fā)上裙椭,一...
    開封第一講書人閱讀 51,488評(píng)論 1 302
  • 那天,我揣著相機(jī)與錄音署浩,去河邊找鬼揉燃。 笑死,一個(gè)胖子當(dāng)著我的面吹牛瑰抵,可吹牛的內(nèi)容都是我干的你雌。 我是一名探鬼主播,決...
    沈念sama閱讀 40,275評(píng)論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼二汛,長吁一口氣:“原來是場噩夢啊……” “哼婿崭!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起肴颊,我...
    開封第一講書人閱讀 39,176評(píng)論 0 276
  • 序言:老撾萬榮一對(duì)情侶失蹤氓栈,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后婿着,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體授瘦,經(jīng)...
    沈念sama閱讀 45,619評(píng)論 1 314
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,819評(píng)論 3 336
  • 正文 我和宋清朗相戀三年竟宋,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了提完。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 39,932評(píng)論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡丘侠,死狀恐怖徒欣,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情蜗字,我是刑警寧澤打肝,帶...
    沈念sama閱讀 35,655評(píng)論 5 346
  • 正文 年R本政府宣布,位于F島的核電站挪捕,受9級(jí)特大地震影響粗梭,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜级零,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,265評(píng)論 3 329
  • 文/蒙蒙 一断医、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧,春花似錦孩锡、人聲如沸酷宵。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,871評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至炕置,卻和暖如春荣挨,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背朴摊。 一陣腳步聲響...
    開封第一講書人閱讀 32,994評(píng)論 1 269
  • 我被黑心中介騙來泰國打工默垄, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人甚纲。 一個(gè)月前我還...
    沈念sama閱讀 48,095評(píng)論 3 370
  • 正文 我出身青樓口锭,卻偏偏與公主長得像,于是被迫代替她去往敵國和親介杆。 傳聞我的和親對(duì)象是個(gè)殘疾皇子鹃操,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,884評(píng)論 2 354

推薦閱讀更多精彩內(nèi)容

  • Android 自定義View的各種姿勢1 Activity的顯示之ViewRootImpl詳解 Activity...
    passiontim閱讀 172,128評(píng)論 25 707
  • 在此特此聲明:一下所有鏈接均來自互聯(lián)網(wǎng),在此記錄下我的查閱學(xué)習(xí)歷程春哨,感謝各位原創(chuàng)作者的無私奉獻(xiàn) 荆隘! 技術(shù)一點(diǎn)一點(diǎn)積...
    遠(yuǎn)航的移動(dòng)開發(fā)歷程閱讀 11,118評(píng)論 12 197
  • 7.16號(hào)見到了歌神張學(xué)友,整場演唱會(huì)無尿點(diǎn)赴背。場地是奧林匹克體育場椰拒,中心舞臺(tái),360度無死角帥到爆炸凰荚,剛看到舞臺(tái)的...
    有耐心有信心閱讀 280評(píng)論 0 0
  • 最近燃观,《沃茲傳:與蘋果一起瘋狂》在多看閱讀上線,看過試讀版以后便瑟,雖然購買要25塊大洋缆毁,還是果斷購入。本書從各個(gè)方面...
    gzb1985閱讀 1,123評(píng)論 1 2
  • 在linux下胳徽,各種軟件的配置文件大多存儲(chǔ)于以“.”開頭以“rc”結(jié)尾的文件中并存放于用戶的個(gè)人目錄~/中积锅,也就是...
    wty21cn閱讀 3,410評(píng)論 0 1