排序算法
分类
-
比较类排序
通过比较来决定元素间 的相对次序，由于其时间复杂度不能突破 O(nlogn)，因此也称为非线性时间比较类排序。
-
非比较类排序
不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称线性时间非比较类排序。
image.png
复杂度
image.png
相关概念
-
稳定：如果 a 原本在 b 前面，而 a=b，排序之后 a 仍然在 b 的前面。
-
不稳定：如果 a 原本在 b 的前面，而 a=b，排序之后 a 可能会出现在 b 的后面。
-
时间复杂度：对排序数据的总的操作次数。当 n 变化时，操作次数呈现什么规律。
-
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模 n 的函数。
初级排序 - O(n^2)
-
选择排序（Selection Sort）
每次找最小值，然后放到待排序数组的起始位置。
-
插入排序 （Insertion Sort）
从前到后逐步构建有序序列；对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
-
冒泡排序（Bubble Sort）
嵌套循环，每次查看相邻的元素如果逆序，则交换。
高级排序
-
快速排序（Quick Sort）
数组取标杆 pivot，将小元素放 pivot 左边，大元素放右侧，然后依次对右边和右边的子数组继续快排；以达到整个序列有序。
-
归并排序（Merge Sort）- 分治
-
把长度为 n 的输入序列分为两个长度为 n/2 的子序列；
-
对这两个字序列分别采用归并排序；
-
将两个排序好的子序列合并成一个最终的排序序列。
-
-
堆排序
1. 数组元素依次建立小顶堆；
2. 依次取堆顶元素，并删除。
特殊排序
-
计数排序（Counting Sort）
计数排序要求输入的数据必须是有确定范围的整数。将输入的数据值转化为键存储在额外开辟的数组空间中；然后依次把计数大于 1 的填充回原数组。
-
桶排序（Bucket Sort）
桶排序（Bucket sort）的工作原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再 分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。
-
基数排序
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先 按低优先级排序，再按高优先级排序。
