常用排序算法介绍
冒泡排序（Bubble Sort）
-
实现思想： 重复地遍历要排序的数列，一次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
-
时间复杂度：
- 最好情况：O(N)。当输入数组已经是有序的时，只需要进行一趟遍历，比较N-1次，没有交换。
- 最坏情况：O(N^2)。当输入数组是逆序的时，需要进行N-1趟遍历，每趟遍历都需要进行多次比较和交换。
- 平均情况：O(N^2)。
-
复杂度计算说明：
- 外层循环需要执行N-1次（或N次）。
- 内层循环在最坏情况下，第一次执行N-1次比较，第二次N-2次，...，最后一次1次。总比较次数约为
(N-1 + 1) * (N-1) / 2，即N*(N-1)/2，所以是O(N^2)。交换次数类似。
-
稳定性：稳定。
选择排序（Selection Sort）
-
实现思想： 首先在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
-
时间复杂度：
- 最好情况、最坏情况、平均情况都是O(N^2)。
- 无论输入数据是什么样的，选择排序的比较次数都是固定的。
-
复杂度计算说明：
- 外层循环需要执行N-1次。
- 内层循环在第一次需要进行N-1次比较，第二次N-2次，...，最后一次1次。总比较次数是
N*(N-1)/2，所以是O(N^2)。 - 交换次数最多是N-1次。
-
稳定性：不稳定。（例如，序列
5 8 5 2 9，第一趟会将第一个5和2交换，导致两个5的相对顺序改变）
插入排序（Insertion Sort）
-
实现思想： 构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。它就像我们打扑克牌时，一张一张地将新牌插入到已有序的手牌中。
-
时间复杂度：
- 最好情况：O(N)。当输入数组已经是有序的时，每次插入都只需要比较1次，总共比较N-1次。
- 最坏情况：O(N^2)。当输入数组是逆序的时，第i个元素需要与前面i-1个元素都进行比较和移动。
- 平均情况：O(N^2)。
-
复杂度计算说明：
- 外层循环从第二个元素开始，遍历到最后一个元素，共N-1次。
- 内层循环在最坏情况下，第i个元素需要进行i-1次比较和移动。总操作次数约为
1 + 2 + ... + (N-1)，即N*(N-1)/2，所以是O(N^2)。
-
稳定性：稳定。
归并排序（Merge Sort）
-
实现思想： 采用分治（Divide and Conquer）策略。
- 分解（Divide）：将n个元素分成各含n/2个元素的子序列。
- 解决（Conquer）：用归并排序递归地排序两个子序列。
- 合并（Combine）：将两个已排序的子序列合并成一个最终的排序序列。
-
时间复杂度：
- 最好情况、最坏情况、平均情况都是O(N log N)。
-
复杂度计算说明：
- 分解过程：树的深度是
log N。 - 合并过程：每一层合并时，所有元素都会被遍历一次，所以每一层的合并操作的时间复杂度是O(N)。
- 总时间复杂度 = 树的深度 * 每层合并的复杂度 =
log N * O(N) = O(N log N)。
- 分解过程：树的深度是
-
稳定性：稳定。
- 空间复杂度：O(N)，因为合并过程需要一个临时的辅助数组。
快速排序（Quick Sort）
-
实现思想： 同样采用分治策略。
- 分解（Partition）：挑选一个元素作为“基准”（pivot），将数组分区（partition），使得所有比基准小的元素都在基准的左边，所有比基准大的元素都在基准的右边。
- 解决（Conquer）：递归地对基准左右两边的子数组进行快速排序。
- 合并（Combine）：因为子数组是原地排序的，所以不需要合并步骤。
-
时间复杂度：
- 最好情况：O(N log N)。当每次选取的基准都能将数组恰好平分为两半时。
- 最坏情况：O(N^2)。当输入数组已经有序或逆序，并且每次都选择第一个或最后一个元素作为基准时，导致每次分区都极不平衡（一边是0个元素，另一边是N-1个元素），递归树退化成链表。
- 平均情况：O(N log N)。通过随机选择基准等方法可以大概率避免最坏情况。
-
复杂度计算说明：
- 最好和平均情况：递归树的深度是
log N。每一层的分区操作都需要遍历该层的所有元素，复杂度是O(N)。总复杂度是O(N log N)。 - 最坏情况：递归树的深度是
N。分区操作的平均复杂度是O(N)，总复杂度是O(N^2)。
- 最好和平均情况：递归树的深度是
-
稳定性：不稳定。（在分区交换元素时，可能改变相等元素的相对顺序）
- 空间复杂度：O(log N) ~ O(N)，取决于递归深度。
堆排序（Heap Sort）
-
实现思想： 利用堆（Heap）这种数据结构。堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。
- 建堆：将无序序列构建成一个大顶堆（或小顶堆）。
- 排序：将堆顶元素（最大值或最小值）与末尾元素交换，然后将剩余的N-1个元素重新调整成一个堆，重复此过程，直到所有元素排序完毕。
-
时间复杂度：
- 最好情况、最坏情况、平均情况都是O(N log N)。
-
复杂度计算说明：
- 建堆过程：时间复杂度是O(N)。
- 调整堆过程：需要进行N-1次循环，每次循环都需要进行一次堆顶元素下沉的调整，这个调整操作的时间复杂度是O(log N)（与堆的高度相关）。
- 总时间复杂度 = O(N) + (N-1) * O(log N) =
O(N log N)。
-
稳定性：不稳定。
- 空间复杂度：O(1)，因为是原地排序。
| 排序算法 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(N^2) | O(N) | O(N^2) | O(1) | 稳定 |
| 选择排序 | O(N^2) | O(N^2) | O(N^2) | O(1) | 不稳定 |
| 插入排序 | O(N^2) | O(N) | O(N^2) | O(1) | 稳定 |
| 归并排序 | O(N log N) | O(N log N) | O(N log N) | O(N) | 稳定 |
| 快速排序 | O(N log N) | O(N log N) | O(N^2) | O(log N)~O(N) | 不稳定 |
| 堆排序 | O(N log N) | O(N log N) | O(N log N) | O(1) | 不稳定 |