av性色,夜操,久久精品

首先要理解堆的含義：要么所有節點都不大于其子孩子節點數據，要么都不小于其子孩子節點數據

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

堆排序的步驟：

1.首先要建成一個大頂堆或者小頂堆，在建的過程中其實就是調整節點的位置，首先要從最后最后一個節點的母親節點開始，按照堆的含義調整。為什么不是最后一個或者其他？因為要保證完整性和不必要性，所以只需從最后一個的母親節點開始即可（下面的堆默認存在順序結構，從索引0開始的，所以有些二叉樹的特性請查閱二叉樹），直至索引節點為0的節點。調整完成后即成為一個堆，但是這里的數據并沒有排序好，所以下一部調整順序。

2.從最后一個數據開始，與第一個數據進行交換，然后按照堆的含義調整第一個數據。為什么先選擇最后一個數據？因為默認情況下，最后一個或者是較大或者是較小，可以滿足調整要求。這時就考慮當前所有數據減去最后一個，因為這個已是最大或者是最小，不必再考慮.。直至調整沒有任何數據，此時已完成排序。

具體圖例不再標識，有此愛好可以參考其他書籍或者網上的介紹，下面看堆排序代碼：

復制代碼代碼如下:

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

//創建堆
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）由于父子節點的關系，for循環第一個數據索引其實是L,len-1，但是其父母節點（i）與當前節點（p）的關系：p = 2i+1 或者2i+2；如果存儲數據的節點第一個索引不是0而是1，這里p=2i或者p=2i+1，請參看有關書籍的證明，所以當前父母節點：i =（p-1）/ 2 = (L.len-1-1)/2 = L.len/2-1

2）由于再次調整數據的時候是從最后一個數據，所以需要交換數據swap，再進行當前頂點數據也就是第一個數據的堆調整，但是此時調整的對象只是（0~i）這些數據，其他已經排序好，所以不再需要調整

下面看一下調整代碼，如下：

復制代碼代碼如下:

	
	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;

	}

這里使用的是在一個層次上是數據直接交換，其實這不是必須的，因為最后才把數據放到最后的位置，所以也可以使用下面的代碼，減少復制的次數

復制代碼代碼如下:

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]) //如果當前節點大于最大子孩子退出
  {
   break;
  }
  L->elem[nPos] = L->elem[i]; //否則進行數據交換
  nPos = i;
}
L->elem[nPos] = nTempkey;
return 0;
}