排序算法总结

发表于 | 分类于 | 次

排序

  1. 基本有序的情况下：快排最慢，堆排最快。
  2. 选择排序的最坏和平均复杂度相同。 归并排序的也是一样的。
  3. 折半插入排序，是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。 所以，很明显比较的次数减少了
  4. 比较次数与初始元素顺序无关的排序算法（即最好、最坏情况的时间复杂度一样）
    选择排序O(n^2)
    堆排序O(nlogn)
    归并排序O(nlogn)
    基数排序O(tn)
  5. 元素的移动次数与关键字的初始排列次序无关的是：基数排序；
  6. 元素的比较次数与初始序列无关是：选择排序
  7. 算法的时间复杂度与初始序列无关的是：直接选择排序
  8. 对n个记录的线性表进行快速排序为减少算法的递归深度，每次分区后,先处理较短的部分
  9. 外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。外部排序最常用的算法是多路归并排序，即将原文件分解成多个能够一次性装入内存的部分，分别把每一部分调入内存完成排序。然后，对已经排序的子文件进行多路归并排序。
  10. 插入排序、选择排序、起泡排序原本时间复杂度是O(n2)，更换为链式存储后的时间复杂度还是O(n2)。希尔排序和堆排序都利用了顺序存储的随机访问特性，而链式存储不支持这种性质，所以时间复杂度会增加。
  11. 先序遍历：根左右；中序遍历：左根右；后序遍历：左右跟。
  12. 快排的阶段性排序结果的特点是，第i趟完成时，会有i个以上的数出现在它最终将要出现的位置，即它左边的数都比它小，它右边的数都比它大。
  13. 小根堆中最大的数一定是放在叶子节点上，堆本身是个完全二叉树，完全二叉树的叶子节点的位置大于[n/2]
  14. 递归算法改为非递归算法不是采用队列做辅助结构，而是栈；
  15. 影响时间复杂度的主要因素为比较的次数。
  16. 二叉排序树的主要用途是链式存储结构的二分查找，查找的最坏次数是树的高度，因此高度最小的二叉排序树是最佳的。
  17. 基数排序又称桶排序，它基于分治的思想，它将序列分为若干组，组与组之间是有序的（比如第一堆最大的元素也不会比第二堆最小的元素更大，诸如此类），因此可以把问题划分为若干个子问题进行并行处理。
  18. 二叉排序树的任一结点，左小右大。
  19. 对长度为n的线性表排序，在最坏情况下，比较次数除堆排序的比较次数是O(nlogn),其他都是n(n-1)/2。

字符串

  1. KMP算法时间复杂度为O(m+n)，空间复杂度为O(m)。
  2. 设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为匹配。

队列和栈

  1. 深度优先遍历DFS可以用栈实现；宽度优先遍历BFS用队列实现。
  2. 用链接方式存储的队列，在进行插入运算时，一般情况下，仅需修改队尾指针；但当队列为空时，插入元素时，队头和队尾指针都需修改。
  3. 有序表中所有元素以递增或递减方式排列，对数据之间的关系进行了描述，是一种逻辑结构。
  4. 循环队列的相关条件和公式：
    1. 队空条件：rear==front
    2. 队满条件：(rear+1) %QueueSIze==front，其中QueueSize为循环队列的最大长度
    3. 计算队列长度：（rear-front+QueueSize）%QueueSize
    4. 入队：（rear+1）%QueueSize
    5. 出队：（front+1）%QueueSize
  5. 输入受限 的 双端队列 是指元素只能从 队列 的一 端输入 ,但可以从 队列 的两端 输出；输出受限 的 双端队列 是指只有一端可以进行出队操作而从两端都可以进行入队操作的 队列。
  6. 广度优先用队列，深度优先用栈。
  7. 线性表可以分顺序存储和链式存储。
  8. 抓住front=tail时，队列可能空，也可能满！
  9. 循环队列插入时，队头指针不变，队尾指针后移一位。
  10. 所谓建初始堆意思是从这里开始调整。
  11. 一个中缀式到其他式子的转换方法：a+b*c-(d+e)
    第一步：按照运算符的优先级对所有的运算单位加括号： 
    式子变成拉：((a+(b*c))-(d+e))
    第二步：转换前缀与后缀表达式 
    前缀：把运算符号移动到对应的括号前面   
      则变成拉：-( +(a *(bc)) +(de))   
      把括号去掉：-+a*bc+de  前缀式子出现   
后缀：把运算符号移动到对应的括号后面   
      则变成拉：((a(bc)* )+ (de)+ )-   
      把括号去掉：abc*+de+-  后缀式子出现
  12. 先序遍历：根左右；中序遍历：左根右；后序遍历：左右根。
  13. 栈内存操作系统来分配，堆内存由程序员自己来分配。
  14. 递归过程转换为非递归过程，一般都要用栈来模拟这个过程调用.
  15. 选择排序，是每一次从未排序序列中找出一个最大或者最小的数，放到已排好序的数列最后。因此关键字比较次数跟数列的初始排列顺序是没有关系的.
  16. 初始数据集排列顺序与比较次数无关的有：归并，堆，选择排序。
  17. 插入排序、堆排序、冒泡排序、快速排序的比较：
    插入排序是依次比较找到自己的位置，有序的数组比较次数少；
    堆排序在数据有序时能够降低维护堆的性质时的交换次数；
    标准冒泡排序的比较次数是固定的，但是改进的冒泡排序可以对于有序的数组减少比较次数；
    快速排序在有序时复杂度最高达到O(n2)，完全无序时O(nlogn)；
  18. 元素的移动次数与关键字的初始排列次序无关的是：基数排序；
  19. 元素的比较次数与初始序列无关是：选择排序；
  20. 算法的时间复杂度与初始序列无关的是：直接选择排序；