十大排序算法
算法是为求解一个问题需要遵循的、被清楚指定的简单指令的集合。
排序算法是《数据结构与算法》中最基本的算法之一，常见的共有十种：
- 1. 冒泡排序（Bubble Sort）
- 2. 选择排序（Selection Sort）
- 3. 插入排序（Insertion Sort）
- 4. 希尔排序（Shell Sort）
- 5. 归并排序（Merge Sort）
- 6. 快速排序（Quick Sort）
- 7. 堆排序（Heap Sort）
- 8. 计数排序（Counting Sort）
- 9. 桶排序（Bucket Sort）
- 10. 基数排序（Radix Sort）
1. 排序算法的分类
排序算法可以分为两大类：
- 比较类排序
- 非比较类排序
通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
2. 排序算法的复杂度
3. 排序算法的相关概念
- 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
- 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
- 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
- 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
冒泡排序（Bubble Sort）：冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。冒泡排序的算法描述。比较相邻的元素。如果第一个比第二个大，就交换它们两个。