排序算法

排序算法

• 概念
  • 排序稳定性
    • 相同关键字排序前后相对顺序
  • 插入排序
    • 直接插入
      • 逐步将无序区的数据插入有序区
      • 顺序比较得出插入的位置
      • 时间复杂度n^2,空间复杂度1,稳定
    • 折半插入
      • 折半查找得出插入位置
      • 时间复杂度n^2,空间复杂度1,稳定
    • 希尔排序
      • 分组进行插入排序
      • 平均时间复杂度n^1.3,空间复杂度1，不稳定
  • 交换排序（全局有序）
    • 冒泡排序
      • 两两比较，交换，每趟排序归位一个数到全局有序区
      • 时间复杂度n^2,空间1，稳定
    • 快速排序
      • 划分：用基准元素划分带排序数列，前小后大，此基准元素全局有序，
      • 接着对划分后的前后区域递归调用划分算法
      • 直到划分区域大小为1或者0
      • 时间复杂度nlogn,空间n，不稳定
  • 选择排序（全局有序）
    • 简单选择排序
      • 每次从无序区顺序遍历选择一个最值，放入有序区中
      • 时间n^2，空间1，不稳定
      • 最坏n^2
    • 堆排序
      • 利用建立根堆树选择最值
      • 时间nlogn,空间1，不稳定
  • 归并排序
    • 二路归并
      • 将两个有序序列合并为一个有序序列
      • 递归调用二路归并，区间由小到大
      • 时间nlogn，空间n，稳定
  • 基数排序

© 著作权归作者所有,转载或内容合作请联系作者