堆排序（heap sort）的C++实现

堆排序（heap sort）的C++实现2015-10-08堆排序包含两个步骤:

第一步: 是建立大顶堆（从大到小排序）或小顶堆（从小到大排序）, 从下往上建立; 如建堆时, s是从大到小;

第二步: 是依次交换堆顶和堆底, 并把交换后的堆底输出, 只排列剩余的堆, 从上往下建立; 如构造时, s始终是1;

堆排序（Heap Sort）的时间复杂度是O（nlogn）, 最坏情况下也是如此.

而快速排序（Quick Sort）, 若初始记录序列有序, 快速排序将退化为起泡排序（Bubble Sort）, 时间复杂度是O（n^2）.

这是堆排序比快速排序的优点.

代码:

/** main.cpp**Created on: 2014.6.12*Author: Spike*//*eclipse cdt, gcc 4.8.1*/#include <iostream>#include <stack>#include <queue>using namespace std;void HeapAdjust （std::vector<int>& L, int s, int num）{int temp = L[s-1];for （int j=2*s; j<=num; j*=2） {if （j<num && L[j-1] > L[j]） //选取最小的结点位置++j;if （temp < L[j-1]） //不用交换break;L[s-1] = L[j-1]; //交换值s = j; //继续查找}L[s-1] = temp;}void HeapSort （std::vector<int>& L）{int num = L.size（）;for （int i=num/2; i>0; --i） {HeapAdjust（L, i, num）; //从第二层开始建堆}for （int i=num; i>1; --i） {std::swap（L[0], L[i-1]）;HeapAdjust（L, 1, i-1）; //从顶点开始建堆, 忽略最后一个}return;}int main （void）{std::vector<int> L = {49, 38, 65, 97, 76, 13, 27, 49};HeapSort（L）;for （std::size_t i=0; i<L.size（）; ++i） {std::cout << L[i] << " ";}std::cout << std::endl;return 0;}

输出:

97 76 65 49 49 38 27 13