終于到了堆排序了，不過(guò)在寫(xiě)堆排序之前得先看看選擇排序，畢竟堆排序的根本思想還是源于選擇排序
選擇排序：
i<--1 ~ length - 2
對(duì)元素a[i]，從i + 1 ~ length - 1中選擇出比i小的那個(gè)最小的數(shù)(假設(shè)為a[j])，然后交換a[i]與a[j]的值，然后對(duì)i進(jìn)行遍歷。
思想就是這么簡(jiǎn)單，很明顯選擇排序時(shí)間復(fù)雜度為O(n2)。
1 /********************************
2 * high為要排序數(shù)組的最后一個(gè)元素的下一個(gè)地址
3 ********************************/
4 void SimpleSort(int a[], int low, int high)
5 {
6 int i, j;
7 int value, index;
8
9 for (i = low; i < high; ++i)
10 {
11 value = a[i];
12 index = i;
13
14 for (j = i + 1; j <= high; ++j)
15 {
16 if (a[j] < value)
17 {
18 value = a[j];
19 index = j;
20 }
21 }
22
23 if (index != i)
24 {
25 EXCHANGE(a[i], a[index]);
26 }
27 }
28 }
EXCHANGE就是一個(gè)簡(jiǎn)單的交換元素值的函數(shù)，可以寫(xiě)成內(nèi)聯(lián)函數(shù)的形式：
1 inline void EXCHANGE(int &a, int &b)
2 {
3 a = a ^ b;
4 b = a ^ b;
5 a = a ^ b;
6 }
比較簡(jiǎn)單，不再贅述。
下面還是看堆排序吧，其實(shí)我覺(jué)得它應(yīng)該和快排一樣有魅力：
先是在一個(gè)普通數(shù)組中建堆；然后再在建好的堆的基礎(chǔ)上進(jìn)行堆排序。
核心的代碼應(yīng)該是下面的這個(gè)函數(shù)：
1 void max_heapify(int a[], int head, int tail)
2 {
3 int largest;
4 int left = LEFT(head);
5 int right = RIGHT(head);
6
7 if (left < tail && a[left] > a[head])
8 {
9 largest = left;
10 }
11 else
12 {
13 largest = head;
14 }
15
16 if (right < tail && a[right] > a[largest])
17 {
18 largest = right;
19 }
20
21 if (largest != head)
22 {
23 EXCHANGE(a[head], a[largest]);
24 max_heapify(a, largest, tail);
25 }
26 }
這個(gè)函數(shù)的功能就是調(diào)整堆結(jié)構(gòu)以使元素a[head]比它左右孩子都大。這里有個(gè)假設(shè)：就是假定a[head]的左右孩子都已經(jīng)是建好的堆了。
這個(gè)假設(shè)很重要，這就使得我們?cè)俳ǘ训臅r(shí)候需要由葉子節(jié)點(diǎn)往上建，反應(yīng)到數(shù)組上就是由a[(tail - 1) / 2]開(kāi)始往前。為什么不從a[tail - 1]開(kāi)始往前建呢？那是因?yàn)樽詀[(tail - 1) / 2]開(kāi)始到a[tail - 1]都是葉子節(jié)點(diǎn)，這些節(jié)點(diǎn)已經(jīng)是一個(gè)只包含一個(gè)節(jié)點(diǎn)的堆了，因此只需要從a[(tail - 1) / 2]開(kāi)始就可以了。看如下代碼：
1 void build_max_heap(int a[], int tail)
2 {
3 int i;
4
5 for (i = (tail - 1) / 2; i > 0; --i)
6 {
7 max_heapify(a, i, tail);
8 }
9 }
最后才是堆排序的代碼：
1 void heap_sort(int a[], int tail)
2 {
3 int i;
4 build_max_heap(a, tail);
5
6 for (i = tail - 1; i > 1; --i)
7 {
8 EXCHANGE(a[1], a[i]);
9 max_heapify(a, 1, i);
10 }
11 }
它首先調(diào)用函數(shù)build_max_heap()函數(shù)建堆，需要耗費(fèi)O(nlgn)時(shí)間，然后是根據(jù)已經(jīng)建立好的堆進(jìn)行排序的過(guò)程了：這個(gè)過(guò)程說(shuō)起來(lái)也比較簡(jiǎn)單，每次都是讓堆的頂元素與堆的最后一個(gè)元素互換，然后再對(duì)堆頂進(jìn)行調(diào)整，即調(diào)用max_heapify()函數(shù)。這樣，當(dāng)循環(huán)結(jié)束時(shí)堆排序便完成了，實(shí)踐耗費(fèi)為O(nlgn)。因此總的說(shuō)來(lái)堆排序時(shí)間復(fù)雜度為O(nlgn)的。
posted on 2011-05-01 00:41
myjfm 閱讀(277)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
雜