#include "stdafx.h"#include <iostream>using namespace std;template<typename T>void adjust(T* arr,int sign,int len){ T temp = arr[sign]; //每一次循环都更新该父节点为根的完全二叉树最大堆 for (int i = sign * 2 + 1; i < len; i = i * 2 + 1){ if (i + 1 < len && arr[i + 1] > arr[i]) i++; //判断子节点 大于父节点 if (arr[i] > temp){ arr[sign] = arr[i]; sign = i; } } arr[sign] = temp;}template<typename T>void swap(T* arr, int x, int y){ T temp = arr[x]; arr[x] = arr[y]; arr[y] = temp;}template<typename T>void sort(T* arr,int length){ //1.从所有非叶子节点 构建初始大顶堆 for (int i = length / 2 - 1; i >= 0; i--){ adjust(arr, i, length); } // for (int i = length - 1; i; i--){ //2.交换最大堆 和 相对的最后一个元素 swap(arr, i, 0); //3.重新调整堆结构 adjust(arr, 0, i); }}template<typename T>void print(const T* ar,int len){ for (int j = 0; j < len; j++){ cout << j << " : " << ar[j] << endl; }}int _tmain(int argc, _TCHAR* argv[]){ int arr[] = { 0,2,1,4,3,6,8,9,7,5}; sort(arr, 10); print(arr, 10); getchar(); return 0;}