# 原创
：  专题：排序算法

# 专题：排序算法

## 专题：排序算法

#### 文章目录

### 1、排序分类

|算法|平均|最好|最坏|空间|稳定性
|------
|冒泡排序|O(N^2)|O(N)|O(N^2)|O(1)|稳定
|直接插入排序|O(N^2)|O(N)|O(N^2)|O(1)|稳定
|折半插入排序|O(NlogN)|O(NlogN)|O(N^2)|O(1)|稳定
|简单选择排序|O(N^2)|O(N^2)|O(N^2)|O(1)|不稳定
|快速排序|O(NlogN)|O(NlogN)|O(N^2)|O(logN)~O(N^2)|不稳定
|希尔排序|O(NlogN)| |O(n^s)|O(1)|不稳定
|归并排序|O(NlogN)|O(NlogN)|O(NlogN)|O(N)|稳定
|堆排序|O(NlogN)|O(NlogN)|O(NlogN)|O(1)|不稳定
|基数排序|O(d(n+r_d))| |O(d(n+r_d))|O(r_d)|稳定
|二叉树排序|O(n+k)|O(n+k)|O(n+k)|O(n+k)|稳定

外部排序较为复杂，后续更新。。。

### 2、常识总结

> 
<p>助记：**快些**以 
      
       
        
        
          n 
         
        
          l 
         
        
          o 
         
         
         
           g 
          
         
           2 
          
         
        
          n 
         
        
       
         nlog_2n 
        
       
     nlog2​n的速度**归队**</p>


> 
稳定性助记：考研复习痛苦啊，情绪**不稳定**，**快些选一堆**好友来聊天吧.


这里需要注意简单选择排序有两个版本，交换板(数组为载体)和插入版(链表为载体)，后者能得到稳定的结果。

> 
更新于2018年10月25日00:30