远方的岛第六章 内部排序
type
status
date
slug
summary
tags
category
icon
password
6.1基本概念
排序/分类、排序算法的稳定性：相同关键字值相对次序不变
分类：（按排序对象存放的设备）内部排序、外部排序
（操作是否基于关键字的比较）基于比较、不基于比较
C
A
6.2冒泡排序
时间复杂度O(n²) 空间复杂度O(1) 稳定排序
6.3快速排序
分治策略：基准元素选取、划分、递归求解、组合
时间复杂度O(nlog2n) 空间复杂度O(log2n) 不稳定排序
A
C 区分：移动次数、比较次数
A 别只看前面，还有后面
A
D
C
C
D
A
C
C
D
B
D
6.4直接选择排序
时间复杂度O(n²) 空间复杂度O(1) 不稳定排序
6.5堆排序
堆：完全二叉树、最小/最大堆
建堆、调堆
时间复杂度O(nlog2n) 空间复杂度O(1) 不稳定排序
适合关键字较多的情况
C
D
A
AD
A
B
A
C 把最末尾的12放到堆顶C 把最末尾的12放到堆顶
A 从下至上，从右至左
6.6（直接）插入排序
时间复杂度O(n²) 空间复杂度O(1) 稳定排序
折半插入排序
6.7希尔排序/分组插入排序/缩减增量排序
步长
时间复杂度O(nlog2n) 空间复杂度O(1) 不稳定排序
D
DA
B
B
B
C
A 快速排序基准元素
A
D
6.8（二路）归并排序
时间复杂度O(nlog2n) 空间复杂度O(n) 稳定排序
6.9基数排序/多关键字排序/桶排序
初态（队列）、分配、收集、重复
C
C
B
D 外部排序
B
B
D
C 在前一趟的基础上
C
期末真题
2021
A
007 110 911 114 119 120 122
2020
n/2-1
2017
C
B
A
2016
C 下界——最低
log2n nlog2n
字母表基数排序
2015
B
D
Loading...