#SortingAlgorithms
Review
- 2021/02/22
- 2024-09-08 08:08
[!Summary] 经典排序算法
- 冒泡排序
- 选择排序
- 插入排序
- 希尔排序
- 归并排序
- 快速排序
- 堆排序
- 计数排序
- 桶排序
- 基数排序
- 快排优化
- 拓扑排序
一、Introduction #
稳定排序：值相同的元素，排序后顺序不变 不稳定排序：值相同的元素，排序后顺序变了
| Name | Best | Average | Worst | Memory | Stable | Comments |
|---|---|---|---|---|---|---|
| Bubble sort | n | $n²$ | n² | 1 | #Stable | |
| Insertion sort | n | n² | n² | 1 | #Stable | |
| Shell sort | n log(n) | depends on gap sequence | n (log(n))2 | 1 | #No-Stable | |
| Selection sort | n² | n² | n² | 1 | #No-Stable | |
| Merge sort | n log(n) | n log(n) | n log(n) | n | #Stable | |
| Quick sort | n log(n) | n log(n) | n² | log(n) | #No-Stable | Quicksort is usually done in-place with O(log(n)) stack space |
| Heap sort | n log(n) | n log(n) | n log(n) | 1 | #No-Stable | |
| Counting sort | n + r | n + r | n + r | n + r | #Stable | r - biggest number in array |
| Radix sort | n * k | n * k | n * k | n + k | #Stable | k - length of longest key |
总结 #
时间复杂度 O($n^2$) 的算法
- 冒泡排序
- 选择排序 #No-Stable
- 插入排序
- 希尔排序 #No-Stable
时间复杂度 O($nlogn$) 的排序算法
- 快速排序 #No-Stable
- 归并排序
- 堆排序 #No-Stable
时间复杂度为线性的排序算法
- 计数排序
- 桶排序
- 基数排序
插入排序的时间复杂度是 O($n^2$)，其中 n 是链表的长度。时间复杂度是 O($nlogn$) 的排序算法包括归并排序、堆排序和快速排序（快速排序的最差时间复杂度是 O($n^2$)），其中最适合链表的排序算法是归并排序。
二、详细介绍 #
2.1、冒泡排序 #
原理：反复遍历数组，每次比较相邻的两个元素，如果顺序错误就交换它们。 优点：实现简单。 缺点：效率较低，时间复杂度为O($n^2$)。
冒泡排序（Bubble sort）优化 #
- isSorted
- sortBorder
- 鸡尾酒排序：第一轮从左到右，第二轮从右到左，第三轮从左到右。。。主要应用于大部分有序的列表，能减少排序回合数
2.2、选择排序 #
- 原理：每次找到未排序部分中的最小（或最大）元素，将其放到已排序部分的末尾。
- 优点：数据移动次数较少。
- 缺点：时间复杂度也是O($n^2$)。
2.3、插入排序 #
- 原理：将一个待排序的元素，按其大小插入到一个已经排好序的有序数列中，从而得到一个新的、个数加1的有序数列。
- 优点：对于部分有序的数组效率较高。
- 缺点：平均时间复杂度为O($n^2$)。
2.4、希尔排序 #
- 原理：插入排序的改进版，通过将数组分成多个子数组，对每个子数组进行插入排序，然后逐渐减小间隔重新分组，直到整个数组有序。
- 优点：比插入排序效率高。
- 缺点：时间复杂度分析比较复杂，取决于增量序列的选择。
2.5、归并排序 #
- 原理：将待排序序列分成若干个子序列，每个子序列是有序的。然后将这些子序列两两合并成新的有序子序列，直到合并成一个大的有序序列。
- 优点：稳定排序，时间复杂度为$O(nlogn)$。
- 缺点：需要额外的空间。
2.6、快速排序 #
- 原理：通过一趟排序将待排序列分割成两个子序列，其中一个子序列中所有元素均比另一个子序列中的所有元素小。然后对这两个子序列分别进行快速排序，整个排序过程可以递归进行，直到每个子序列只有一个元素或者为空。
- 优点：平均时间复杂度为O($nlogn$)，是常用的排序算法。
- 缺点：不稳定排序，最坏情况（不平衡）时间复杂度为O($n^2$)。
partition的选择可以优化：
- 选择最右元素
- 选择最左元素
- 选择中间元素
- 选择随机元素
快排优化 #
- 双路快速排序：双路快速排序算法是随机化快速排序的改进版本，partition 过程使用两个索引值（i、j）用来遍历数组，将 <v 的元素放在索引i所指向位置的左边，而将 >v 的元素放在索引j所指向位置的右边，v 代表标定值。
- 三路快速排序：
2.7、堆排序 #
- 原理：将待排序序列构造成一个大顶堆或小顶堆，每次取出堆顶最大的（或最小的）元素，然后调整堆，使其仍然是一个堆，直到堆为空。
- 优点：时间复杂度为O($nlogn$)。
- 缺点：不稳定排序。
2.8、计数排序 #
- 原理：假设输入的元素都是非负整数，且知道输入元素的范围。通过一个辅助数组，计算每个输入元素的个数，然后根据计数数组来重构输出数组。
- 优点：时间复杂度为O(n+k)，其中k是输入元素的范围。
- 缺点：空间复杂度为O(k)，适用于数据范围较小的场景。
2.9、桶排序 #
- 原理：将数据分到多个桶中，每个桶再分别排序，最后将各个桶中的数据依次取出，得到有序的序列。
- 优点：时间复杂度可以达到O(n)，适用于数据分布比较均匀的情况。
- 缺点：需要额外的空间。
2.10、基数排序 #
- 原理：按照低位优先（或高位优先）的原则，将整数按个位、十位、百位…进行分别排序。
- 优点：稳定排序，时间复杂度为O($d*n$)，其中d是数字的位数。
- 缺点：适用于整数排序。