基础算法总结

基础算法总结

前段时间看了一部分《算法-第4版》，加深了我对排序、查找等基础算法的理解，在项目中更能够熟练的使用他们。所以这篇文章主要是按照我自己的理解对这些算法进行叙述，以方便日后浏览。文章可能有不严谨的地方，希望多多包涵。

排序

有很多操作都是基于有序序列的，所以排序算法可以说是基础中的基础，接下来就进行简单叙述。
排序算法的稳定性是值在有重复元素的排序操作后，等值有序元素的前后顺序不改变，否则即为不稳定。

冒泡排序

  • 中心思想： 对一个长度为N的无序数组进行N次冒泡，每次冒泡是将最大值冒泡到本次冒泡的末尾，每次从0开始到m结束（m=N-n，n表示第几次排序），依次两两比较。由于整个过程是从最大值到最小值依次冒泡到末尾，所以这个算法被形象地称为冒泡排序。
  • 时间复杂度： O(n^2)
  • 动图演示：

    选择排序

  • 中心思想：与冒泡排序类似，选择排序是每次选择最小或最大值到数组待排序序列最前方，知道所有地数据排序完毕，如果序列长度为N，那么总共需要进行N次选择最小或最大值地过程，并且每次选择都在剩余数据中进行两两比较。
  • 时间复杂度：O(n^2)
  • 动图演示：

    插入排序

  • 中心思想： 将数组分为两部分，前部分为已排序部分，后部分为未排序部分，每次操作是从未排序部分取第一个数插入到已排序部分的正确位置，插入过程是从已排序数组末尾到0，依次与每个索引的元素进行比较，当已排序元素比待插入元素大，则进行数据移位，否则将待插入数据放入当前index所指空间。
  • 时间复杂度：O(n^2)
  • 动图演示：

    希尔排序

  • 中心思想： Shell排序又叫减小增量排序，是对简单插入排序的改进，主要操作是依靠一个排序增量序列，这个序列从大到小递减，最终递减为1，如此能减少比较次数。按照增量序列的长度K，对整个序列进行K趟排序。如增量序列为[7, 4, 1]，则总共需要3趟排序：
  1. 第一趟：从index为0开始每次间隔6个元素，到index为6时结束，总共分为N/7个小序列；
  2. 第二趟：从index为0开始每次间隔3个元素，到index为4时结束，总共分为N/4个小序列；
  3. 第三趟：从index为0开始每次间隔0个元素，这一次即把所有元素排序完成。
  • 时间复杂度：O(n^1.3)
  • 动图演示：

    归并排序

  • 中心思想：将长度为N的待排序数组分成两部分，每部分长度为N/2，并对两部分分别二分，直到不能细分时，即长度为2时，对两个元素进行排序，然后对两组元素进行归并，即把两个有序数组归并为一个有序数组，依次类推直到归并到一个长度为N的数组，排序即结束。
  • 时间复杂度：O(nlog2n)
  • 动图演示：

    快速排序

  • 中心思想：选定未排序序列的第一个为基准值，并且依照该基准值进行分区，比基准值小的排在前面，比基准值大的排在后面，再对两部分分别进行分区操作，依次类推，直到无法分区，即只有1个元素，至此排序完成。
  • 时间复杂度：O(nlog2n)
  • 动图演示：

    堆排序

  • 中心思想：以优先队列为基础构造长度为N的优先队列，再每次将最大值取出与已经构造的优先队列中右下最末尾数据进行交换，再对剩余数据进行上浮和下沉操作，再取出最大值，依次类推，将所有数据排序完成。
  • 时间复杂度：O(nlog2n)
  • 动图演示：

  • 计数排序

  • 中心思想：
  • 时间复杂度：
  • 动图演示：

    桶排序

  • 中心思想：
  • 时间复杂度：
  • 动图演示：

    基数排序

  • 中心思想：
  • 时间复杂度：
  • 动图演示：
    ———————————————未完待续——————————————

    查找

    无序链表顺序查找

    有序数组二分查找

    二叉树查找

    红黑树

    散列表

    图

    广度优先搜索算法

    深度优先搜索算法

    字符串

    排序

    索引计数

    低位优先排序

    高位优先排序

    查找

    单词查找树

    三向单词查找树

    子串查找

    正则表达式

    数据压缩

参考： https://www.cnblogs.com/onepixel/articles/7674659.html