By

Contents
  1. 1. 一、稳定性
  2. 2. 二、时间复杂度
  3. 3. 三、排序算法的选择
    1. 3.1. 1. 数据规模较小
    2. 3.2. 2. 数据规模不是很大
    3. 3.3. 3. 数据规模很大
    4. 3.4. 4. 序列初始基本有序，适合直接插入，冒泡

一、稳定性

稳定： 冒泡排序、插入排序、归并排序、基数排序
不稳定： 选择排序、快速排序、希尔排序、堆排序

二、时间复杂度

O(n^2): 直接插入排序、简单选择排序、冒泡排序
O(nlgn): 快速排序、归并排序、堆排序、希尔排序 （快徘>归并、希尔> 堆徘）

三、排序算法的选择

1. 数据规模较小

  • 待排序列基本序的情况下，可以选择直接插入排序；
  • 对稳定性不作要求宜用简单选择排序，对稳定性有要求宜用插入或冒泡

2. 数据规模不是很大

  • 完全可以用内存空间，序列杂乱无序，对稳定性没有要求，快速排序，此时要付出log（n）的额外空间
  • 序列本省可能有序，对稳定性有要求，空间允许下，宜用归并排序

3. 数据规模很大

  • 对稳定性有要求，则可考虑归并排序
  • 对稳定性没有要求，则 堆排序

4. 序列初始基本有序，适合直接插入，冒泡

Contents
  1. 1. 一、稳定性
  2. 2. 二、时间复杂度
  3. 3. 三、排序算法的选择
    1. 3.1. 1. 数据规模较小
    2. 3.2. 2. 数据规模不是很大
    3. 3.3. 3. 数据规模很大
    4. 3.4. 4. 序列初始基本有序，适合直接插入，冒泡