goal00001111

     摘要: 快速排序是在實(shí)踐中最快的已知排序算法，它的平均運(yùn)行時(shí)間是O（NlogN）。該算法之所以特別快，主要是由于非常精練和高度優(yōu)化的內(nèi)部循環(huán)。在隊(duì)列中尋找合適的樞點(diǎn)元素，并按樞點(diǎn)元素劃分序列，是快速排序算法的關(guān)鍵。
為簡(jiǎn)單起見(jiàn)，我這里數(shù)組的第一個(gè)元素作為樞點(diǎn)元素，重新排列數(shù)組，使得樞點(diǎn)元素之前的元素都小于樞點(diǎn)元素，而樞點(diǎn)元素之后的元素都大于或等于樞點(diǎn)元素。  閱讀全文

     摘要: 排序在最壞的情況下，其時(shí)間復(fù)雜度也能達(dá)到O（nlogn）。相對(duì)于快速排序來(lái)說(shuō)，這是它最大的優(yōu)點(diǎn)，此外，堆排序僅需要一個(gè)記錄大小供交換用的輔助存儲(chǔ)空間。
堆排序的數(shù)據(jù)結(jié)構(gòu)是二叉堆，二叉堆的特點(diǎn)有兩個(gè)，一個(gè)是它是一棵完全二叉樹(shù)，另一個(gè)是它的根結(jié)點(diǎn)小于孩子結(jié)點(diǎn)，所以我們很容易找到它的最小結(jié)點(diǎn)----根結(jié)點(diǎn)；當(dāng)然如果你想找到最大結(jié)點(diǎn)的話，那就要掃描所有的葉子結(jié)點(diǎn)，這是很費(fèi)時(shí)間的，如果你想找的是最大結(jié)點(diǎn)的話，你最好把它弄成一個(gè)大頂堆，即一棵根結(jié)點(diǎn)大于孩子結(jié)點(diǎn)的完全二叉樹(shù)。
二叉堆通常用數(shù)組來(lái)實(shí)現(xiàn)，它舍棄下標(biāo)0，從下標(biāo)1開(kāi)始置數(shù)，則很容易滿(mǎn)足，對(duì)于數(shù)組中任意位置i上的元素，其左兒子的位置在2i上，右兒子的位置在2i+1上，雙親的位置則在i/2上。
堆排序的算法之一是把數(shù)組構(gòu)建成二叉堆----這只要增添一個(gè)長(zhǎng)度為n+1的輔助空間，然后把原數(shù)組的元素依次插入到二叉堆即可。然后刪除二叉堆的根，把它作為排序后的數(shù)組的第一個(gè)元素,然后使二叉堆的長(zhǎng)度減1，并通過(guò)上移使得新得到的序列仍為二叉堆，再提取新二叉堆的第一個(gè)元素到新數(shù)組。依此類(lèi)推，直到提取最后  閱讀全文