排序算法大体可分为两种：
一种是比较排序，时间复杂度O(nlogn) ~ O(n^2)，主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。
另一种是非比较排序，时间复杂度可以达到O(n)，主要有：计数排序，基数排序等。
| 算法名称 | 原理 | 发明时间 | 发明人 | 平均时间复杂度 | 最坏时间复杂度 | 最优时间复杂度 | 空间复杂度（辅助空间） | 稳定性 |
|---|---|---|---|---|---|---|---|---|
| 冒泡排序(Bubble Sort) | 重复地遍历要排序的序列，一次比较两个元素，如果它们顺序错误就把它们交换过来。 | O(n^2) | O(n^2) | O(n) | O(1) | 稳定 | ||
| 选择排序(Selection Sort) | 在未排序序列中找到最小（大）元素，存放到已排序序列的末尾。 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 | ||
| 插入排序(Insertion Sort) | 对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。 | O(n^2) | O(n^2) | O(n) | O(1) | 稳定 | ||
| 希尔排序(Shell Sort) | 将待比较的所有元素分为几个区域，让一个元素可以一次性地朝最终位置前进一大步。 | 1959 | Donald Shell | 根据步长序列的不同而不同 | 根据步长序列的不同而不同。已知最好的： O(n(logn)^2) | O(n) | O(1) | 不稳定 |
| 归并排序(Merge Sort) | 将两个已经排序的序列合并成一个序列。 | 1945 | 冯·诺伊曼 | O(nlogn) | O(nlogn) | O(n) | O(n) | 稳定 |
| 快速排序(Quick Sort) | 使用分治策略把一个序列分为两个子序列，其中一个子序列所有元素的键值都比基准小，另一个都比基准大。 | 1962 | 托尼·霍尔（Tony Hoare） | O(nlogn) | O(n^2) | O(nlogn) | 根据实现方式不同而不同 | 不稳定 |
| 堆排序(Heap Sort) | 堆是一棵完全二叉树，其子节点的键值总是小于（或大于）它的父节点。 | 1964 | 罗伯特·弗洛伊德(Robert W．Floyd）和威廉姆斯(J．Williams） | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
| 基数排序(Radix Sort) | 将整数按位数切割成不同的数字，然后按每个位数进行比较。 | 1887 | 赫尔曼·何乐礼（Herman Hollerith） | O(kn) | O(n+k) | 稳定 | ||
| 计数排序(Counting Sort) | 把键值作为计数数组的索引。 | 1954 | Harold H. Seward | O(n+k) | O(n+k) | O(n+k) | O(n+k) | 稳定 |
网友评论