古剑奇谭3,实习期上高速怎么处罚,蔚县-白客消息,一个演员的自我修养

admin 2019-07-12 阅读:298

堆排序,一种就地算法,最坏状况O(nlogn)。

二叉堆

虽然完好二叉树的表明方式是树的方式,但它的存储实际上是数组。而且0索引处通常会用来寄存岗兵。

保护堆特性

节点的下沉:

原本三个元素上下次序是4、14、8,先将4取出,然后拿子节点作比较,将大的拿出来与4交流方位,最终完结4的下沉。

以上代码是存在右孩子的状况,假如不存在右孩子,而且需求下沉的节点小于左孩子:

至此,整个下沉操作完毕。

建堆

即从结尾开端第一个有子节点的父节点(非叶子节点)开端进行下沉操作。

堆排序

从建一个最大堆--->从小到大排序。先建堆、再排序。为什么是从小到大排序?能够这么了解:前半部分是一个最大堆,取出堆顶,此刻结尾天然变为空,正好用来保存这个最大的堆顶元素,因而到最终会从小到大排好序。

堆排序代码(感觉写的很乱):

def adjust(arr):
   # 首要需求构建最大堆(即从第一个非叶子结点(有子节点)开端下沉)
   # 由于选用岗兵思维,0索引处寄存岗兵,所以数组长度要-1再除以2
   start = int((arrlen-1)/2)
   for i in range(start,0,-1):
       arr[0] = arr[i]
       R = i*2+1
       # 当存在右孩子时:
       while R < arrlen:
           MAX = i
           if arr[MAX] < arr[R]:
               MAX = R
           if arr[MAX] < arr[R-1]:
               MAX = R-1
           if MAX == i:
               break
           arr[i] = arr[MAX]
           i = MAX
           R = 2*i+1
       # 假如不存在右孩子,而且需求下沉的节点小于左孩子
       if R == arrlen and arr[i] < arr[R-1]:
           arr[i] = arr[R-1]
           i = R-1
       arr[i] = arr[0]
   # 做完调整后交流第一个和最终一个元素    
   arr[1],arr[arrlen-1] = arr[arrlen-1],arr[1]
   return arr


if __name__ == "__main__":
   # 输入元素个数至少为两个
   input_list = [int(i) for i in input("input elements:").split(" ")]
   new_list = [0] + input_list
   global arrlen
   arrlen = len(new_list)
   while arrlen > 2:
       result = adjust(new_list)
       arrlen -= 1
   print(result)

上浮操作

将新元素放到结尾进行上浮。

上浮操作的伪代码:

Williams算法

思路:将元素逐一放入堆(堆的结尾方位)中,然后进行上浮。