在大量資料中找最大或最小一些元素時，使用堆排序往往會很高效，那么堆排序是如何實作的呢？首先通過堆進行排序必須得建一個堆，其次得明白升序，降序該建大堆還是小堆？
對于堆排序，我們必須得清楚以下幾點：
1.通常我們采用升序建大堆，降序建小堆的方法；
2.建好堆之后，下來就要對堆進行排序了；
以升序為例：首先將這組資料建一個大堆，建好之后交換堆頂與最后一個元素(堆頂元素肯定是堆中最大的數)，這會兒最大的那個數就調到了最后，然后再將不包含最后一個元素的堆從根節點起進行向下調整，使其依然滿足大堆的特點；
下一次再進行調整的時候，依然交換堆頂元素和最后一個元素，再將不包含最后一個元素的堆從根節點起進行向下調整……直至下調元素個數為0.
首先實作大堆升序：
#include<iostream>
#include
using namespace std;
void AdjustDown(int*a, size_t root, size_t size)
{
size_t parent = root;
size_t child = parent * 2+ 1;
while(child < size)
{
if(child + 1< size && a[child] < a[child + 1])
{
++child;
}
if(a[parent] < a[child])
{
swap(a[parent], a[child]);
parent = child;
child = parent*2+ 1;
}
else
{
break;
}
}
}
voidHeapSort(int* a,intsz)
{
assert(a);
for(inti=(sz-2)/2;i>=0;--i) //建堆，下調
{
AdjustDown(a,i,sz);
}
/*int end=sz-1;
while (end>0)
{
std::swap(a[0],a[end]); //這里的end代表元素下標，為最后一個元素
AdjustDown(a,0,end); //這個end代表需要下調的元素個數，第一次交換后只需要調sz-1個元素，不包括最后一個元素
--end; //注意每次交換元素后，下調元素個數都在減小(范圍縮小)
}*/
for(size_t i=0;i<sz;++i) for=""i="0;i<sz;++i)"int=""pre=""return=""sz="sizeof(a)/sizeof(a[0]);"void=""><p><strong>由于降序與升序的實作類似，所以采用仿函式的方式，增加代碼的復用性，</strong></p><pre >#pragma once
#include<iostream>
#include
using namespace std;
//升序建大堆，降序建小堆
template<classt="">
struct UpOrder
{
bool operator()(constT& l,constT& r)
{
returnl<r; t="">
struct DownOrder
{
bool operator()(constT& l,constT& r)
{
returnl>r;
}
};
template<classcompare="UpOrder<T">>
classHeapSort
{
public:
voidSort(T* a,size_t size)
{
assert(a);
for(inti=((int)size-2)/2;i>=0;--i)
{
AdjustDown(a,i,size);
}
for(size_t i=0;i<size;++i) 1=""child="parent*2+1;"compare=""else=""if=""parent="root;"pre=""protected:=""size=""size_t=""void="">
<strong>測驗代碼</strong>：<pre >#include"HeapSort.h"
voidTest1()
{
HeapSort<int> h;
inta[] = {10,11,13,12,16,18,15,17,14,19};
intsz=sizeof(a)/sizeof(a[0]);
h.Sort(a,sz);
for(inti=0;i<sz;++i) int=""void="">> h1;
inta[] = {10,11,13,12,16,18,15,17,14,19};
intsz=sizeof(a)/sizeof(a[0]);
h1.Sort(a,sz);
for(inti=0;i<sz;++i) int=""pre=""return=""><p> </p>
</sz;++i)></sz;++i)></int></pre>
</size;++i)></class></r;></class></assert.h></iostream></pre>
</sz;++i)></assert.h></iostream>
另外如果你想更好的提升你的編程能力，學好C語言C++編程！彎道超車，快人一步！筆者這里或許可以幫到你~
分享（原始碼、專案實戰視頻、專案筆記，基礎入門教程）
歡迎轉行和學習編程的伙伴，利用更多的資料學習成長比自己琢磨更快哦！
編程學習：
編程學習：
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/270555.html
標籤：C++