Zu3zz/Learn_some_algorithm_and_data_structure

排序

• 选择排序(Selection Sort)复杂度 O(n^2)

  找到最小的元素然后与当前位置交换

• 插入排序(Insertion Sort)复杂度 O(n^2)

  找到合适的位置然后插入

• 改进的插入排序(取消了交换操作)

  将当前位置的元素先拿出 然后逐个与之前的元素比较 如果小于 就将之前的元素后移 在与前一位比较

• 冒泡排序(Bubble Sort)

• 希尔排序(Shell Sort)

• 归并排序(Merge Sort)复杂度 O(n*logn)

  先不断的二分 归并过程

• 归并排序自底向上版(Merge Sort Buttom Up)

  不先对数组进行二分 直接以 1、2、4 这样大小循环合并直至数组全部合并完成

• 快速排序(Quick Sort)

  先选中一个元素 然后找到它应该所在的位置 然后继续递归

  • 第一部分 partition

    先选中一个元素 然后找到它应该所在的位置 然后继续递归 如果此时 e > v，那么 e 直接加入到紫色的数组中
    如果此时 e < v, 那么直接将 e 与 j 所指向的位置交换即可 之后 j++ 最后所有元素分类完毕之后 将 l 与 j 所在位置的元素交换一下即可

• 快速排序存在的两点问题

  1. 对于近乎有序的数组,快速排序会退化到复杂度 O(n^2),此时解决办法就是随机选取一个初始值 然后与第一个需要定位的元素 l 交换 这样操作 快速排序的期望复杂度 EO(Nlogn)
  2. 对于一个 � 数量庞大但是所有元素都在一个很小区间的数组,快速 � 排序依旧会退化到复杂度 O(n^2),因为会导致大量的不平衡数组出现

     

• 此时 使用双路快排(hard):scream:

  主要在 partition 过程中进行了更加细化的操作

• 三路快排

  • 这是初始排序的情况

  

  • 此时是排序完毕的情况

  

堆(优先队列)

• 二叉堆

堆 是一个完全二叉树

排序算法总结

最大索引堆

• 基础 添加index用来记录当前索引堆每个元素所在的位置

• 优化 添加reverse�行用来存储索引对应index中的数

• reverse数组�more detail

• 二项堆
• 斐波那契堆