Algorithm4 十种排序

[TOC]

排序

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

暴力遍历：

• 冒泡排序【稳定】：$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);
}