算法相关

• 快速排序 (Quick Sort)
  • 通过一趟排序将待排序记录分隔成独立的两部分；
  • 其中一部分记录的关键字均比另一部分记录的关键字小；
  • 则可分别对两部分记录继续进行行行排序，以达到整个排序有序的目的。
  • 不稳定排序，最优（nlog2n），最差（n2）
• 归并排序
  • 分 - 治 思想
  • 稳定排序，nlog2n
• 冒泡排序
  • 两两比较
  • 稳定排序，最好n，最差n2
• 堆排序
  • 二叉树， 分大顶堆、小顶堆
  • 属于选择排序，不稳定排序，nlog2n
  • 映射到数组后
    • 大顶堆 -> arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
    • 小顶堆 -> arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
  • 将无序序列构建成一个堆，根据升序降序需求选择大顶堆或者小顶堆
  • 将堆顶元素与末尾元素交换，将最大元素沉到数组末端
  • 重新构造结构，使其满足堆定义，然后继续交换堆顶元素和末尾元素，反复执行调整+交换步骤，直到整个序列有序
• 选择排序
  • 不稳定排序， n2
• 二分搜索法
• 插入排序
• shell排序

动态规划算法使用范围的两个限制：
①构成原问题解的子问题的解，与该原问题的解 正相关；
②构成原问题解的各个子问题的解之间，要么互不影响，要么正相关。