排序算法总结

主要对学习过的排序算法进行时间、空间复杂度上的一些整理。

算法名称	类别	最好	平均	最坏	空间复杂度	核心思想
1. 冒泡排序 (Bubble Sort)	交换排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	消除逆序对：通过重复遍历，比较并交换相邻的逆序元素，直到没有逆序对。
2. 选择排序 (Selection Sort)	选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	消除逆序对：每一轮从未排序部分选出最小（或最大）元素放到已排序序列末尾。
3. 插入排序 (Insertion Sort)	插入排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	消除逆序对：构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置插入。
4. 堆排序 (Heapsort)	选择排序	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(1)$	优先队列：利用堆结构（通常是大顶堆）的性质，每次弹出最高优先级的元素（根节点）归位。
5. 归并排序 (Mergesort)	归并排序	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(n)$	分治法：将序列递归分为子序列，排序后再合并。瓶颈在于需要额外的辅助空间。
6. 快速排序 (Quicksort)	交换排序	$O(n \log n)$	$O(n \log n)$	$O(n^2)$	$O(\log n)$	分治法：选取基准值，通过交换将数据分为两部分。
7. 桶排序 (Bucketsort)	分布排序	$O(n+k)$	$O(n+k)$	$O(n^2)$	$O(n+k)$	非比较排序：打破 $\Theta(n \log n)$ 限制。将数据分发到有限数量的桶里，桶内单独排序。
8. 基数排序 (Radixsort)	分布排序	$O(nk)$	$O(nk)$	$O(nk)$	$O(n+k)$	非比较排序：打破 $\Theta(n \log n)$ 限制。按照低位先排序收集，再按高位排序收集，以此类推。