好理解的堆排序

 1 #include <iostream>
 2 using namespace std;
 3 
 4 void swap(int &a, int &b){
 5     int tmp = a;
 6     a = b;
 7     b = tmp;
 8 }
 9 
10 int findmax(int a[],int lenth,int i){
11     //找到第i个节点所代表的子树中的最大值
12     if(2*(i) >= lenth) return a[i];
13     int left, right,max;
14     int rightmax,leftmax;
15     rightmax = leftmax = max =0;
16     right = 2*i+1;
17     left = 2*i;
18     if(i == 0){
19         right = 2;
20         left = 1;
21     }
22     leftmax = findmax(a,lenth,left);
23     if(right < lenth){
24         rightmax = findmax(a,lenth,right);
25     }
26     if(leftmax > rightmax && leftmax > a[i])swap(a[i],a[left]);
27     if(rightmax > leftmax && rightmax > a[i])swap(a[i],a[right]);
28     return a[i];
29 }
30 
31 int* heapSort(int a[], int lenth){     
32     int max;
33     for(int i = 0; i < lenth; i++){
34         max = findmax(a, lenth-i, 0);
35         swap(a[0], a[lenth-i-1]);
36     }
37     return a;
38 }