堆排序算法，附图与C++代码


堆的意思就是上面的都比下面大，或者小。
举个例子，下图就是个最小堆，父节点都比子节点小。如果将其反过来，父节点都比子节点大，那就是最大堆。
如图，想象一下东西是怎么磊成堆的，就能理解这个名字的精妙了。
      1
    /   
  2     7
 /     / 
3  4  8  9
堆很容易就可以用数组表示，任意元素i，其子节点就是[2*i]，[2*i+1]，其父节点就是[j/2]，写起来很简单吧，也很容易理解。
堆排序的思想就是利用堆的这种父子节点大小关系的特性，来降低比较次数。
想象一下单循环淘汰赛，比如说欧洲冠军杯。先捉对厮杀，再一层一层往上走。堆排序就是这么做的。第一次从N中选出冠军。然后将冠军拿掉，剩下的N-1再选，以此计算，直到剩最后一个时，全部排序也就完成了。
举个例子：数组为：2, 5, 3, 2, 3, 0, 8, 1
得到初始状态如下图：
       2
     /   
    5     3
   /      / 
  2  3  0  8
 /
1
选出第一个冠军：
       8
     /   
    5     2
   /      / 
  2  3  0  3
 /
1
将冠军移到最后，然后，图也就变成
       1
     /   
    5     2
   /      / 
  2  3  0  3
8
继续选冠军：
       5
     /   
    1      3
   /      / 
  2  3  0  2
8
再将冠军移到树的最后：
       2
     /   
    1      3
   /      / 
  2  3  0  5
8
继续选冠军：
       3
     /   
    2      3
   /      /
  2  1  0  5
8
再将冠军移到树的最后：
       0
     /   
    2     3
   / 
  2  1  3  5
8
继续选冠军：
       3
     /   
    2     0
   / 
  2  1  3  5
8
再将冠军移到树的最后：
       1
     /   
    2     0
   /
  2  3  3  5
8
继续选冠军：
       2
     /   
    1     0
   /
  2  3  3  5
8
再将冠军移到树的最后：
       2
     /   
    1     0
  2  3  3  5
8
继续选冠军：
       2
     /   
    1     0
  2  3  3  5
8
再将冠军移到树的最后：
       0
     /
    1     2
  2  3  3  5
8
继续选冠军：
       1
     /
    0     2
  2  3  3  5
8
再将冠军移到树的最后：
       0
    1     2
  2  3  3  5
8
搞定啦！
0, 1, 2, 3, 3, 5, 8
代码如下：
view plaincopy to clipboardprint?
void FindMaxInHeap(int arr[], const int size) {   
    for (int j = size - 1; j > 0; --j) {   
        int parent = j / 2;   
        int child = j;   
        if (j < size - 1 && arr[j] < arr[j+1]) {   
            ++child;   
        }   
        if (arr[child] > arr[parent]) {   
            int tmp = arr[child];   
            arr[child] = arr[parent];   
            arr[parent] = tmp;   
        }   
    }   
}   
void HeapSort(int arr[], const int size) {   
    for (int j = size; j > 0; --j) {   
        FindMaxInHeap(arr, j);   
        int tmp = arr[0];   
        arr[0] = arr[j - 1];   
        arr[j - 1] = tmp;   
    }   
}   
void TestHeapSort() {   
    int arr[] = {2, 5, 3, 2, 3, 0, 8, 1};   
    int n = sizeof(arr) / sizeof(arr[0]);   
    HeapSort(arr, n);   
    for (int j = 0; j < n; ++j) {   
        cout << arr[j] << ", ";   
    }   
    cout << endl;   
}

补充：软件开发 , C++ ,