flash布局网站/nba最新交易

堆排分析:
        本质是利用完全二叉树的性质,将待排序的数组按照二叉树层序遍历的顺序进行处理,例如数组大小为N=10: 
        int array={1, 9, 2, 6, 3, 5, 4, 7, 8, 0};
用二叉树层序遍历得到:
               1
          /            \
        9              2 
     /       \       /     \ 
   6         3      5       4
  /   \     /
 7   8  0  
        我们从上到下按照数组的索引, 将根节点编号为1, 后面以此类推. 按照完全二叉树的性质, 只有索引编号为N/2节点和其之前的节点才有子节点, 并且编号为k的节点(k取[1 ~ N/2])的左子节点的索引为2k, 右子节点索引2k+1. 
        所以我们从第N/2个节点开始处理, 这里是10/2=5也就是array[4], 如果发现当前节点array[4]的子节点中有比当前节点大的节点, 则选两个子节点最大的那个节点与当前节点交换我们称为一次"上浮". 
        重复该方法依次上浮处理索引N/2到索引1的所有节点, 我们将这棵树称为"有序堆", 显然数组中的最大值将位于根节点. 并且, 所有以当前节点为根节点构成的子完全二叉树(子堆)也是有序堆(从当前节点到叶子节点的任意路径都是有序的)
               9
          /          \
        8              5 
     /        \      /       \ 
   7          3   2            4
  /   \      /
1    6     0    
此时数组变为:
        array={9, 8, 5, 7, 3, 2, 4, 1, 6, 0}
        现在我们将root节点也就是对应数组array[0]的值与最后元素array[N-1]交换,针对新的 array[0] ~ array[N-2], 继续使用上浮处理得到有序堆, 然后将新有序堆的根节点(最大值)与array[N-2]交换, 以此类推直到array[0] 与array[N-N]也就是自身交换时停止, 至此整个数组排序完毕.

整个过程时间复杂度小于 2N*lgN + 2N, 空间复杂度为 1.

示例：

/*************************************************************************> File Name: heap_sort.h> Author: XXDK> Email: v.manstein@qq.com > Created Time: Fri 29 Sep 2017 03:50:33 PM CST************************************************************************/#ifndef _HEAP_SORT_H
#define _HEAP_SORT_H#include <vector>
#include <iostream>using std::vector;
using std::cout; 
using std::endl; template <typename T>
class HeapSort
{
private:unsigned len;vector<T> array;
public:HeapSort(vector<T> _array, unsigned _len) {for (unsigned i = 0; i < _len; ++i) {array.push_back(_array[i]);}this->len = _len;}/* * max key swim to top.** 1. A N node complete binary tree height: lgN.* 2. The relationship between two adjacent layers is double.* 3. Set The root node's index as 1, only [1 ~ N/2] indexes node has child. ** In a heap, the parent of the node in position [k] is in position [k/2] and,* conversely, the two children of the node in position [k] are in positions * [2k] and [2k+1]. [k] is array indices.** parameter:*     @a	 -- heap array*     @start -- sink start position*     @end   -- sink end position */void maxKeySwim(vector<T>& array, int start, int end){int cnp = start;			// current node positionint lnp = 2*cnp + 1;		// left child position int tmp = array[cnp];		// current node key (array element value)cout << "[ " << start << " ]"<< " ~ " << "[ " << end << " ]"<< endl;for (; lnp <= end; cnp=lnp,lnp=2*lnp + 1) {// "lnp" is left child index, "lnp+1" is right child index.if (lnp < end && array[lnp] < array[lnp+1])lnp++;			// choice the larger one from the two child.if (tmp >=array[lnp])break;			// sink completeelse {				// sink min to child layer(exchange with the larger child)array[cnp] = array[lnp];array[lnp] = tmp;}printArray();}}void heapSort() {int i, tmp;// k <=> 2k ~ 2k + 1;// Coding this process is straightforward// when you keep in mind that the children of// the node at position k in a heap is at positions 2k and 2k+1.// Get some ordered subheaps after this "for" process.// 1. construct heap.cout << "------------construct heap." << endl;for (i = len/2 - 1; i >= 0; i--)maxKeySwim(array, i, len-1);// 2. Adjust the order of sequence.(analogy with insertion sort)cout << "------------adjust the order." << endl;for (i = len - 1; i > 0; i--){// exchange a[0](heap btree's root) with a[i], now a[i] is the max key in a[0...i].cout << "exchange a[0]=" << array[0] << " and a[" << i << "]=" << array[i] << endl;tmp = array[0];array[0] = array[i];array[i] = tmp;// adjust a[0...i-1], keep valid property of the heap(a[0...i-1]).printArray();cout << "------------construct heap." << endl;maxKeySwim(array, 0, i-1);}}void printArray(){for (int i=0; i<len; i++)cout << array[i] << " ";cout << endl;}
};
#endif // _HEAP_SORT_H

/*************************************************************************> File Name: heap_sort.cpp> Author: XXDK> Email: v.manstein@qq.com > Created Time: Fri 29 Sep 2017 04:12:01 PM CST************************************************************************/#include "heap_sort.h"int main()
{int a[] = {12,3,9,4,7,11,6,14,10,5,8,0,1,2,13};int ilen = (sizeof(a)) / (sizeof(a[0]));vector<int> testData;for (unsigned i = 0; i<ilen; i++) {testData.push_back(a[i]);}HeapSort<int> test(testData, ilen);cout << "===============================================" << endl;cout << "orignal order: " << endl;test.printArray();cout << "===============================================" << endl;test.heapSort();cout << "===============================================" << endl;cout << "ascend order:  " << endl;test.printArray();cout << "===============================================" << endl;return 0;}

The end！