大學(xué)的時(shí)候很多學(xué)長就跟我們講打好基礎(chǔ)，基礎(chǔ)決定了未來的成長的高度克锣，工作幾年來也參加了不少面試，那么多面試腔长，首先都是基礎(chǔ)袭祟，甚至有的面試全部算法和數(shù)據(jù)結(jié)構(gòu)，也許大學(xué)里學(xué)的挺扎實(shí)的捞附，工作后算法用的少巾乳，很多東西都忘了您没。所以需要慢慢的拾起來。
排序中被問得最多的是快速排序和堆排序胆绊，對于堆排序氨鹏，大學(xué)都學(xué)過，大概知道就是有大根堆压状，小根堆以及重建堆仆抵，很多人也就記得一個(gè)大概，讓具體寫就不知道怎么寫了种冬。
1.定義
堆邏輯上可以看成滿二叉樹肢础，所以有k個(gè)節(jié)點(diǎn)，那么父節(jié)點(diǎn)就是k/2碌廓，堆的定義中要求每個(gè)節(jié)點(diǎn)
大根堆：1.a[k] >= a[2k] && a[k] >= a[2k+1]
小根堆：1.a[k] <= a[2k] && a[k] <= a[2k+1]
堆排序并不是指這個(gè)堆是有序的传轰，它的排序是不斷的把根節(jié)點(diǎn)移到末尾然后重建剩余的堆，使之繼續(xù)構(gòu)造大根堆或者小根堆谷婆，再次移除慨蛙，重建，每次移出來的都是剩余中最大的或者最小的纪挎，數(shù)據(jù)就有序了期贫。
2.建初始堆
堆排序首先要解決的問題，建初始堆异袄，就是把最初的數(shù)據(jù)建成大根堆或者小根堆通砍。那小根堆來說，根據(jù)定義烤蜕，需要讓父節(jié)點(diǎn)小于子節(jié)點(diǎn)封孙，所以我們重建堆或者調(diào)整堆就是調(diào)整父節(jié)點(diǎn)和子結(jié)點(diǎn)的位置。
//調(diào)整lst[s..m]為一個(gè)小根堆
void HeadAdjust(int *lst, int s, int m) {
int t = lst[s];
for (int j = 2 * s; j < m; j *= 2) { //對j的子結(jié)點(diǎn)進(jìn)行篩選
//如果右結(jié)點(diǎn)小于左節(jié)點(diǎn)讽营，j+1,j始終記錄的是最小的結(jié)點(diǎn)下標(biāo)
if (j < m && lst[j] > lst[j+1])
++j;
//如果左右結(jié)點(diǎn)中最小的結(jié)點(diǎn)都比父節(jié)點(diǎn)小虎忌，不用調(diào)整
if (t <= lst[j]) break;
//需要調(diào)整，t已經(jīng)記錄了最初的lst[s]的值,直接覆蓋橱鹏，s記錄了上次調(diào)整的下標(biāo)
lst[s] = lst[j];
s = j;
}
lst[s] = t; //調(diào)整結(jié)束膜蠢，s就是t最終的位置。
}
設(shè)想如果一個(gè)二叉樹莉兰，如果最下層的結(jié)點(diǎn)都是小根堆挑围，那么只需依次從最下層往上調(diào)整，最終就能調(diào)整為一個(gè)小根堆糖荒，即根節(jié)點(diǎn)就是最小的結(jié)點(diǎn)杉辙。所以建初始堆的代碼：
void InitHeap(int *lst, int size) {
//從最下層開始調(diào)整，依次往上寂嘉，直到根節(jié)點(diǎn)
for (int i = size/2; i > 0; --i) {
HeadAdjust(lst, i, size);
}
}
3.調(diào)整堆
初始小根堆建成以后奏瞬，根節(jié)點(diǎn)就是最小的節(jié)點(diǎn)枫绅，我們?nèi)〕龈?jié)點(diǎn)移到數(shù)組尾部，然后重建剩余的堆硼端，使之成繼續(xù)為小根堆并淋，如此往復(fù)直到只剩最后一個(gè)節(jié)點(diǎn)。
void ReBuildHeap(int *lst, int size) {
//從最下層開始調(diào)整珍昨，依次往上县耽，直到根節(jié)點(diǎn)
for (int i = size; i > 1; --i) {
//根結(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)交換，調(diào)整1..i-1為小根堆镣典。
std::swap(lst[i], list[1];
HeadAdjust(lst, 1, i-1);
}
//執(zhí)行結(jié)束兔毙，lst從1到size依次從大到小
}
完整代碼：
int main(int argc, char* argv[])
{
int list[10];
for (int i = 1; i < 10; ++i) {
list[i] = rand() % 10;
printf("%d ", list[i]);
}
for (int i = 9/2; i > 0; --i) {
HeadAdjust(list, i, 9);
}
std::cout << list[1] << std::endl;
for (int i = 9; i > 1; --i) {
std::swap(list[1], list[i]);
printf("\n%d", list[i]);
HeadAdjust(list, 1, i - 1);
}
return 0;
}
也算自己的一次加深理解吧，理解記憶兄春，只有真的理解了澎剥，才能記憶的更長久！
