1.堆排序基本介绍：
1)堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。
2)堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆,注意:没有要求结点的左孩子的值和右孩子的值的大小关系。
3)每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆
4)大顶堆举例说明
5)小顶堆举例说明
6)一般升序采用大顶堆，降序采用小顶堆.
可以看出对小顶堆来说：
设当前元素在数组中以R[i]表示，那么：
它的左孩子结点是：R[2i+1];
它的右孩子结点是：R[2i+2];
它的父结点是：R[(i-1)/2];
R[i] <= R[2*i+1] 且 R[i] <= R[2i+2]。
2.堆排序基本思想
堆排序的基本思想是：
1)将待排序序列构造成一个大顶堆
2)此时，整个序列的最大值就是堆顶的根节点，将其与末尾元素进行交换，此时末尾就为最大值。
3)然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。
可以看到在构建大顶堆的过程中，元素的个数逐渐减少，最后就得到一个有序序列了.
3.堆排序步骤图解说明:
针对无序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 }：
构造大顶堆示意图
堆排序示意图
3.代码实现
class AdjustHeap():
#1.将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆，这里是大顶堆
def adjust(self,arr,star,length):
self.arr = arr
self.length = length
self.star = star
#先取出当前元素的值，保存在临时变量
self.temp = self.arr[self.star]
#开始调整
#k=2*self.star+1 k是i结点的左子结点
k = 2*self.star+1
while (k < self.length):
#本题错点： 这里要加上k+1<self.length 防止当k+1<self.length 的时候还进行self.arr[k] < self.arr[k+1]
#这个比较导致最后结果不对
#这里是为了 如果左子结点的值小于右子结点的值 那么k指向右子结点
if k+1<self.length and self.arr[k] < self.arr[k+1]:
k = k+1
#如果子结点大于父结点，把较大的值赋给当前结点，再让self.star指向k,继续循环比较
if self.arr[k] > self.arr[self.star]:
#交换的技巧，老是没记住
self.arr[self.star] = self.arr[k]
self.star = k
else:
#这里能直接break，因为这个程序满足 从下往上，从左往右构成顶堆。
#这里要分清楚，如果是在构成顶堆的一次循环中，是从上面的子树往下面的子树进行比较的，那从下往上构成顶堆从何而来呢？
#是因为这里是下面的子树已经满足了顶堆了，再去加入上面的结点，这个是从下往上
#那么这里如果不需要换了，那么就保证这已经就是个顶堆了 于是可以直接break
break
#当for循环结束后，我们已经将以star为父结点的树的最大值，放在了最顶(局部)，然后要将一开始的值放到 本来是最大值的位置，完成交换
self.arr[k] = self.temp
#这里其实是for 循环摘出来了，for(intk=i*2+1;k<lenght;k=k*2+1) 第三个表达式，完成循环比较的动作
k = 2*self.star+1
return self.arr
arr = [4,6,8,5,9]
len = len(arr)
adj = AdjustHeap()
for i in range(int(len/2)-1,-1,-1):
arr = adj.adjust(arr,i,len)
#这里只需要进行4次排序，因为5个数只要4次就够了
for j in range(len-1,0,-1):
print("步骤1:",arr)
#2.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
arr[0],arr[j] = arr[j],arr[0]
print("步骤2:",arr)
#3.3).重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
arr = adj.adjust(arr,0,j)
print("步骤3:",arr)
print()
print(arr)
