Python 面试题 - 堆排序 & 演算过程
今天头给我份python招聘的笔试题，让我看看难度如何？
最后编程大题是： 请使用python实现整数数组的推排序？
由于过于一直对于此排序很触头，如何用python实现让我有些头疼，于是度娘理清了下概念，开始自己实现，并附上推演过程。
具体概念请参考：http://blog.csdn.net/v_july_v/article/details/6198644
maxHeap(array,largest,heapSize) #即 最大值的index
1. 条件：index = len(arr)/2 值为3
leftChild: 3*2+1=7 rightChild: 3*2+2=8 此时都大于arrSize(heapSize) Pass
2. 条件: 2
leftChild: 2*2+1=5 rightChild: 2*2+2=6 此时最大值67[6]，与7[2] 交换。
此时数组变为：1[0] 2[1] 67[2] 4[3] 34[4] 25[5] 7[6]
2.1 子条件： 6
leftChild: 6*2+1=13 rightChild: 6*2+2=14 此时都大于arrSize(heapSize) 递归回归
3. 条件： 1
leftChild: 1*2+1=3 rightChild: 1*2+2=4 此时最大值34[4]，与2[1]交换
此时数组变为：1[0] 34[1] 67[2] 4[3] 2[4] 25[5] 7[6]
3.1 子条件：4
leftChild: 4*2+1=9 rightChild: 4*2+2=10 此时都大于arrSize(heapSize) 递归回归
4. 条件：0
leftChild: 0*2+1=1 rightChild: 0*2+2=2 此时最大值67[2]，与1[0]交换
此时数组变为： 67[0] 34[1] 1[2] 4[3] 2[4] 25[5] 7[6]
4..1 子条件: 2
leftChild: 2*2+1=5 rightChild: 2*2+2=6 此时最大值25[5]， 与1[2]交换
此时数组变为： 67[0] 34[1] 25[2] 4[3] 2[4] 1[5] 7[6]
4.2 子条件：5
leftChild: 5*2+1=11 rightChild: 5*2+2=12 此时都大于arrSize(heapSize) 递归回归
初始堆为：67[0] 34[1] 25[2] 4[3] 2[4] 1[5] 7[6]
树形展示为：
67[0]
/ \
34[1] 25[2]
/ \ / \
4[3] 2[4] 1[5] 7[6]
C 堆排序：
注意： 条件一直是无序堆的0
1. 交换大堆根头和最后的一个元素。
交换67[0]与7[6]，并将67[0]从无序堆中取出，此时无序堆: 7[0] 34[1] 25[2] 4[3] 2[4] 1[5]
根据条件 0 来整理无序堆(逻辑同上): 34[0] 7[1] 25[2] 4[3] 2[4] 1[5]
2. 交换34[0]与1[5]，并将34[0]从无序堆中取出，此时无序堆: 1[0] 7[1] 25[2] 4[3] 2[4]
根据条件 0 来整理无序堆为：25[0] 7[1] 1[2] 4[3] 2[4]
3. 重复1和2
最后无序堆中的元素全部取出，并组成堆排序的最后结果。
[1, 2, 4, 7, 25, 34, 67]
