我所理解的堆排序算法
堆排序在最壞的情況下，其時(shí)間復(fù)雜度也能達(dá)到O（nlogn）。相對(duì)于快速排序來說，這是它最大的優(yōu)點(diǎn)，此外，堆排序僅需要一個(gè)記錄大小供交換用的輔助存儲(chǔ)空間。
堆排序的數(shù)據(jù)結(jié)構(gòu)是二叉堆，二叉堆的特點(diǎn)有兩個(gè)，一個(gè)是它是一棵完全二叉樹，另一個(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í)現(xiàn)，它舍棄下標(biāo)0，從下標(biāo)1開始置數(shù)，則很容易滿足，對(duì)于數(shù)組中任意位置i上的元素，其左兒子的位置在2i上，右兒子的位置在2i+1上，雙親的位置則在i/2上。
堆排序的算法之一是把數(shù)組構(gòu)建成二叉堆----這只要增添一個(gè)長度為n+1的輔助空間，然后把原數(shù)組的元素依次插入到二叉堆即可。然后刪除二叉堆的根，把它作為排序后的數(shù)組的第一個(gè)元素,然后使二叉堆的長度減1，并通過上移使得新得到的序列仍為二叉堆，再提取新二叉堆的第一個(gè)元素到新數(shù)組。依此類推，直到提取最后一個(gè)元素，新得到的數(shù)組就是排序后的數(shù)組。
算法如下：
template <class T>
void Insert(T a[], int len, T x)//把x插入到原長度為len的二叉堆，注意保證新二叉堆不越界
{
int i;
for (i=len; i/2>0 && a[i/2]>x; i/=2)
a[i] = a[i/2];
a[i] = x;
}
template <class T>
T DeleteMin(T a[], int len)//刪除二叉堆的根，并通過上移使得新得到的序列仍為二叉堆
{
if (len == 0)
exit(1);
T min = a[1];//二叉堆的根
T last = a[len--];//二叉堆的最后一個(gè)元素
int c;
int i;
for (i=1; i*2<=len; i=c)//把二叉堆的某些元素往前移，使得新得到的序列仍為二叉堆
{
c = i * 2;//i的左兒子
if (c != len && a[c+1] < a[c])//若i有右兒子，且右兒子小于左兒子，c指向右兒子
c++;
if (last > a[c])//若i的小兒子小于二叉堆的最后一個(gè)元素，把其移到i的位置
a[i] = a[c];
else
break;
}
a[i] = last; //把二叉堆的最后一個(gè)元素放到適當(dāng)?shù)目瘴唬藭r(shí)得到的序列仍為二叉堆
return min;
}
template <class T>
void HeapSort(T a[], int len)
{
T *ca = new T[len+1]; //復(fù)制原數(shù)組到二叉堆
ca[0] = 0;
for (int i=0; i<len; i++) //把元素依次插入到二叉堆
Insert(ca, i+1, a[i]);
for (int i=0; i<len; i++)//依次提取二叉堆的根作為排序后的數(shù)組的元素
{
a[i] = DeleteMin(ca, len-i);
}
a[len-1] = ca[1]; //注意不能忘了最后一個(gè)元素
delete []ca;
}
在《數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析》（李春葆 編著 清華大學(xué)出版社）中看到一個(gè)類似的算法，它是把原數(shù)組構(gòu)建成一個(gè)大頂堆，然后把大頂堆的第一個(gè)元素與最后一個(gè)元素交換；再把前n-1個(gè)元素重新構(gòu)造成一個(gè)大頂堆，把新大頂堆的第一個(gè)元素與最后一個(gè)元素交換；依此類推，直到新大頂堆只有一個(gè)元素，這樣就得到了一個(gè)有序的二叉堆。
算法如下：
template <class T>
void HeapSort(T a[], int len)
{
T *ca = new T[len+1];
ca[0] = 0;
for (int i=0; i<len; i++)
ca[i+1] = a[i];
for (int i=len/2; i>0; i--) //建立初始堆
HeapAdjust(ca, len, i);
for (int i=len; i>1; i--)//進(jìn)行l(wèi)en-1次循環(huán)，完成堆排序
{
Swap(ca[1], ca[i]); //新大頂堆的第一個(gè)元素與最后一個(gè)元素交換
HeapAdjust(ca, i-1, 1);//篩a[1]元素，得到i-1個(gè)元素的堆
}
for (int i=0; i<len; i++)
a[i] = ca[i+1];
delete []ca;
}
template <class T>
void HeapAdjust(T a[], int len, int left) //將i與其小兒子交換位置
{
if (len == 0)
exit(1);
T x = a[left];
int i = left;
int c = 2 * i;
while (c <= len)
{
if (c < len && a[c+1] > a[c])//若i有右兒子，且右兒子大于左兒子，c指向右兒子
c++;
if (last < a[c])//若i的大兒子大于二叉堆的最后一個(gè)元素，把其移到i的位置
{
a[i] = a[c];
i = c;
c = 2 * i;
}
else
break;
}
a[i] = x; //把原二叉堆的第一個(gè)元素放到適當(dāng)?shù)目瘴?br>}
template <class T>
void Swap(T & a, T & b)
{
T t = a;
a = b;
b = t;
}
還有一種方法是每次都要重新調(diào)整大頂堆，使得父親比兒子大，這樣調(diào)整的函數(shù)較簡單，
但因?yàn)槊看味家闅v一半的元素，時(shí)間復(fù)雜度較大。
算法如下：
template <class T>
void HeapSort(T a[], int len)
{
T *ca = new T[len+1];
ca[0] = 0;
for (int i=0; i<len; i++)
ca[i+1] = a[i];
for (int i=len/2; i>0; i--) //把原數(shù)組構(gòu)建成一個(gè)大頂堆
HeapAdjust(ca, len, i);
Swap(ca[1], ca[len]); //把大頂堆的第一個(gè)元素與最后一個(gè)元素交換
for (int i=len-1; i>0; i--)
{
for (int j=i/2; j>0; j--)//遍歷長度為i的堆，得到新的大頂堆
HeapAdjust(ca, i, j);
Swap(ca[1], ca[i]);
}
for (int i=0; i<len; i++)
a[i] = ca[i+1];
delete []ca;
}
template <class T>
void HeapAdjust(T a[], int len, int i) //將i與其小兒子交換位置
{
int c = 2 * i;
if (c < len)
{
T & max = (a[c] > a[c+1])? a[c] : a[c+1];
if (a[i] < max)
Swap(a[i], max);
}
else
{
if (a[i] < a[c])
Swap(a[i], a[c]);
}
}
template <class T>
void Swap(T & a, T & b)
{
T t = a;
a = b;
b = t;
}
模仿構(gòu)造大頂堆的方法，我們可以調(diào)用HeapAdjust()構(gòu)造一個(gè)二叉堆，并提取二叉堆的根到新數(shù)組，
然后把原二叉堆的最后一個(gè)元素放到根的位置，再調(diào)用HeapAdjust()構(gòu)造一個(gè)新二叉堆，依此類推。
算法如下：
template <class T>
void HeapSort(T a[], int len)
{
T *ca = new T[len+1];
ca[0] = 0;
for (int i=0; i<len; i++)
ca[i+1] = a[i];
for (int i=len/2; i>0; i--) //把原數(shù)組構(gòu)建成一個(gè)大頂堆
HeapAdjust(ca, len, i);
a[0] = ca[1];
ca[1] = ca[len]; //把二叉堆的最后一個(gè)元素放到根的位置
for (int i=len-1; i>0; i--)
{
for (int j=i/2; j>0; j--)
HeapAdjust(ca, i, j);
a[len-i] = ca[1];
ca[1] = ca[i]; //把二叉堆的最后一個(gè)元素放到根的位置
}
delete []ca;
}
template <class T>
void HeapAdjust(T a[], int len, int i)
{
int c = 2 * i;
if (c < len)
{
T & min = (a[c] < a[c+1])? a[c] : a[c+1];
if (a[i] > min)
Swap(a[i], min);
}
else
{
if (a[i] > a[c])
Swap(a[i], a[c]);
}
}
template <class T>
void Swap(T & a, T & b)
{
T t = a;
a = b;
b = t;
}
后面兩種方法采用的是遞歸，容易理解，但時(shí)間復(fù)雜度較高，因?yàn)楸惹皟煞N要慢上很多，所以不可能是O（nlogn），估計(jì)是O（n^2），但具體我也不會(huì)算，請(qǐng)高手指教。