数据结构算法分析！在线等待！当待排序元素的个数n小，元素基本有序，且要求稳定时，则采用为宜，当待排序元素的个数n大，内存空间允许，且要求排序稳定时，则采用为宜

Question

数据结构 算法分析！ 在线等待！
当待排序元素的个数n小，元素基本有序，且要求稳定时，则采用___为宜，当待排序元素的个数n大，内存空间允许，且要求排序稳定时，则采用____为宜

Answer 1

当待排序元素的个数n小，元素基本有序，且要求稳定时，则采用_冒泡__为宜，当待排序元素的个数n大，内存空间允许，且要求排序稳定时，则采用_归并_为宜
下面是一个总的表格，大致总结了我们常见的所有的排序算法的特点。 排序法 平均时间 最差情形 稳定度 额外空间 备注
冒泡 O(n2) O(n2) 稳定 O(1) n小时较好
交换 O(n2) O(n2) 不稳定 O(1) n小时较好
选择 O(n2) O(n2) 不稳定 O(1) n小时较好
插入 O(n2) O(n2) 稳定 O(1) 大部分已排序时较好
基数 O(logRB) O(logRB) 稳定 O(n) B是真数(0-9)，
R是基数(个十百)

Shell O(nlogn) O(ns) 1<2 不稳定 O(1) s是所选分组
快速 O(nlogn) O(n2) 不稳定 O(nlogn) n大时较好
归并 O(nlogn) O(nlogn) 稳定 O(1) n大时较好
堆 O(nlogn) O(nlogn) 不稳定 O(1) n大时较好