終于到了堆排序了，不過在寫堆排序之前得先看看選擇排序，畢竟堆排序的根本思想還是源于選擇排序
選擇排序：
i<--1 ~ length - 2
對元素a[i]，從i + 1 ~ length - 1中選擇出比i小的那個最小的數(假設為a[j])，然后交換a[i]與a[j]的值，然后對i進行遍歷。
思想就是這么簡單，很明顯選擇排序時間復雜度為O(n2)。
1 /********************************
2 * high為要排序數組的最后一個元素的下一個地址
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就是一個簡單的交換元素值的函數，可以寫成內聯函數的形式：
1 inline void EXCHANGE(int &a, int &b)
2 {
3 a = a ^ b;
4 b = a ^ b;
5 a = a ^ b;
6 }
比較簡單，不再贅述。
下面還是看堆排序吧，其實我覺得它應該和快排一樣有魅力：
先是在一個普通數組中建堆；然后再在建好的堆的基礎上進行堆排序。
核心的代碼應該是下面的這個函數：
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 }
這個函數的功能就是調整堆結構以使元素a[head]比它左右孩子都大。這里有個假設：就是假定a[head]的左右孩子都已經是建好的堆了。
這個假設很重要，這就使得我們再建堆的時候需要由葉子節點往上建，反應到數組上就是由a[(tail - 1) / 2]開始往前。為什么不從a[tail - 1]開始往前建呢？那是因為自a[(tail - 1) / 2]開始到a[tail - 1]都是葉子節點，這些節點已經是一個只包含一個節點的堆了，因此只需要從a[(tail - 1) / 2]開始就可以了。看如下代碼：
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 }
它首先調用函數build_max_heap()函數建堆，需要耗費O(nlgn)時間，然后是根據已經建立好的堆進行排序的過程了：這個過程說起來也比較簡單，每次都是讓堆的頂元素與堆的最后一個元素互換，然后再對堆頂進行調整，即調用max_heapify()函數。這樣，當循環結束時堆排序便完成了，實踐耗費為O(nlgn)。因此總的說來堆排序時間復雜度為O(nlgn)的。
posted on 2011-05-01 00:41
myjfm 閱讀(297)
評論(0) 編輯 收藏 引用 所屬分類:
雜