堆排序

堆排序

""" 堆排序： 堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。 堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。 堆排序可以说是一种利用堆的概念来排序的选择排序。 大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] 根节点大于两个子节点的值 小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] 根节点小于两个子节点的值 堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。 --> 有两个构造堆的过程：一个是初始数组构造成堆（不断从后面插入），另一个是堆顶与末尾元素互换后重新构造堆（从头向下比较） 将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。 如此反复执行，便能得到一个有序序列了 1.首先将待排序的数组构造成一个大根堆，此时，整个数组的最大值就是堆结构的顶端 2.将顶端的数与末尾的数交换，此时，末尾的数为最大值，剩余待排序数组个数为n-1 3.将剩余的n-1个数再构造成大根堆，再将顶端数与n-1位置的数交换，如此反复执行，直到只剩下一个元素为止，便能得到有序数组 """ # 将初始数组构造成大根堆（通过新插入的数上升） def heapInsert(arr): """将待排序数组构造成一个大根堆，每次插入新的数据的时候，都与它的父节点进行比较， 如果比父节点的值大，则进行交换，然后继续与新的父节点进行比较，直到小于等于父节点，或者到达顶端； 如果比父节点小，则插入就可以了 """ for i in range(len(arr)): # 遍历数组 currentIndex = i # 记录当前索引 # 计算父节点 fatherIdx = int((currentIndex - 1) / 2) # 当前节点与父节点的值进行比较 while arr[currentIndex] > arr[fatherIdx]: # 当前值比父节点大 # 进行交换 arr[currentIndex],arr[fatherIdx] = arr[fatherIdx],arr[currentIndex] # 更改当前的索引 currentIndex = fatherIdx # 重新计算父节点 fatherIdx = int((currentIndex - 1) / 2) # 直到当前节点到达顶端或者比父节点小，插入下一个 # 固定最大值，将剩余的数再次构造成大根堆,这属于一个循环操作，可以使用递归实现，直到只剩下一个元素结束 def heapify(arr,index,size): """将顶端的最大值与数组末尾的数交换，重新构造大根堆，通过顶端的数下降来重新构造""" # 计算当前index的左右子节点，index总是从根节点0开始 left = 2 * index + 1 right = 2 * index + 2 while left < size: # 当存在左孩子的时候，可以进行重新构造 # 拿到子节点中较大值的索引 largeIdx = 0 if arr[left] < arr[right] and right < size: # 右孩子存在并且右孩子大于左孩子，右子节点的索引值不能超过数组长度size（说明右孩子存在） largeIdx = right else: # 没有右孩子或者左孩子值较大 largeIdx = left # 如果当前父节点的值比较大孩子节点大，当前父节点，说明只有当前这个父节点的子树发生了变化 if arr[index] > arr[largeIdx]: # 当父节点已经是最大，说明已经构成大根堆 break else: # 继续修改当前父节点的子树 # 如果父节点的值比孩子节点小，进行交换 arr[index],arr[largeIdx] = arr[largeIdx],arr[index] # 更改父节点的索引指向 index = largeIdx # 继续与新的子节点进行比较 left = 2 * index + 1 right = 2 * index + 2 # 进行堆排序 def heapSort(arr): # 构造大根堆 heapInsert(arr) size = len(arr) # 固定最大值，再次构造大根堆 while size > 1: arr[0],arr[size-1] = arr[size - 1],arr[0] # 最大值与末尾元素交换 size = size - 1 # 元素长度少了最大值 heapify(arr,0,size) # 重新构造大根堆 return arr if __name__ == '__main__': a = [1,5,7,4,12,36,48,1,2,4,78,89,6,100] print(heapSort(a))