堆排序

class HeapSort {
public:
	void sink(int a[],int n,int k) {
		while (k <= n / 2) {
			int j = 2 * k;                  //左孩子位置
			if (j + 1 <= n && a[j] < a[j + 1]) //如果有右孩子 比较哪个大
				j++;
			if (a[k] < a[j])                 //和更大的孩子比较
				swap(a[k], a[j]);          //如果子节点更大就交换
			else break;                   //否则退出
			k = j;                        //如果交换了就更改指针
		}
	}

	void swim(int a[],int n,int k) {
		while (k > 1 && a[k / 2] < a[k]) {
			swap(a[k / 2], a[k]);
			k = k / 2;
		}
	}

	void sort(int a[],int n) {
		for (int k = n / 2; k >= 1; k--)
			sink(a, n, k);
		while (n > 1) {
			swap(a[1], a[n]);
			n--;
			sink(a,n,1);
		}
	}
};

堆调整（大堆为例）