C/C++基础知识：堆排序

957 0 0

作者:大天使维迦

在大量数据中找最大或最小一些元素时，使用堆排序往往会很高效，那么堆排序是如何实现的呢？首先通过堆进行排序必须得建一个堆，其次得明白升序，降序该建大堆还是小堆？

对于堆排序，我们必须得清楚以下几点：

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="">由于降序与升序的实现类似，所以采用仿函数的方式，增加代码的复用性。<pre class="brush:java;">#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="">

测试代码：<pre class="brush:java;">#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=""> 

</sz;++i)></sz;++i)></int></pre>

</size;++i)></class></r;></class></assert.h></iostream></pre>

</sz;++i)></assert.h></iostream>