数据结构与算法 - 03排序 (冒泡、插入、归并、快速、拓扑)
分类:
文章
•
2024-01-07 12:42:34
-
-
- 给定一个数组，这些元素将通过相互之间的比较，按照大小顺序一个个地像气泡一样浮出水面
-
-
- 每一轮，从头部开始，每两个元素比较大小进行交换，直到这一轮中最大或最小元素被放置到尾部，不断重复，直到所有元素都排好位置
-
-
-
- 指如果数组里两个相等的数，那么排序前后这两个相等的数的相对位置保持不变
-
-
- 冒泡排序中，经过每一轮的排序处理后，数组后端的数是排好序的
- 插入排序中，经过每一轮的排序处理后，数组前段的数是排好序的
-
-
- 将数组分成左右两个部分，左边是已经排好序的部分，右边是没排序的部分
- 刚开始时，左边只有第一个元素
- 接下来，对右边的元素一个个进行处理，将他们放到左边
-
-
- 分治
- 把复杂的问题分成两个或多个相同或相似的子问题，
- 然后把子问题分成更小的子问题，直到子问题可以简单的直接求解，
- 圆问题的解，就是子问题解的合并
-
-
- 先把数组从中间划分成两个子数组，一直递归地把子数组划分成更小的子数组，直到子数组里只有一个元素，才开始排序
- 排序方法：按照大小顺序合并两个元素，接着依次按照递归的返回顺序，不断地合并排好序的子数组，直到最后把整个数组的顺序排好
-
-
-
从原始的数组，选取一基准值，筛选成较小和较大的两个子数组，然后从两个子数组不断地挑选基准值，进行递归排序，当所有的子数组的元素个数都为 1 时结束
-
-
-
时间 最优：O(nlogn) 最坏：O(n2)
-
空间 O(logn)
-
-
-
LC 215：给定一个尚未排好序的数组，要求找出第 k 大的数
-
-
-
-
解1 直接将数组进行排序，然后得出结果
-
解2 快速排序：每次随机选取一个基准值，将数组分成较小的一半和较大的一半，然后检查这个基准值最后所在的下标是不是 k，算法复杂度只需要 O(n)
-
-
-
1. 将问题用一个有向无环图进行抽象表达，定义出哪些是图顶点，顶点之间如何互相关联
-
2. 可以利用广度优先搜索 或 深度优先搜索 进行拓扑排序
-
-
-
选择一个没有前驱（入度为 0）的顶点，输出，然后删除该顶点及相关的有向边
- 重复上述操作
