程序员

归并排序

基本思想 核心思想是“分治法”。 将序列看成nge有序的子序列,每个序列的长度为1,然后两两归并,得到n/2个长度为2或1的有序子序列,然后再两两归并······这样重复下去,直到得到一个长度为n的有序序列,这种排序方法叫做2-路归并算法。依次类推,还有3-路归并排序等等。 如何有效的将两个有序序列…

程序员

堆排序

数据结构堆 是一颗完全二叉树。完全二叉树:设二叉树的深度为h,除了第h层以外,前面的每一层的节点数都达到最大,并且第h层的叶子都集中在最左边。 所有非终端(有叶子)节点的值均不小于(或不大于)其左、右孩子的值。前者叫大顶堆,后者叫小顶堆。 堆排序思想 利用堆数据结构的堆顶肯定是最大值(或最小值),则…

大数据

排序算法总结(一) 堆排序

1 时间复杂度对比 排序算法时间复杂度总结.png 本节我们只关注堆排序的时间复杂度.首先, 从上图我们可以看到,堆排序是不稳定的. 排序算法的稳定性: 对于一组数,如果相同元素的相对位置在排序前后保持一致,则该算法是稳定的,否则是不稳定的. 其次, 堆排序的时间复杂度都是O(nlogn), 空间复…

大数据

lintcode 第十七、十八题 子集和带重复数字的子集

第十七题是给定一个不含重复数字的集合,返回其子集;十八题是给定一个可能有重复数字的集合,返回其子集。先来说没有重复数字的情况首先把空集合加进去,然后在循环里面进行递归调用,在进行递归时,将i的值加1,就可以排除前面已经加进去的数字,这道题可以和十五十六题进行比较,都属于深度优先搜索。代码如下: cl…