今天自己研究了堆排序，發(fā)現(xiàn)個問題，你認(rèn)證他就很簡單你不認(rèn)真就很難。用心去看任何算法都是很有魅力的，以前復(fù)習(xí)的時候感覺所有的算法都是背會的，這次復(fù)習(xí)感覺很爽所有的都是靠理解來處理；下面我就把自己簡單的理解寫寫做個小記錄方便后續(xù)鞏固

1.先把數(shù)據(jù)構(gòu)建一個堆，這里我們選用大根堆（就是每個節(jié)點(diǎn)的值都不大于其父節(jié)點(diǎn)的值）。

? 處理的具體步驟是從樹的第一個非葉子節(jié)點(diǎn)開始，一般都是從n/2節(jié)點(diǎn)開始，如果2*n<=n 則2*n是其左子節(jié)點(diǎn)， 如果2*n+1 <=n。

? 從n/2節(jié)點(diǎn)開始，把n/2節(jié)點(diǎn)和其左右子節(jié)點(diǎn)中較大的值進(jìn)行比較，如果子節(jié)點(diǎn)的值大于父節(jié)點(diǎn)的值那么就交換兩者的值。

? 處理完該節(jié)點(diǎn)在下一個非葉子節(jié)點(diǎn)重復(fù)上面的步驟，如果出現(xiàn)數(shù)據(jù)交換的情況導(dǎo)致堆被破壞就重新整理調(diào)整。直至所有的節(jié)點(diǎn)都滿足為止。

2.經(jīng)過上面的處理之后，下面就開始排序，主要就是把堆最后一個子節(jié)點(diǎn)n-1的數(shù)據(jù)和根節(jié)點(diǎn)0的數(shù)據(jù)對換，對換后我們就得到了新的被破壞的堆和排序數(shù)組 ? n，繼續(xù)按 ? 照步驟1的過程重新調(diào)整被破壞的堆，調(diào)整完成后把最新的堆的最后一個數(shù)據(jù)n-2的數(shù)據(jù)和根節(jié)點(diǎn)0的數(shù)據(jù)對換，...一直重復(fù)知道得到我們的排序數(shù)組[a0 a1 a2 ... n]為 ?止。

?

下面貼個我寫的代碼

void HeapSort(int* a, int n) {for (int i = n / 2 - 1; i >= 0; i--)//從樹的第一個非葉子節(jié)點(diǎn)的節(jié)點(diǎn)開始，第一個非葉子節(jié)點(diǎn)的節(jié)點(diǎn)id是n/2 {while (2 * i + 1 < n)//有左節(jié)點(diǎn) {int j = 2 * i + 1;if ((j + 1 < n) && (a[j] < a[j + 1]))//有右側(cè)節(jié)點(diǎn)，同時右側(cè)節(jié)點(diǎn)大于左側(cè)節(jié)點(diǎn) {++j;}if (a[i] < a[j])//交換父節(jié)點(diǎn)和子節(jié)點(diǎn)的數(shù)據(jù){int t = a[i];a[i] = a[j];a[j] = t;i = j;//堆被破壞，重新整理}else{break;}}}//調(diào)整完后進(jìn)行處理for (int i = n - 1; i > 0; i--){int t = a[i];a[i] = a[0];a[0] = t;//交換完畢，開始重新調(diào)整int k = 0;while (2 * k + 1 < i){int j = 2 * k + 1;if ((j + 1) < i && a[j] < a[j + 1]){++j;}if (a[k] < a[j]){int t = a[k];a[k] = a[j];a[j] = t;k = j;}else{break;}}} }#define MAX_LEN 10 int _tmain(int argc, _TCHAR* argv[]) {int *a = new int[MAX_LEN];memset(a, 0, MAX_LEN);srand(time_t(NULL));for (int i = 0; i < MAX_LEN; i++){a[i] = rand() % 100;printf("%d ", a[i]);}printf("\n");printf("開始排序\n");int tick = GetTickCount(); HeapSort(a, MAX_LEN );printf("\n");printf("排序用時:%d\n", GetTickCount() - tick);for (int i = 0; i < MAX_LEN; i++){printf("%d ", a[i]);}system("pause");return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/davygeek/p/4379596.html

總結(jié)

以上是生活随笔為你收集整理的堆排序实践的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。