【笔记/模板】排序算法
1. 冒泡排序
排序原理:
每次将未确定部分的相邻两个值对比,设为,如果,则对这两个值进行交换,可以使用swap
来快速对两个值进行交换。
那么,这样一轮交换下去,第一个数就可以确定是最小的了。以此类推,直到所有值都被确定,就得出最终排好序的数列了。
时间复杂度:
核心模板代码如下:
1 | int n,a[100001]; |
2. 桶排序
排序原理:
桶排序的原理很简单,就是定义一个数组为桶,然后每个桶代表一个数字,每输入一个数就将这个数对应的桶加上 (比如说 ,它所对应的桶下标就是 ),最后扫描桶,因为题目要求是从小到大排序,所以就直接正序扫描即可,只要桶里有值就输出。
这种排序的速度比较快,但是缺点是数值如果数的范围十分大,需要定义一个大的桶,这样会 MLE。
时间复杂度:( 为待排序数据值域)
核心模板代码如下:
1 | const int N = 1e8 + 9; |
3. 快速排序
排序原理:
我们设待排序的序列为一个长度为 的序列。
快速排序的具体原理如下:
首先,在 中随机选择一个数,之后我们进行如下操作:
如果 或 ,此时根本无需排序,直接退出;
定义三个新的序列 , , ;
在中随机选择一个数 ;
遍历整个序列 ,将比 小的放在 内,比 大的放在 内,和 相等的放在 内;
将 , 按如上过程继续排序。
序列中的数因为都相等所以不必排序。
时间复杂度:
核心模板代码如下:
1 | void quicksort(int a[],int l,int r){ |
4. 归并排序
排序原理:
归并排序用的是分治思想,分为三大步:
-
将个元素分成两个含有个元素的子序列。
-
解决:用合并排序法对两个子序列递归来排序。
-
合并:合并两个已排序的子序列来得到最终的排序结果。
时间复杂度:
两种实现方法:
-
迭代法
① 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列。
② 设定两个指针,最初位置分别为两个已经排序序列的起始位置。
③ 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置。
④ 重复步骤③直到某一指针到达序列尾。
⑤ 将另一序列剩下的所有元素直接复制到合并序列尾。
-
递归法
① 将序列每相邻两个数字进行归并操作,形成$\left \lfloor \frac{n}{2} \right \rfloor \left \lfloor \frac{n}{4} \right \rfloor $个序列,每个序列包含四个元素。
③ 重复步骤②,直到所有元素排序完毕。
核心模板代码如下:
1 | void mergesort(int l, int r, int a[]) |