排序算法总结

知乎参考地址

最近在刷Leetcode过程中，部分题目需要手写排序算法。发现很多之前学习过的排序算法，均已经玩的差不多啦。特将常见的排序算法思想与算法实现总结如下：

最近在刷Leetcode（NO.399）过程中看到了并查集的概念，发现自己并不是很清楚其概念，故这里将相关概念总结如下：

堆排序实在数据结构中常见的排序算法，但许久未看已经忘得差不多啦。这里简单的将相关概念记录如下：

回朔法的思想：

回朔法的重要思想在于： 通过枚举法，对所有可能性进行遍历。 但是枚举的顺序是 一条路走到黑，发现黑之后，退一步，再向前尝试没走过的路。直到所有路都试过。因此回朔法可以简单的理解为： 走不通就退一步的方枚举法就叫回朔法。而这里回退点也叫做回朔点。

初次见到动态规划是在王道论坛划水的时候，见到时简直一脸懵逼。最近在刷Leetcode发现大量的题目建议采用动态规划的解法，遂将相关概念整理如下。

我自己对股票问题经常打怵，特将相关算法框架与相关题目解读总结如下：

前缀树的概念

参考地址

前缀树也称之为单词查找树，Trie树，是一种N叉树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

Leetcode讲解

在二维数组中涉及到大量计算某区域的算法题目，为了降低时间复杂度，对数组区域进行记忆是必不可少的，这也就提出了二维数组的前缀和（P）概念。

学习二叉树时，前序中序后序遍历方式是基础知识。最近再刷Leetcode时，发现很多遍历实现的基本本方式已经忘记了，这里将各种方式的原理与代码实现整理如下；

参考博客

第二次刷Leetcode_034题目时，涉及到二分查找左右边界时，又出现了算法理解不清楚的问题。发现第一次也并没有去总结，这里总结下。