排序算法一览表

相关概念：
稳定： 如果 a 原本在 b 前面，而 a=b，排序之后 a 仍然在 b 的前面
不稳定：如果 a 原本在 b 前面，而 a=b，排序之后 a 可能会出现在 b 的后面
时间复杂度：对排序数据的总的操作次数。反映当 n 变化时，操作次数呈现什么规律。
空间复杂度：指算法在计算机内执行时所需存储空间的度量，它也是数据规模 n 的函数。
时间复杂度排序：O(1) > O(logn) > O(n) > O(nlogn) > O(n²) > O(n³) > O(2ⁿ) > O(n!)

类别	算法名称	英文名称	时间复杂度			空间复杂度	稳定性
类别	算法名称	英文名称	平均情况	最好情况	最坏情况	空间复杂度	稳定性
插入排序	直接插入	Insertion Sort	O(n²)	O(n)	O(n²)	O(1)	稳定
插入排序	希尔排序	Shell Sort	O(n(㏒₂n)²)	O(n㏒₂n)	O(n(㏒₂n)²)	O(1)	不稳定
选择排序	直接选择	Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	不稳定
选择排序	堆排序	Heapsort	O(n㏒₂n)	O(n㏒₂n)	O(n㏒₂n)	O(1)	不稳定
选择排序	树排序	Tree Sort	O(n㏒₂n)	O(n㏒₂n)	O(n²)	O(n)	不稳定
交换排序	冒泡排序	Bubble Sort	O(n²)	O(n)	O(n²)	O(1)	稳定
交换排序	快速排序	Quicksort	O(n㏒₂n)	O(n㏒₂n)	O(n²)	O(㏒₂n)	不稳定
归并排序	归并排序	Mergesort	O(n㏒₂n)	O(n㏒₂n)	O(n㏒₂n)	O(n)	稳定
归并排序	Timsort	Timsort	O(n㏒₂n)	O(n)	O(n㏒₂n)	O(n)	稳定
基数排序	基数排序	Radix Sort	O(nk)	O(nk)	O(nk)	O(n+k)	稳定
桶排序	桶排序	Bucket Sort	O(n+k)	O(n+k)	O(n²)	O(n)	稳定
计数排序	计数排序	Counting Sort	O(n+k)	O(n+k)	O(n+k)	O(k)	稳定

排序算法总览表