常用排序算法归纳
评价排序算法好坏的标准：
1.执行时间和所需的辅助空间。
2.算法本身的复杂程度。
| 排序 | 稳定性 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 气泡排序(bubble sort) | 稳定 | 最差、平均为O(n²)，最好为O(n) | 1 |
| 插入排序(insertion sort) | 稳定 | 最差、平均为O(n²)，最好为O(n) | 1 |
| 归并排序(merge sort) | 稳定 | 最差、平均和最好都是O(nlog n) | O(n) |
| 二叉树排序(Binary tree sort) | 稳定 | O(nlog n) | O(n) |
| 选择排序(selection sort) | 不稳定 | 最差、平均都是O(n²) | 1 |
| 堆排序(heapsort) | 不稳定 | 最差、平均和最好都是O(nlog n) | 1 |
| 快速排序(quicksort) | 不稳定 | 平均是O(n log n),最坏情况O(n²) | O(log n) |
No comments:
Post a Comment