排序算法
2022-05-31 本文已影响0人
风之子__
排序算法
- 概念
- 排序稳定性
- 相同关键字排序前后相对顺序
- 插入排序
- 直接插入
- 逐步将无序区的数据插入有序区
- 顺序比较得出插入的位置
- 时间复杂度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，稳定
- 二路归并
- 基数排序
- 排序稳定性
