常见的排序算法，复杂度

作者：小舞很执着 | 2024-07-17 16:20:01

踩

常见的排序算法，复杂度

稳定 / 非稳定排序：两个相等的数排序前后相对位置不变。
插入排序（希尔排序）：
- 每一趟将一个待排序记录，按其关键字的大小插入到已排好序的一组记录的适当位置上，直到所有待排序记录全部插入为止。稳定，O(n)，O(1)。
- 把记录按下标增量（模）分组，对每组进行直接插入排序，每次排序后减小增量，当增量减至 1 时排序完毕。不稳定，不知道（有个实验结论），O(1)。
冒泡排序：
- 比较相邻的元素，如果第一个比第二个大就进行交换，对每一对相邻元素做同样的工作。稳定，O(n)，O(1)。
选择排序：
- 每次在未排序序列中找到最小元素，和未排序序列的第一个元素交换位置，再在剩余未排序序列中重复该操作，直到所有元素排序完毕。不稳定，O(n)，O(1)。
桶排序：
- 将数组分到有限数量的桶里（比如按照十进制最高位，分到10个桶里），每个桶分别排序（可能使用别的排序算法，也可能递归桶排序），然后把排序好的桶连接起来。
- 稳定。桶数量 = 数据量时，O(N)，O(N)。桶数量 = 2，完全递归桶排序，O(NlogN)，O(N)。
归并排序：
- 将待排序序列分成两部分，先对两部分分别递归排序，然后进行合并。稳定，O(nlogn)，O(n)。
堆排序：
- 堆是一种完全二叉树，最大值堆：子节点均小于父节点，最小值堆：子节点均大于父节点。
- 插入：放在完全二叉树最后一点，一直往上升。
- 删除：取出根节点，最后一点升顶，往下降。
- 不稳定，O(nlogn)，O(1)（树状数组）。
快速排序：
- 随机选择一个基准元素，通过一趟遍历将要排序的数据分割成两部分，一部分全部小于等于基准元素，一部分全部大于等于基准元素，继续对两部分递归快排。不稳定，O(nlogn)，O(1)。
- 最优：每一次选基准元素都恰好选到中位数，⼆叉树的层数（logn）即为递归需要进⾏的次数，并且每轮递归结束时，都将⼆叉树遍历了⼀遍（n），O(nlogn)。
- 最差：数组完全倒序，每次都选到最大的作基准，O(n^2)。

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】