堆排序

       1.建堆， 依据数组和二叉树的原理，保证子节点小于祖先节点，开始于i=n/2-1，其孩子为2i+1,2i+2，然后i--做循环。在内部建堆时，要保证交换后的数值仍满足“子节点小于祖先节点”，需要进行递归操作。

       2.排序时，每次将数组的第一位最大值取出与数组的当前最后一位交换。交换后，针对数组的第一个元素进行建堆操作。

 

#include <iostream>

using namespace std;

#define cmp(a,b) a<b?a:b

const int len = 16;
int a[len];

void initArray() {
	for(int i=0;i<len;i++)
		a[i] = i + 1;
}

// 建堆的堆排序
void heapify(int idx, int max) {
	int left = 2*idx + 1;
	int right = 2*idx + 2;
	int largest;

	if(left < max && a[left] > a[idx]) {
		largest = left;
	} else {
		largest = idx;
	}

	if(right < max && a[right] > a[largest]) {
		largest = right;
	}

	if(largest != idx) {
		int temp;
		temp = a[largest];
		a[largest] = a[idx];
		a[idx] = temp;

		heapify(largest, max);
	}

}

// 建堆
void buildHeap(int n) {
	int i;
	for(i=n/2-1;i>=0;i--) {
		heapify(i, n);
	}
}

// 排序
void sort() {
	buildHeap(len);
	int i;
	int temp;
	for(i=len-1;i>=1;i--) {
		temp = a[0];
		a[0] = a[i];
		a[i] = temp;

		heapify(0, i);
		//buildHeap(i);
	}
}

int main() {
	// 初始化数组
	initArray();
	sort();

	for(int i=0;i<len;i++) {
		cout << a[i] << " ";
	}
	
	getchar();
	return 0;
}