八大经典排序算法的理解、动图演示和C++方法实现
刘刘 2021-05-10 23:45:21 2021-05-10 131 0
晚上加班整理了另一篇算法必备基础类文章，七大查找算法的理解与实现，可点击链接进行查阅。
0. 排序算法概述
所谓排序，就是使一串序列，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。掌握基本排序方法是算法入门的必备基础知识。这里将要介绍八种经典排序算法，希望这篇文章帮助我们对排序算法有一个全面理解。
看到有文章说计数排序是稳定排序，实际上计数排序是重新赋值的，所以我的理解它应该属于不稳定排序。这里介绍的8种排序算法的基本情况，如下思维导图和表格所示：
| 排序算法 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O ( n 2 ) O(n^2) O(n2) | O ( n ) O(n) O(n) | O ( n 2 ) O(n^2) O(n2) | O ( 1 ) O(1) O(1) | 稳定 |
| 选择排序 | O ( n 2 ) O(n^2) O(n2) | O ( n 2 ) O(n^2) O(n2) | O ( n 2 ) O(n^2) O(n2) | O(1)$ | 不稳定 |
| 插入排序 | O ( n 2 ) O(n^2) O(n2) | O ( n ) O(n) O(n) | O ( n 2 ) O(n^2) 暂无评论 |