最大堆的原理与实现
基本原理最大堆是一个二叉树，要求这个二叉树的父节点大于它的子节点，同时这个二叉树是一个完全二叉树，也就是说这个二叉树除了最底层之外的其它节点都应该被填满，最底层应该从左到右被填满。显然，最大堆的顶部节点的值是整个二叉树中最大的。我们使用数组来构建一个最大堆，使用数组构建一个二叉树最大堆存在如下性质。假设二叉树某节点在数组中的下标索引为index，则它的父节点在数组中的下标索引为parent = (index - 1) // 2，它的左子节点的下标索引为child_left = index * 2 + 1，右子节点的下标索引为child_right = index * 2 + 2。如果计算出来parent小于0或者child大于了数组最大值，就说明没有父节点或者子节点。代码实现接下来我们创建最大堆类，存储一..
更多常见排序算法的原理和实现
冒泡排序冒泡排序的原理很简单，就是每次都把当前无序序列中最大（或者最小）的元素移动到序列的开头（或者结尾），之后再对除该元素之外的剩余序列做同样的操作。当所有的元素都冒泡完毕之后，整个序列就会变得有序。冒泡排序的过程正如它的名字一般，每次都把序列中最大的元素移动到末尾（假设我们选择了这种规则），这种操作就好像水中的泡泡不断地从水中浮到水面一般。冒泡排序的实现如下，简单观察就可以知道它的时间复杂度为O(n2)123456def bubble_sort(arr): length = len(arr) for i in range(length - 1): for j in range(length - 1 - i): if arr[j] > arr[j +..
更多