Algorithm4 十种排序

[TOC]

排序

排序时间复杂度中的 $log_x^n$ 中以x为底n的对数通常x是取2的。 详细计算:通过k-叉树的计算次数,可以得到,最底层想覆盖n个数,那么就要$k^{depth}=n$ 然后也就得到$depth=log_k^n$ 也就是要depth次搜索,才能从最上层搜到最下层,所以log的值是和k叉树是有关系的,如果k叉越大,那么搜到最底层的速度也就越快 height of a binary tree

暴力遍历:

  • 冒泡排序【稳定】:$O(n^2)$ 最大的往后冒泡,保证「每次提取最大」的,然后「放到最后」
  • 选择排序【不稳定】:$O(n^2)$ 「拿到合适的然后放置」选择出最值以及最值的索引,然后进行交换。
  • 插入排序三种:「拿到然后找合适的地方放置一个/多个」
    • 直接插入【稳定】:$O(n^2)$ 对每次拿到的数,从一端到另一端暴力查找,找到合适的位置插入进去
    • 折半插入【稳定】:$O(nlog_2^n)$ 在选择合适的位置的时候,会进行二分折半查找,找到合适位置插入进去
    • 希尔插入【不稳定】:$O(n^{1.3})\sim O(n^2)$ 更复杂的插入排序过程,三大步,首先对半分,两半一对一匹配进行插入排序;然后对半分的两类内部分别进行插入,然后对整体进行插入排序。

递归 二分与合并:$O(n*log_2^n)$

  • 快速排序【不稳定】:首先移动,然后「合理的分割」
  • 归并排序【稳定】:「分割」,然后「合理的合并」

递归 桶 多分与合并:

  • 计数排序:n个数n个桶,然后把n个桶再合并
  • 桶排序:n个数k个桶,k个桶各自进行排序,然后再把k个桶合并
  • 基数排序【稳定】:n个数10个桶,10个桶为首位/尾位的是个数字对应的数。
    • 思路一:先合并,然后再根据首位/尾位的下面一位接着入桶
    • 思路二:对每一个桶分别根据下一位再重新进小小桶,然后对小小桶进行合并,再对大桶进行合并

其他: $$ O(n*log_n2) $$

  • 锦标赛排序/堆排序【不稳定】:利用类似于堆/树的log2n的结构来提取最大/最小,然后放在首/尾。
    • 利用最小堆:递增排序
  • 利用最大堆:递减排序

归并排序

两个易错点:

1、递归完了回来将要排序的时候,两个范围注意,左边小于等于mid,右边小于等于r,然后右边的起点也是mid+1。

2、******递归

快速排序

题目链接:https://www.luogu.com.cn/problem/P1177

1、所有排序算法的函数形式都是可以写成sort_algorithm(int[] arr, int l,int r){}

2、找分块的标准数的部分快排的核心思想就是找一个数,来作为分块标准,而不是找一个分割的数的索引,因为索引的话,会随着swap()变换而导致本来已经确定的数变化。

3、分块的部分,可以通过前后遍历,碰到一对分别小于、大于的,直接swap()掉即可。但是会引发一个问题,就是如果碰到了一边刚好完全都是符合那个标准的,然后另一边存在不符合标准的,此时就需要把标准和不符合标准的换位置了。

4、递归的部分边界的设定问题,存在有刚好极端情况也就是分块的标准数刚好是最大或者最小的,那就不用再递归他了。所以要判断l < j或者i < r也就是排除了最大最小两种极端情况,其他的次大次小=>都要老老实实的把长度为2的给往下递归

void quicksort(int l, int r){
    int mid = a[(l+r)/2], i = l, j = r;
    do{
        while (a[i] < mid) i++;
        while (a[j] > mid) j--;
        if (i <= j) {swap(a[i], a[j]);i++;j--;}
    }while (i <= j);
    // recursion left and right
    if (l < j) quicksort(l, j);
    if (i < r) quicksort(i, r);
}
Posted on Feb 1, 2021