8.堆排序

1.堆排序基本介绍：

1)堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。
2)堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆,注意:没有要求结点的左孩子的值和右孩子的值的大小关系。
3)每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆
4)大顶堆举例说明

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)