排序算法小小总结

- 日理万妓 2022-06-17 23:15 156阅读 0赞

比较排序：排序结果中个元素的次序基于输入元素间的比较。这列排序称为比较排序。O(logn)  
稳定性：所有相等的数经过排序后，仍能保持它们在排序之前的相对次序，称为稳定排序。否则，称为非稳定排序。  
内排序：排序过程中所有需要排序的数都在内存，并在内存中调整他们的存储顺序。  
外排序：排序中只有部分被调入内存，借助内存调整数在外村的存放顺序的排序方法。  
  
空间复杂度：空间性能是排序所需辅助空间大小  
排序算法(都是内排序，内排序也是外排序的基础)

<table> 
 <tbody> 
 <tr> 
 <td> 排序算法 </td> 
 <td> 怎样排序 </td> 
 <td> 时间复杂度 </td> 
 <td> 空间复杂度 </td> 
 <td> 稳定性 </td> 
 </tr> 
 <tr> 
 <td> 冒泡排序 </td> 
 <td> 比较排序 </td> 
 <td> O(n^2) </td> 
 <td> O(1) </td> 
 <td> 稳定排序 </td> 
 </tr> 
 <tr> 
 <td> 插入排序 </td> 
 <td> 比较排序 </td> 
 <td> O(n^2) </td> 
 <td> O(1) </td> 
 <td> 稳定排序 </td> 
 </tr> 
 <tr> 
 <td> 归并排序 </td> 
 <td> 比较排序 </td> 
 <td> O(n*log n) </td> 
 <td> O(n) </td> 
 <td> 稳定排序 </td> 
 </tr> 
 <tr> 
 <td> 计数排序 </td> 
 <td> 非比较 </td> 
 <td> &nbsp; </td> 
 <td> O(1) </td> 
 <td> 稳定排序 </td> 
 </tr> 
 <tr> 
 <td> 基数排序 </td> 
 <td> 非比较 </td> 
 <td> &nbsp; </td> 
 <td> O(1) </td> 
 <td> 同子排序 </td> 
 </tr> 
 <tr> 
 <td> 桶排序 </td> 
 <td> 非比较 </td> 
 <td> &nbsp; </td> 
 <td> O(1) </td> 
 <td> &nbsp; </td> 
 </tr> 
 <tr> 
 <td> &nbsp; </td> 
 <td> &nbsp; </td> 
 <td> &nbsp; </td> 
 <td> &nbsp; </td> 
 <td> &nbsp; </td> 
 </tr> 
 <tr> 
 <td> 选择排序 </td> 
 <td> 比较排序 </td> 
 <td> O(n^2) </td> 
 <td> O(1) </td> 
 <td> 非稳定排序 </td> 
 </tr> 
 <tr> 
 <td> 堆排序 </td> 
 <td> 比较排序 </td> 
 <td> O(n*log n) </td> 
 <td> O(1) </td> 
 <td> 非稳定排序 </td> 
 </tr> 
 <tr> 
 <td> 快速排序 </td> 
 <td> 比较排序 </td> 
 <td> 最坏O(n^2),平均O(n*log n) </td> 
 <td> O(log n) </td> 
 <td> 非稳定排序 </td> 
 </tr> 
 <tr> 
 <td> Shell排序 </td> 
 <td> 比较排序 </td> 
 <td> O(n^a),1&lt;a&lt;2,平均a约为1.3 </td> 
 <td> O(1) </td> 
 <td> 非稳定排序 </td> 
 </tr> 
 </tbody> 
</table>

计数排序应用场景：假设n个输入元素中的每一个都介于0—k之间的整数。总的运行时间是O(n+k);当k=O(n)时，基数排序的运行时间为O(n)。  
基数排序:给定n个d位数，每一个数位可以取k种可能的值。如果所用的稳定排序需要O(n+k)的时间，基数排序算法能以O(d(n+k))的时间正确地对这些数进行排序。  
桶排序，又称箱子排序：桶排序的输入大致符合均匀分布，所有输入数据的取值范围是已知的\[a，b),分r个相同大小的子区间（就是桶），每个桶使用链表存储数据，链表是有序的。运行时间复杂度O(n+r)。  
  
  
其中插入，归并，快速已经整理。其他算法没有整理，这些排序算法留待以后整理成代码。