快捷導(dǎo)航

堆排序算法(選擇排序改進(jìn))

更新時(shí)間：2014年01月09日 15:08:44 作者：

這篇文章主要介紹了堆排序算法(選擇排序改進(jìn))，有需要的朋友可以參考一下

首先要理解堆的含義：要么所有節(jié)點(diǎn)都不大于其子孩子節(jié)點(diǎn)數(shù)據(jù)，要么都不小于其子孩子節(jié)點(diǎn)數(shù)據(jù)

堆排序的核心思想：就是要滿足所有節(jié)點(diǎn)都滿足上面兩點(diǎn)，如何完成，看下面

堆排序的步驟：

1.首先要建成一個(gè)大頂堆或者小頂堆，在建的過(guò)程中其實(shí)就是調(diào)整節(jié)點(diǎn)的位置，首先要從最后最后一個(gè)節(jié)點(diǎn)的母親節(jié)點(diǎn)開(kāi)始，按照堆的含義調(diào)整。為什么不是最后一個(gè)或者其他？因?yàn)橐ＷC完整性和不必要性，所以只需從最后一個(gè)的母親節(jié)點(diǎn)開(kāi)始即可（下面的堆默認(rèn)存在順序結(jié)構(gòu)，從索引0開(kāi)始的，所以有些二叉樹(shù)的特性請(qǐng)查閱二叉樹(shù)），直至索引節(jié)點(diǎn)為0的節(jié)點(diǎn)。調(diào)整完成后即成為一個(gè)堆，但是這里的數(shù)據(jù)并沒(méi)有排序好，所以下一部調(diào)整順序。

2.從最后一個(gè)數(shù)據(jù)開(kāi)始，與第一個(gè)數(shù)據(jù)進(jìn)行交換，然后按照堆的含義調(diào)整第一個(gè)數(shù)據(jù)。為什么先選擇最后一個(gè)數(shù)據(jù)？因?yàn)槟J(rèn)情況下，最后一個(gè)或者是較大或者是較小，可以滿足調(diào)整要求。這時(shí)就考慮當(dāng)前所有數(shù)據(jù)減去最后一個(gè)，因?yàn)檫@個(gè)已是最大或者是最小，不必再考慮.。直至調(diào)整沒(méi)有任何數(shù)據(jù)，此時(shí)已完成排序。

具體圖例不再標(biāo)識(shí)，有此愛(ài)好可以參考其他書(shū)籍或者網(wǎng)上的介紹，下面看堆排序代碼：

復(fù)制代碼代碼如下:

int HeapSort(MergeType* L)
{
int i = 0;
if (!L->elem)
{
return -1;
}

//創(chuàng)建堆
for (int i = L->len/2-1; i >= 0; i--)
{
HeapAdjust(L, i, L->len-1);
}

//堆排序
for (i = L->len-1; i >= 0; i-- )
{
swap(L->elem[i], L->elem[0]);
HeapAdjust(L, 0, i-1);
}
return 0;
}

注意：
1）由于父子節(jié)點(diǎn)的關(guān)系，for循環(huán)第一個(gè)數(shù)據(jù)索引其實(shí)是L,len-1，但是其父母節(jié)點(diǎn)（i）與當(dāng)前節(jié)點(diǎn)（p）的關(guān)系：p = 2i+1 或者2i+2；如果存儲(chǔ)數(shù)據(jù)的節(jié)點(diǎn)第一個(gè)索引不是0而是1，這里p=2i或者p=2i+1，請(qǐng)參看有關(guān)書(shū)籍的證明，所以當(dāng)前父母節(jié)點(diǎn)：i =（p-1）/ 2 = (L.len-1-1)/2 = L.len/2-1

2）由于再次調(diào)整數(shù)據(jù)的時(shí)候是從最后一個(gè)數(shù)據(jù)，所以需要交換數(shù)據(jù)swap，再進(jìn)行當(dāng)前頂點(diǎn)數(shù)據(jù)也就是第一個(gè)數(shù)據(jù)的堆調(diào)整，但是此時(shí)調(diào)整的對(duì)象只是（0~i）這些數(shù)據(jù)，其他已經(jīng)排序好，所以不再需要調(diào)整

下面看一下調(diào)整代碼，如下：

復(fù)制代碼代碼如下:

int HeapAdjust(MergeType* L, int nPos, int nEnd)
{
 for (int i = nPos*2+1; i < nEnd ; i = 2*i+1)
 {
  if (L->elem[i] <= L->elem[i+1])
  {
   i++;
  }
  if (L->elem[nPos] >= L->elem[i])
  {
   break;
  }
  swap(L->elem[nPos], L->elem[i]);
  nPos = i;
 }
 return 0;
}

這里使用的是在一個(gè)層次上是數(shù)據(jù)直接交換，其實(shí)這不是必須的，因?yàn)樽詈蟛虐褦?shù)據(jù)放到最后的位置，所以也可以使用下面的代碼，減少?gòu)?fù)制的次數(shù)

復(fù)制代碼代碼如下:

int HeapAdjustEx(MergeType* L, int nPos, int nEnd)
{
int nTempkey = L->elem[nPos];

for (int i = nPos*2+1; i < nEnd ; i = 2*i+1)
{
  if (L->elem[i] <= L->elem[i+1])//選出最大的子孩子
  {
   i++;
  }
  if (nTempkey >= L->elem[i]) //如果當(dāng)前節(jié)點(diǎn)大于最大子孩子退出
  {
   break;
  }
  L->elem[nPos] = L->elem[i]; //否則進(jìn)行數(shù)據(jù)交換
  nPos = i;
}
L->elem[nPos] = nTempkey;
return 0;
}

這里就可以減少較多的復(fù)制操作，也就是俗稱的移動(dòng)操作次數(shù);這里for循環(huán)的起始節(jié)點(diǎn)按照上面的推論，子節(jié)點(diǎn)應(yīng)該為p=2i+1，所以第一個(gè)應(yīng)該為2*nPos+1，對(duì)應(yīng)當(dāng)前要比較節(jié)點(diǎn)的做孩子，右孩子為2*nPos+2，也就是左孩子+1，其他請(qǐng)看注釋。
時(shí)間復(fù)雜度：O（nlogn），分析過(guò)程暫略

您可能感興趣的文章: